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

이번에는 Chapter8 다이나믹 프로그래밍을 공부할 차례다. 다이나믹 프로그래밍은 연산 속도 한계 및 메모리 공간 한정이라는 컴퓨터의 제약 사항들을 극복하고자 하는 기법이다. 동적 계획법이라고도 하며 탑다운과 보텀업 2가지 방식이 존재한다. 해당 방식 모두 공부하고 마지막으로는 다이나믹 프로그래밍에 자주 사용되는 메모이제이션 기법까지 공부한다. 

 

※ 주의할점

다이나믹 프로그래밍과 동적 할당의 다이나믹은 다른 의미임.

 

 

 

1. 중복되는 연산을 줄이자

---

- 다이나믹 프로그래밍(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (출처 : 위키백과)

• 수열 시간 복잡도 O(N)
• Top-Down(메모이제이션, 하향식) 방식 : 큰 문제를 해결하기 위해 작은 문제 호출(재귀)
  • 다이나믹 프로그래밍과 메모이제이션의 개념 혼용해서 사용하는 경우가 있음.
  • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미 => 다이나믹 프로그래밍과는 별도의 개념.
• Bottom-Up(상향식) 방식 : 단순히 반복문을 이용하여 소스코드 작성 시 작은 문제부터 차근차근 답을 도출
  • 다이나믹 프로그래밍의 전형적인 형태
  • 결과 저장용 리스트 = DP 테이블
  • 리스트 뿐마 아니라 사전(dict)자료형으로도 DP 테이블 생성 가능

 

- 다이나믹 프로그래밍 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

- 메모이제이션(Memoization) 기법

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미
• 값을 저장하는 방법으로 캐싱(Cashing 이라고도 함)

 

- 다이나믹 프로그램으로 해결할 수 있는 대표적인 예 => 피보나치 수열

• 기존 피보나치 : 동일한 함수가 반복적으로 호출됨. ex) f(3)이 3번이나 호출됨.

 

• 다이나믹 프로그래밍 적용한 피보나치 : 메모이제이션을 통해 한 번 실행한 함수의 결과값을 저장해 놓았기 때문에 각각의 함수가 1번씩만 실행됨. => 결과적으로 색칠한 노드만 실행됨

 

 

- 문제 파악법 및 주의사항

 

• 한 번 해결했던 문제를 다시금 해결해야하는 문제
• 재귀 함수 대신 반복문을 사용하여 오버헤드를 줄일 수 있음
• 일반적으로 반복문을 이용한(보텀업) 다이나믹 프로그래밍이 성능이 더 좋음
• 대체로 간단한 형태로 출제됨
• 특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 적용할 수 있는지 고민 and 해결하고자 하는 부분 문제들의 중복 여부를 확인 할 것
• 만약 탑다운 방식의 다이나믹 프로그래밍에서 재귀함수를 사용할 경우 recursion depth와 관련 오류 발생할 수 있음 => sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출해 재귀 제한을 완화할 수 있단 점 기억할 것!

 

 

 

2. 다이나믹 프로그래밍 알고리즘 문제

---

- 실전문제 1로 만들기

- 실전문제 개미 전사

- 실전문제 바닥 공사

- 실전문제 효율적인 화폐 구성

- Q 31  금광

- Q 32  정수 삼각형

- Q 33  퇴사

- Q 34  병사 배치하기

- Q 35  못생긴 수

- Q 36  편집 거리