메모제이션

백준 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..

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

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