백준

백준 9461 풀이 (파도반 수열, 메모제이션, 다이나믹 프로그래밍)

이번 문제는 상당히 쉽게 풀었다. 왜냐하면 이전에 피보나치수열을 경험해보았기 때문이다. 파도반 수열은 아래와 같다. [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ......] 이 수열의 점화식을 세우면...... f(n) = f(n-1) + f(n-5) 단, n>5이어야한다. 따라서 제약조건을 토대로 재귀함수를 만들면 피보나치와 거의 유사하다. 하지만 이번에는 메모제이션 기법을 이용하여 효율적인 코딩을 해보기로 한다. (내 머리속 지우개는 굉장히 부지런하다보니 안쓰면 굉장히 빨리 까먹는다. 써볼 수 있을때 많이 써봐야한다.) n = int(input()) tmp = [0 for i in range(100)] tmp = [1,1,1,2,2] + tmp def pado(n): if n..

백준 1904 풀이 (재귀함수 인척하는 점화식 풀이)

이거 문제도 파악하고 금방 식을 세웠다. 그런데 재귀함수로 풀으려 했더니 메모리 초과나고, 출력도 초과나고 난리도 아니었다. 결국에 고수분들 푼거 슬쩍 보고오니 재귀함수로 푸는게 아니었다. 낚였다. 사실 재귀함수를 써야할 때가 있고 재귀함수를 안써도 되는 경우가 존재한다. 예를 들어 연산이 너무 많아지는 경우에는 재귀함수를 정말 써야하는지 고민해보아야한다. 만약 재귀함수를 써야하는 경우에는 다이나믹 프로그래밍을 염두해 보고, 그래도 초과가 난다면 최대 재귀 제한을 풀어주면 된다. import sys sys.setrecursionlimit(재귀횟수) 난 점화식도 세웠고 딱히 재귀함수를 써야할 필요성이 없음에도 재귀함수로 푸는 것이라 추측하고 재귀를 놓지를 못했다. 그래서 이렇게 뻘한 삽질을 반복했다. 그래..

백준 9184 풀이 (재귀함수, 메모제이션, 다이나믹 프로그래밍)

우선 이 문제를 보고 당혹감을 감출 수 없었다. 식을 그냥 줬다. 그냥 풀어보라고 줘버린것이다. 이런건 유저가 만들어야하는데 주는 이유가 있을것이다. 처음에는 규칙을 찾아야하나?하고 고민을 했다. 솔직히 저렇게 복잡하게 얽히고 섥혀있는데 규칙을 어떻게 찾나 고민을 했다. 그러다가 9184를 구글링 했더니 메모제이션이라는 기법이나 DP가 같이 쓰여있는 것을 확인했다. 그래서 메모제이션을 찾아보았다. 메모제이션이란 일반적인 재귀에서 이미 같은 인자를 연산했더라도 또 연산하는 경우가 존재한다. 그래서 이미 연산한 결과는 저장해두고, 만약 같은 연산이 필요할때 꺼내어 쓰자는 의도이다. ssminji.github.io/2020/02/05/the-cake-thief/ [알고리즘] Memoization(메모이제이션)..

백준 14889 풀이 (itertools,combinations)

이번에 itertools를 처음 배웠다. itertools는 자신만의 반복자를 만들기 위해서 사용되는 모듈이다. 즉 무엇인가 반복되는 요소를 쉽게 만들기 위해서 사용한다. 이 문제는 조합을 만들어야 하기 때문에 combinations를 함수에 대해서만 공부했다. combinations는 조합을 만들어 주는 함수이다. combinations([1,2,3,4], 2) 를 하면 4개의 수를 2조합으로 만들겠다는 의미다. 따라서 이러한 값을 이용해서 조합을 빠르게 구한다. 나는 조합을 못구해서 얼타다가 결국 고수의 코드를 참고하여 이해했다. from itertools import combinations N = int(input()) Nlist = [i for i in range(N)] Map = [] for _..

백준 14888 풀이 (재귀함수, 백트래킹, 연산자 끼워넣기)

일단 혹시나 내 코드를 보시는 분은 내가 아직도 백트래킹을 이해를 못한 관계로 코드만 참고하면 좋겠다. 일단 한방에 성공하긴 했으나 아직도 재귀와 백트래킹이 두려운 시점이라 일단 재귀로 대충짜봤다. 1. 주어진 값들을 리스트와 연산자 맵을 재귀함수로 사용한다. 2. 리스트의 0번째와 1번째를 연산자 맵에서 하나꺼내서 사용한다. 3. 반복하다가 연산자 맵이 전부 0이면(sum이 0이면) 종료하고 전체 리스트에 넣어준다. n = int(input()) nlist = list(map(int,input().split())) Map = list(map(int,input().split())) Tmp = [] def back(nlist, miniMap): if len(nlist) == 1: Tmp.append(nli..

백준 9663 풀이 (백트래킹, 재귀함수)

사실 어제 풀다가 안풀려서 포기했다. 어제 짠 코드는 모든 경우를 다 확인하다보니 시간도 오래걸리고, 무엇보다 중복이 생겼다. 그래서 그냥 시원하게 던져버리고 오늘 다시 풀어보았다. 오늘은 접근을 달리했다. N * N개의 판에서 퀸이 4개가 들어가야한다고 하는데 이는 결국 각 행마다 퀸이 딱 하나씩 들어가야한다는 소리다. 즉, 무조건 배열이 [[0,?], [1,?], [2,?], [3,?] ......[n-1,?]] 이런 방식이면 되는거다. 따라서 이를 토대로 코드를 짰다. N = int(input()) sum = 0 def queen(tlist,n): global N global sum if len(tlist) == N: sum+=1 return for i in range(N): check = 0 fo..

백준 15650 풀이 (재귀함수)

저번에 풀었던 15649문제에서 코드를 살짝만 수정하면 쉽게 구할수 있다. 조건은 뒤에 수열이 반드시 오름차순이어야하며 중복을 포함하지 않는다. 코드의 중복이 살짝 있지만 애교로 넘어가자 n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map[i],end=' ') print() return for i in range(n): if len(tlist) == 0: tlist.append(i) back(tlist,n,m-1) tlist.pop() else: if i > tlist[-1]: tlist.append(i) back(tlist,n,m-1) tli..

백준 15649 풀이 (재귀함수, 백트래킹)

음 백트래킹이 먼지 몰랐다. 그래서 여기저기 기웃거려본 결과 트리를 만들때 불필요한걸 쳐내면서 트리를 만드는거 같다. 물론 이 문제에 백트래킹을 어떻게 적용해야하는지 전혀 이해못했다. 그냥 재귀함수로 적용해서 풀어보자! 라는 마인드로 풀었는데 어찌저찌 풀리긴 풀렸다. 순서는 다음과 같다. 1. 빈 리스트, n, m을 인자로 넣어준다. 2. for 을 이용하여 사용되지 않은 숫자를 리스트에 추가하며 재귀함수를 실행시킨다. 3. m을 하나씩 줄여서 m이 0이 되면 리스트에 저장된 값을 출력해준다. n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map..