본문 바로가기

메모이제이션2

백준 1904. 01타일 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이 🔔 문제 설명은 백준 문제 링크로 대신합니다 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 피보나치 수열이라 메모이제이션 방식과 바텀업 방식 둘 다로 풀어보았는데, 메모이제이션 방식은 재귀 깊이 설정(setrecursionlimit())을 안 하거나 충분한 깊이로 하지 않으면 RecursionError가 발생하고, 충분한 깊이로 하면 메모리 초과가 발생한다. 문제에서 N의 범위가 1 ≤ N ≤ 1,000,000 라고 해서 재귀 깊이를 10**7로 했더니 메모리가 초과되고, 줄였더니 런타임에러가 발생했다. 결국 메.. 2022. 10. 15.
백준 2748. 피보나치 수 2 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이 🔔 문제 설명은 백준 문제 링크로 대신합니다 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열의 n번째 원소를 출력하는 문제이다. 이번 주 학습 주제인 동적프로그래밍과 그리디에 대해서 먼저 이론을 공부하고 문제를 풀었는데, 피보나치 수열은 동적프로그래밍의 너무나도 대표적인 예시라서 공부를 하는 과정 중에 먼저 코드를 이해할 수 있었고 문제를 금방 풀 수 있었다. 동적프로그래밍의 두 방식 메모이제이션(memoization)과 바텀업(bottom-up) 방식 모두로.. 2022. 10. 14.
반응형