글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>다이나믹 프로그래밍(DP; Dynamic Programming)</h2><h3>해결하기 어려운 문제</h3><p>현실 세계에서 컴퓨터를 활용해도 해결하기 어려운 문제</p><ul><li><strong>최적의 해</strong>를 구하는데 매우 많은 시간이나 메모리 공간이 필요한 문제<ul><li>컴퓨터의 연산 속도의 한계, 메모리 공간의 한계</li></ul></li></ul><p><aside> 💡 <strong>계산 복잡도 이론</strong></p><p>해결하기 어려운 문제에 대해 깊게 다루는 분야. P → NP문제를 다룸</p><p></aside></p><ul><li>효율적인 알고리즘의 설계와 분석 기법<ul><li>다이나믹 프로그래밍<ul><li>최적해에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용</li></ul></li><li>그리디 알고리즘</li><li>분할상환 분석 (amortized analysis)</li></ul></li></ul><h3>다이나믹 프로그래밍이란?</h3><ul><li><strong>큰 문제를 작은 문제로</strong> 나누고, <strong>같은 문제라면 한 번씩만</strong> 풀어 문제를 효율적으로 해결하는 알고리즘 기법</li><li>메모리 공간을 조금 더 활용해 연산 속도를 비약적으로 증가시키는 방법 중 하나</li><li>한국어로 <strong>동적 계획법</strong>이라고도 불림</li><li>분할 정복(Divide and Conquer) 알고리즘과의 차이점<ul><li>문제들이 서로에게 영향을 미치는지 여부<ul><li>영향을 미침 : DP</li><li>영향이 없음 : 분할 정복</li></ul></li></ul></li></ul><p><aside> 💡 <strong>다이나믹 프로그래밍과 동적 할당의 다이나믹</strong></p><p>프로그래밍에서의 다이나믹</p><ul><li>’프로그램이 실행되는 도중에‘라는 의미</li></ul><p>동적 할당</p><ul><li>프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법</li></ul><p>다이나믹 프로그래밍</p><ul><li>DP의 ‘다이나믹’은 이러한 의미가 아니라는 것만 기억하자</li><li>프로그래밍 : 컴퓨터 코드를 쓰는 것을 의미하는 것이 아닌 <strong>테이블을 이용</strong>하는 방법을 말함 </aside></li></ul><p>일반적으로 최적화 문제에 적용</p><ul><li>다양한 해를 가지나 그 중에 최적의 해를 찾는 문제</li></ul><h3>다이나믹 프로그래밍 사용 조건</h3><ol><li>큰 문제를 작은 문제로 나눌 수 있다<ul><li>최적 부분 구조<ul><li>문제의 최적해가 그 안에 부분 문제의 최적해를 포함하는 문제의 구조</li><li>최적 부분 구조를 갖는 문제는 DP나 그리디 적용할 수 있는 단서<ul><li>DP와 그리디 차이<ul><li>DP : 부분 문제들의 최적해를 먼저 구한 후 선택</li><li>그리디 : 선택을 한 다음 그 결과로 얻어진 부분 문제만을 품</li></ul></li></ul></li></ul></li></ul></li><li>작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다<ul><li>중복되는 부분 문제<ul><li>같은 문제를 반복해서 계산해야 함<ul><li>한 번만 계산해 테이블에 넣고 중복될 경우 상수 시간에 테이블 조회</li></ul></li></ul></li></ul></li></ol><h3>메모이제이션(Memoization) 기법</h3><ul><li>다이나믹 프로그래밍을 구현하는 방법 중 한 종류<ul><li>다이나믹 프로그래밍과는 별도의 개념</li></ul></li><li>한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법</li><li>값을 저장하는 방법이므로 **캐싱(Caching)**이라고도 함</li><li>구현 방법</li></ul><p>단순히 한 번 구한 정보를 리스트에 저장</p><p>때에 따라 딕셔너리 자료형을 이용할 수도 있음</p><p>→ 수열처럼 연속적이지 않은 경우 유용</p><p>→ ex) an을 계산하고자 할 때, a0 ~ an-1 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우</p><p>같은 정보가 필요시 이미 구한 정답을 그대로 리스트에서 가져옴</p><h3>다이나믹 프로그래밍 작성 방식</h3><ul><li>탑다운(Top-Down) 방식 (하향식)<ul><li>큰 문제를 해결하기 위해 작은 문제를 호출</li><li>재귀 함수 사용</li><li><strong>메모이제이션</strong> : 이전 결과 저장용 리스트</li></ul></li><li>바텀업(Bottom-Up) 방식 (상향식)<ul><li>작은 문제부터 차근차근 답을 도출해 올라감</li><li>반복문 사용</li><li>다이나믹 프로그래밍의 전형적 방식</li><li><strong>DP 테이블</strong> : 결과 저장용 리스트</li></ul></li></ul><h3>DP 알고리즘 개발 (풀이) 4단계</h3><ol><li>최적해의 구조의 특징을 찾음</li><li>최적해의 값을 재귀적으로 정의 (점화식을 세움)</li><li>최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산</li><li>계산된 정보들로부터 최적해를 구성</li></ol><h3>코딩테스트와 다이나믹 프로그래밍</h3><ul><li>대체로 간단한 유형이 출제됨</li><li>주어진 문제가 DP 유형임을 빠르게 파악하는 것이 중요<ul><li>특정 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸리는 경우</li><li>부분 문제들의 중복 여부 체크</li></ul></li><li>일단 단순히 재귀를 이용해 비효율적인 프로그램을 작성한 뒤 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용할 수 있으면, 즉 메모이제이션을 적용할 수 있다면 코드를 수정해 개선해 나가는 방법도 좋음</li><li>가능하다면 탑다운 방식의 재귀보단 바텀업 방식으로 구현하는 것을 권장<ul><li>시스템상 재귀 함수의 스택 크기가 한정되어 있음<ul><li><code>sys</code> 라이브러리의 <code>setrecursionlimit()</code> 를 이용해 재귀 제한을 완화 가능하긴 함</li></ul></li></ul></li></ul><h2>피보나치 수열과 DP</h2><h3>기본적인 피보나치 재귀 함수 코드</h3><pre><code class="language-python">def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(6)) </code></pre><ul><li>문제점</li></ul><p>n이 커질수록 수행 시간이 기하급수적으로 늘어남</p><ul><li>동일한 함수가 반복적으로 호출되어 비효율적임</li><li>O(2^N) (정확히는 세타(1.618^N))</li></ul><h3>메모이제이션을 사용한 피보나치 함수 코드 (재귀)</h3><pre><code class="language-python"># 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): if x == 1 or x == 2: return 1 # 이미 계산된 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산되지 않았다면 점화식에 따라 피보나치 결과 반환 d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99)) </code></pre><p>바뀐 재귀 동작</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/541d21d1-7d00-4971-8248-a026450ac99b/Untitled.png" alt="Untitled"></p><ul><li>이로써 시간복잡도가 O(N)이 됨</li><li>호출 순서<ul><li>f(6) → f(5) → f(4) → f(3) → f(2) → f(1) → f(2) → f(3) → f(4)</li></ul></li></ul><h3>DP테이블을 사용한 피보나치 함수 코드 (반복)</h3><pre><code class="language-python"># 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1 d[1] = 1 d[2] = 1 n = 99 # 피보나치 함수 반복문으로 구현 (바텀업 다이나믹 프로그래밍) def fibo(n): for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] print(d[n]) </code></pre><h2>문제 풀이</h2><h3>1로 만들기</h3><p>정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지</p><ol><li>x가 5로 나누어 떨어지면, 5로 나눔</li><li>x가 3으로 나누어 떨어지면, 3으로 나눔</li><li>x가 2로 나누어 떨어지면, 2로 나눔</li><li>x에서 1을 뺌</li></ol><p>정수 x가 주어졌을 때, 연산 4개를 적절히 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하라.</p><p>입력 조건</p><ul><li>첫째 줄에 정수 X가 주어짐 (1 ≤ X ≤ 30,000)</li></ul><p>출력 조건</p><ul><li>첫째 줄에 연산을 하는 횟수의 최솟값을 출력</li></ul><p>입력 예시</p><pre><code class="language-python">26 </code></pre><p>출력 예시</p><pre><code class="language-python">3 </code></pre><p>코드</p><pre><code class="language-python">import sys input = sys.stdin.readline x = int(input()) # dp 테이블 d = [0] * (x + 1) # 다이나믹 프로그래밍 진행 (바텀업) for i in range(2, x + 1): # 현재 수에서 1을 빼는 경우 d[i] = d[i - 1] + 1 # 현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) # 현재의 수가 3으로 나누어 떨어지는 경우 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) # 현재의 수가 5로 나누어 떨어지는 경우 if i % 5 == 0: d[i] = min(d[i], d[i // 5] + 1) print(d[x]) </code></pre><p>문제 해결 방법</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/35ad379a-41c7-45ea-b858-6c12923cc7c0/Untitled.png" alt="Untitled"></p><h3>개미 전사</h3><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/136a4f8b-896e-4605-9426-2e2c712429e5/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1b881db7-be77-4342-b2c7-2fbcb89a36d2/Untitled.png" alt="Untitled"></p><p>코드</p><pre><code class="language-python">import sys input = sys.stdin.readline ''' 1. (i - 1)번째 식량창고를 털기로 결정한 경우 현재의 식량 창고를 털 수 없다 2. (i - 2)번째 식량창고를 털기로 결졍한 경우 현재의 식량 창고를 털 수 있다 ''' n = int(input()) k = list(map(int, input().split())) d = [0] * (n + 1) d[0], d[1] = k[0], max(k[0],k[1]) for i in range(2, n): d[i] = max(d[i - 1], d[i - 2] + k[i]) print(d[n-1]) </code></pre><p>문제 해결 방법</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f1e0d693-df51-4a71-9af4-86211c21d61f/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f41e6ce3-20b5-4a59-bb67-baf74192c58a/Untitled.png" alt="Untitled"></p><h3>바닥 공사</h3><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/987131f4-e435-4970-bd80-f6d74ba0e041/Untitled.png" alt="Untitled"></p><p>코드</p><pre><code class="language-python">import sys input = sys.stdin.readline ''' 1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 * 1 덮개를 하나 채우는 경우 존재 2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 * 2 덮개 2개는 넣는 경우, 혹은 2 * 2 덮개 하나를 넣는 경우 2가지 존재 ''' n = int(input()) d = [0] * (n + 1) d[1], d[2] = 1, 3 if n > 2: for i in range(3, n + 1): d[i] = d[i - 1] + (d[i - 2] * 2) print(d[n]%796796) </code></pre><p>문제 해결 방법</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f23f3350-e333-4acb-b019-0a0c74928c31/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/4c2fa216-c621-4bc8-84ef-0e1eb8e69d87/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/325e0286-3f07-48f6-bccc-8f4903428efd/Untitled.png" alt="Untitled"></p><h3>효율적인 화폐 구성</h3><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/73593d5d-cf23-4a7b-a000-1e483729308b/Untitled.png" alt="Untitled"></p><p>코드</p><pre><code class="language-python">import sys input = sys.stdin.readline ''' ai = 금액i를 만들 수 있는 최소한의 화폐 개수 k = 화폐의 단위 ai-k = (i - k)를 만들 수 있는 최소한의 화폐 개수 - ai-k를 만드는 방법이 존재하는 경우 : ai = min(ai, ai-k + 1) - ai-k를 만드는 방법이 존재하지 않는 경우 : ai = 10001 ''' n, m = map(int, input().split()) coins = [] for i in range(n): coins.append(int(input())) coins.sort() d = [10001] * (m + 1) d[0] = 0 for k in coins: for i in range(k, m + 1): d[i] = min(d[i], d[i - k] + 1) print(d[m]) if d[m] < 10001 else print(-1) </code></pre><p>문제 해결 방법</p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b7b39219-e096-4617-9e0f-35fb68a85987/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a9eb36b9-927a-4b8e-893d-be9a0ae34e36/Untitled.png" alt="Untitled"></p><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/e2b3ee6b-8824-4077-bfc5-4684bee68aa6/Untitled.png" alt="Untitled"></p><h2>금주의 문제</h2><p><a href="https://www.acmicpc.net/problem/11053">11053번: 가장 긴 증가하는 부분 수열</a></p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소