[백준] 11726 : 2 x n 타일링 (Python)

출처 : https://www.acmicpc.net/problem/11726  아이디어해당 문제는 DP의 대표적인 유형이다. 그렇다면, 연산 과정(경우의 수)을 통해, 왜 DP로 접근해야 하는지 살펴보자. n이 증가할 때 마다, 어떤 규칙이 있는지를 파악하는 것이 핵심 인사이트이다.먼저, n이 1과 2일때는 손쉽게 경우의 수가 고정되는 것을 알 수 있다. n이 3일때 또한 쉽게 발견할 수 있으나, 다음과 같은 생각을 해봐야 한다.n이 2일 때와 1일 때에서 타일링을 진행하면, n=3일 때의 타일을 만들 수 있지 않을까?이를 통해, n이 1,2일 때의 각 경우를 통해 n=3 경우의 수를 구하게 되면, 점화식 가설을 세울 수 있게 된다. 해당 점화식이 과연 올바른지 확인하기 위해, 우리는 n=4일 때, 가설..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 29.

[백준] 1003 : 피보나치 함수 (Python)

출처 : https://www.acmicpc.net/problem/1003  아이디어해당 문제는 대표적인 그래프 탐색 유형의 문제이며, '중복 연산'에 대한 핵심 인사이트를 개념으로 설명하는 문제이다. 다만, 피보나치 값을 물어보는 것이 아닌, 단말노드인 0과 1을 몇 번 탐색하느냐를 요구사항으로 제시한다.먼저, 일반적인 피보나치 수열에 대한 그래프와 이에 따른 0과 1 단말노드 관점을 시각화하여 살펴보자.왼쪽 그래프에서 Fibo(4), Fibo(3), Fibo(2)과 중복으로 연산된다는 사실을 알 수 있으며, 다음의 DP 조건을 만족하므로, 알고리즘으로 DP를 선택할 수 있다.큰 문제를 작은 문제로 나눌 수 있는가작은 문제의 답이 큰 문제에서 일부분으로 사용되는가이 과정에서 중복되는 연산이 있는가즉, ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 21.

[백준] 9095 : 123 더하기(Python)

출처 : https://www.acmicpc.net/problem/9095  아이디어정수 n의 자식노드들을 트리로 그려보게 되면 n-1, n-2, n-3임을 알 수 있고, 이를 통해, 다음과 같은 규칙을 발견할 수 있다.n의 합 개수는 자식노드들인 각 n-1, n-2, n-3의 개수를 모두 더한 것이다.자식에 해당되는 트리 깊이의 답들이 부모 깊이에서 재사용된다.중복 노드가 존재할 수 있다.그러므로, DP의 조건에 부합되므로 메모제이션 기법이 적용된 DP로 프로그램을 구현할 수 있다. 필자는 Bottom-Up을 선택하였으므로, 보텀업을 통한 DP테이블 저장 과정을 살펴보자. 저장 연산 일반화 공식n이 4일 때를 가정해보자. 4의 모든 경우의 수는 3,2,1 자식노드들을 모두 더한 것과 같다. 이를 통해 ..

• format_list_bulleted Problem Solving/Baekjoon
• · 2025. 1. 15.