[Python] 이것이 코딩테스트다 8장 다이나믹 프로그래밍

다이나믹 프로그래밍의 핵심

 

 

🔑 수열의 점화식을 구하는 것이 핵심! 

중복되는 연산을 줄이자. 연산 속도와 메모리공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성

현재의 항들로 다음 항을 구할 수 있는 경우 다이나믹 프로그래밍을 쓴다.

 

 

대표적 예시 >> 피보나치 수열

 

• 재귀 함수(탑다운 방식)

구현하긴 간편하지만 숫자가 커지면 기하급수적으로 연산횟수가 늘어난다. 

f(100)을 구하기 위해서는 약 1,000,000,000,000,000,000,000,000,000,000번 연산을 해야한다. 시간으로 따지면 수백억년이 넘어가는 시간이 걸림.

 

• 다이나믹 프로그래밍 (보텀업 방식)

하지만 다이나믹으로 풀 경우, 같은 문제라면 한번 씩만 풀어 저장해 놓기 때문에 효율적으로 해결하게 된다. O(N)의 성질을 보임.

 

다이나믹 프로그래밍을 이용하여 피보나치 수열 문제를 풀었던 방법을 잘 알아두면 다른 다이나믹 프로그래밍 문제에 접근 하는 방법 또한 떠올릴 수 있다.

 

수열은 배열이나 리스트, 딕셔너리로 표현하여 이용할 수 있다. 

 

 

 

코딩 테스트

코딩 테스트에서 다이나믹 프로그래밍은 비교적 간단한 형태. 물론 3차원 리스트를 이용하여야 하는 복잡한 난이도의 문제가 출제될 수도 있다.(최단경로, 플로이드)

 

 

• 메모이제이션: 엄밀히 말하면 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념 . 탑다운에 사용되는 표현
• 다이나믹 프로그래밍: 보텀업방식을 사용하여 사용되는 결과를 DP테이블에 기록해 놓은것.

---

----------------------------------시간제한 참고

파이썬 => 1초 20000000번 연산

 

데이터 20,000,000 => O(N)

데이터 1,000,000 => O(NlogN)

데이터 4~5,000 => O(N^2)

---

다이나믹 프로그래밍 예제

 

📝 체감난이도 : ★☆☆☆☆

 

 

 

🎨 피보나치 수열 : 재귀

 

 

 

 

🎨 피보나치 수열 : 다이나믹 이용한 재귀

 

 

 

 

🎨 피보나치 수열 : 다이나믹 이용한 반복문

 

 

 

 

🔑 Key Point 

 

다이나믹을 이용할 때에는 배열에 바텀에서부터 계산한 결과를 저장해두어, 이미 계산된 결과라면 함수를 탈출하게 하는 if문을 하나 더 두었다.

 

 

 

---

1로 만들기

시간제한 1초 . 데이터 30,000개 

 

📝 체감 난이도 : ★★★☆☆

 

 

🎨 내가 짠 코드 (이진 탐색)

 

 

 

 

 

 

🔑 Key Point 

 

• 그리디 문제로 풀 수 없는 이유

이 문제를 처음 보면 그리디 방법을 생각 할 것.

하지만 그리디가 만족하려면 각각의 수가 배수관계에 있어야하는데 주어진 수는 5,3,2로,

그리디를 이용한다면 모든 경우에 대하여 최적의 해를 보장할 수 없다.

 

따라서, 다이나믹 프로그래밍 접근법을 의심해 보아야 한다.\

 

• 핵심 점화식

 

A(i) = min ( A(i-1)+1, A(i/2)+1, A(i/3)+1, A(i/5)+1)

A(i) = min ( A(i-1), A(i/2), A(i/3), A(i/5))+1

 

+1 을 해주는 이유는 이전 항을 정보를 가져올때 한번 연산이 수행되기 때문이다. 그리고 1은 공통적으로 더해주는 덧셈이기 때문에 min함수에서 뺄 수 있다. 

 

위의 점화식을 이용하여 2부터 (바텀에서부터) 반복하여 DP테이블을 목적지 까지 채우면 된다. 

 

 

---

개미 전사

시간제한 1초 . 데이터 100개 

 

 

체감 난이도 : ★★★☆☆

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

 

점화식으로 푼다고 생각이 들었으면 

왼쪽부터 차례대로 식량창고를 턴다고 생각하면 어렵지 않게 점화식을 세울수 있다

 

A[i] = max(A[i-1], A[i-2] + k(i))

 

처음 두가지 경우는 우선 dp테이블에 채워둔 뒤 2일때부터(바텀부터) 위의 점화식을 적용하여 목적지까지 채우면 쉽게 구할 수 있다.

 

코드는 매우 쉬운데, 점화식을 생각해 내는 것이 어려운 편이다.

 

---

바닥 공사

시간제한 1초 . 데이터 1000개 

 

 

 

체감 난이도 : ★★★☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

 

 

A[i] = A[i-1] + A[i-2] * 2

 

역시나 점화식 생각하기가 어려운 문제 

타일 문제는 다이나믹 프로그래밍 중 대표적 기본문제라고 하니, 생각이 나지 않는다면 그림을 그려보아야 한다

 

A[0] = 0

A[1] = 1

A[2] = 3

으로 초기 설정 한 뒤, 3부터 위의 점화식을 반복하여, 구하고자 하는 목적지까지 채워주면 된다.

---

효율적인 화폐 구성

시간제한 1초. N = 100개, M =1000개

 

 

체감 난이도 : ★★★☆☆

 

🎨 내가 짠 코드

 

 

 

🔑 Key Point 

 

주어진 화폐를 가지고 목적 화폐를 구성할 수도 있고 구성하지 못할 수도 있다. 화폐가 배수 관계가 아닐 수 있기 때문에 그리디 보단 다이나믹을 떠올려야하며,

 

바텀업으로 dp테이블을 채워나간다.

 

배열을 초기에 10,001로 초기해 놓는다( 10,000까지 나올수 있다 했으므로)

 

핵심 점화식

 

A[i] = min(A[i], A[i - coins[j]] +1) 

 

 

---

마무리

 

다이나믹은 점화식이 넘 어렵다. 

자꾸 수학때 생각이 나서 계산을 하려하는데 , 계산은 컴퓨터가 해주므로 우리는 점화식만 세우면 된다 

연습이 필요한 부분 같다