[파이썬] 15649 N과 M (1) feat 띠용하다!
2022. 2. 4. 04:08
프로그래밍/파이썬
오늘은 백트래킹을 풀어보기로 했다 사실 dfs 가 적혀있어서 그래프를 마치고 하려 했는데 dfs만으로도 풀 수 있는데 왜 묵히고 있었을까!라는 마음에 그냥 들어가 보기로 했다 문제는... 사실 for문으로 풀까 생각했다 근데 그러면 백트래킹이 아니라 브루트 포스가 아닌가! 결국 for문을 적절하게 제어할만한 방법이 필요하다 거기서 dfs를 쓴다는 것을 알게 되었다 사실문제 보고 답이 없어서 구글링을 하면서 수십 개의 답을 봤다 결국 메커니즘은 같았는데 이러하다 1. 숫자 2개를 받아 dfs 시작 2. 4, 4일 경우 1부터 시작해서 4까지 가면서 배열에 for숫자를 넣어준다 근데 여기서 for 숫자 하나에 각각 dfs를 걸어준다 예를 들어서 for i==1일 때 dfs를 걸어 다시 1부터 시작하게 한다 ..
[파이썬] 11053 가장 긴 증가하는 부분 수열
2022. 2. 3. 07:47
프로그래밍/파이썬
최근에 조금 놀았다 그래도 하루에 한 문제는 풀고 놀았다... 물론 그게 유익한 풀이라고는 할 수는 없으나 적어도 습관을 유지하기 위해서는 꼭 한 문제는 풀어야 한다는 생각.. 새벽에 dp나 하나 풀어보자! 해서 단계별 학습에 있는 dp문제를 하나 가져왔다 LIS라 불리는 문제인 듯한데.. 유명한듯하다 처음 문제 딱 봤을 때는 ?? 이거 그냥 배열로 풀면 풀리는 거 아니냐 해서 질문게시판에 있는 반례 몇 개와 돌려봤더니 역시 틀렸다 문제를 살짝 잘못 이해하고 있었다 5 40 1 5 10 90 문제의 예제와 이 반례를 생각하면 쉽게 풀릴 것 같다 증가하는 부분 배열이니 중간에 끊기는 건 상관없으나 제일 처음에 잘리는 수는 빼야한다! 를 깨달았다 사실 여기까지는 생각해냈는데 dp를 어떻게 이용해서 풀어야할지..
[파이썬] 2992 크면서 작은 수
2022. 1. 28. 05:15
프로그래밍/파이썬
새벽에 졸면서 푼다고 어떻게 풀었는지 기억은 나지 않는다 그래도 좀 고민해서 아, 이렇게 풀면 풀리긴 풀리겠네! 해서 그거 생각하고 제출을 보니 역시나 그렇게 풀었다.. num = input() ary = sorted(list(map(int,num.strip()))) k = str(9) fo = int(k*len(num)) count = 0 for i in range(int(num), fo): j =str(i) tempary=sorted(list(map(int,j.strip()))) if tempary == ary: if i>int(num): print (i) count = 1 break if count == 0: print(0) 일단 자릿수를 따와서 자릿수만큼 9를 만든 뒤 for문을 받은 num값부터..
[파이썬] 재귀함수를 이해해보자 feat 10829, 1769, 10872, 2447
2022. 1. 27. 04:00
프로그래밍/파이썬
그래프를 들어가려하니 재귀는 필수인듯하여 재귀문제를 조금 풀어보고 들어가보려 한다 먼저 한 것은 solved에서 재귀 태그를 가진 문제를 난이도별로 정렬, 하나씩 풀어보았다 10829 - 이진수 변환 이 문제는 보자마자 감이왔다 a를 2로 나누고 계속 함수에 쌓고 0이면 print로 쌓인 것들을 하나씩 꺼내 출력한다 사실 이 문제는 재귀보다는 그냥 단 한줄로 문제를 풀어버릴 수가 있다 print(str(bin(int(input()))[2:])) 근데 우리의 목적은 재귀를 사용하여 문제를 푸는 것이니 재귀를 이용해 코드를 작성해보자 def bin(a): if a >1: bin(a//2) return print(a%2,end="") bin(int(input())) 내용은 간단하다 bin(a)를 만들고 a가 ..