17. 동적 계획법

---

 

 

1. 배낭 문제 (Knapsack Problem)

무게와 가격이 다른 여러 물건 중, 가장 효율적으로 배낭을 채우는 방법을 찾아내는 문제.

 

---

 

2. 브루트 포스 검색법 (Brute Force Search)

모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법이다.

확실하게 가장 좋은 방법을 찾아낼 수 있지만 시간이 매우 오래 걸린다.

 

2.1) 브루트 포스 검색법으로 배낭 문제 해결하기

아무것도 넣지 않은 경우, 무게에는 문제가 없지만 이득도 없다.

보석을 1개씩 넣은 경우, 모든 경우가 최대 무게를 넘지 않으며, 금괴를 넣었을 때 이득이 가장 크다.

보석을 2개씩 넣은 경우, 수정 + 루비 조합을 제외하고는 모두 최대 무게를 초과하며, 가격은 14억으로 금괴 1개만 넣을 때보다 이득이 크다.

보석을 3개씩 넣은 경우, 모든 경우가 최대 무게를 넘는다.

보석 4개를 모두 넣은 경우, 모든 경우가 최대 무게를 넘는다.

이 중에서 최선의 방법은 수정과 루비를 넣어 14억을 취득하는 것이다.

 

2.2) 브루트 포스 검색법의 단점

데이터의 개수가 많아지면 고려해야 할 경우의 수는 기하급수적으로 늘어난다.

데이터의 개수가 n이라고 가정하면, 전체 경우의 수는 2^n 개다.

 

---

 

3. 탐욕 알고리즘 (Greedy Algorithm)

탐욕적으로 문제를 해결한다는 의미를 지닌다.

가장 이득이 되는 큰 데이터를 먼저 취하고, 그다음 이득이 큰 데이터를 취하는 방식으로 데이터를 선택한다.

 

3.1) 탐욕 알고리즘으로 배낭 문제 해결하기

가격이 가장 높은 금괴(6kg)를 배낭에 넣는다.

배낭 용량이 7kg이므로, 금괴를 넣을 수 있다.

금괴를 넣은 상태에서 다음 과정을 전개한다.

금괴 다음으로 가격이 높은 진주를 배낭에 넣을 경우, 배낭 무게를 초과한다.

진주 다음으로 가격이 높은 수정을 배낭에 넣을 경우, 배낭 무게를 초과한다.

수정 다음으로 가격이 높은 루비를 배낭에 넣을 경우, 배낭 무게를 초과한다.

더 이상 시도해볼 경우의 수가 없으므로, 금괴 1개를 넣은 배낭을 완성시킨다.

 

 

---

 

4. 브루트 포스 검색과 탐욕 알고리즘의 비교

브루트 포스 검색법은 모든 경우의 수를 다 확인하기 때문에 확실하고 최적의 결과를 도출할 수 있다.

탐욕 알고리즘은 최적의 결과는 얻지 못할 수 있지만, 적은 연산 횟수로 최선의 결과를 도출할 수 있다.

만약 보석이 40개인 경우, 브루트 포스 검색을 사용하려면 약 1조 가지 경우의 수를 연산해야 하지만, 탐욕 알고리즘을 사용하면 40회 연산을 13억(금괴 1개)을 도출할 수 있다.

배낭 문제를 예시로 보면 브루트 포스 방식보다는 손해이지만, 탐색 시간에 있어서는 비교할 수 없을 만큼 빠르다.

 

---

 

5. 동적 계획법 (Dynamic Programming)

불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘.

최적 부분 구조(Optimal Substructure)란, 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조를 의미한다.

큰 문제를 작은 문제로 단순화한 후 재귀적인 호출을 활용하여 문제를 해결한다.

재귀 함수의 중복 호출 문제를 해결하기 위해 메모이제이션(Memoization) 프로그래밍 기법을 사용한다.

 

5.1) 메모이제이션 배열

행: 배낭에 넣은 보석의 최대 개수로, 0~4개이다.

열: 배낭에 담을 수 있는 최대 무게로, 0~7kg이다.

노란색 영역: 보석을 넣었을 때 배낭에 들어있는 최대 가격이다.

배열 초기화: 보석 개수가 0개인 행과 배낭 무게가 0인 열을 0으로 초기화한다.
(제시한 문제를 가장 작은 문제로 쪼개면 배낭은 0kg, 보석은 없음에서 문제가 시작됨)

 

5.2) 보석(금괴)이 1개일 경우

1kg 배낭에 6kg 금괴를 담을 수 없다.

바로 윗행의 결과를 가져온다.

2~5kg 배낭에도 6kg 금괴를 넣을 수 없으므로, 바로 윗행의 결과를 가져온다.

6kg 배낭을 사용할 경우, 금괴 1개를 담을 수 있다.

만약 금괴 1개를 담은 상태에서 여유분에 추가로 보석을 넣을 수 있다면 더 큰 이익을 낼 수 있을 것이다.

7kg 배낭에는 금괴를 넣을 수 있다.

배낭의 여유분에 해당하는 0원을 합산하여 보석을 넣지 않은 7kg 배낭과 비교해서 더 높은 값을 채운다.

 

5.3) 보석(금괴, 수정)이 2개일 경우

1~3kg 배낭에는 4kg 수정을 넣을 수 없다.

바로 윗행의 결과를 가져온다.

4kg 배낭에는 4kg 수정을 넣을 수 있다.

수정 가격에 여유분 0원을 합산한 후, 바로 윗행의 결과와 비교하여 더 높은 8억을 저장한다.

 

5.4) 동적 계획법 동작 과정

위와 같은 과정을 거쳐서 마지막 행/열에 대입되는 값은 최상의 이익을 가지는 값으로, 14억이 된다.

 

---

 

6. 황금 미로 문제

황금이 있는 미로의 왼쪽 상단 입구에서 출발하여 오른쪽 하단 출구로 나가면서 가장 많은 황금을 가지고 지나는 방법.

 

6.1) 황금 미로 문제의 동적 계획법 풀이

황금 미로를 2차원 배열로 작성한다.

미로를 이동하면서 누적된 황금 개수를 채우기 위한 메모이제이션 배열을 작성한다.

황금 미로 값 [0][0] 위치부터 누적하여 첫 행(0행)을 채운다.

황금 미로 값 [0][0] 위치부터 누적하여 첫 열(0열)을 채운다.

0행 1열의 원소와 1행 0열의 원소 중 큰 값을 골라서 황금 미로 값과 합계를 계산한다.

2~4행도 동일한 방법을 반복하여 수행한다.

 

---

 

---

수고하셨습니다!

---