1. 문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 2차원 DP형태의 문제라 직관적으로 해답을 떠올리기 다소 어려운 유형의 문제라고 할 수 있다. 따라서 점화식을 먼저 한 번 도출해보도록 하자. 숫자 N을 정수 K개의 조합으로 만들 수 있는 문제를 다시 재조합하면 아래와 같이 생각할 수도 있다. dp[N][K]는 N을 K개 조합으로 만드는 경우의 수를 의미하고, 예시로 N = 6이고 K = 4라고 가정해보자. (_ , _ , _ , L) 네 개의 숫자 조합에서 마지막 자리를 L(0 ≤ L ≤ 6) 로 결정한다면, L 값에 따라서 아래 표의 경우의 수가 만들어짐을 알 수 있다. L case 0 dp[6][3] 1 dp[..

특정한 문제를 풀이함에 있어 큰 문제를 작은 문제로 나뉘어서 푸는 방법들에 대해서는 앞선 포스트들을 통해 계속해서 언급하였다. 오늘 다룰 분할정복(Divide & Conquer)은 그 패러다임을 가장 직관적으로 다루는 테크닉이라고 볼 수 있다. 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 것 분할정복은 아래의 세 구성요소로 다시 생각해볼 수 있다. Divide : 문제를 더 작은 문제로 분할하기 Merge : 각 문제의 답을 원래 문제에 대한 답으로 병합 Base Case : 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 세 구성요소에 대해서는 부가적인 설명이 필요없을 것으로 보이나, 분할정복으로 특정 문..

동적 계획법은 정말 가장 많이 대회에서 출제되는 문제 유형임과 동시에 반드시 알아야만 하는 내용이기도 하다. 명확하게 '이것이 동적 계획법 문제다' 라고 분류하기 보다는 앞선 브루트 포스나 그리디 알고리즘과 같이 문제를 풀어나가는 하나의 방법으로 접근하는 것이 올바르다고 생각한다. 동적 계획법 역시 큰 문제를 작은 문제로 나누는 것에서 출발한다. 지금까지의 내용을 정리하면 아래와 같다. 브루트 포스(Brute Force): 작은 문제 하나하나 다 살펴볼거야! 탐욕법(Greedy): 작은 문제마다 답을 선택해 버릴거야! 그렇다면 동적 계획법의 메커니즘은 어떤 것일까? 다른 작은 문제에서 만들어 놓은 값을 다시 쓸거야! 즉, 작은 문제들로 분류하여 연산을 하는 과정에서 같은 연산을 반복적으로 수행해야 한다면..