🧐 coding interview/🧠 concept

[PS] Dynamic programming : 동적 프로그래밍

dev!n 2023. 2. 15. 20:23

한 번 해결된 부분 문제의 정답을 메모리에 기록하여 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법. 다이나믹 프로그래밍은 점화식을 그대로 코드로 옮겨서 구현할 수 있다. 점화식이란 인접한 항들 사이의 관계식을 의미한다.

조건

  1. 최적 부분 구조(Optional substructure)
    큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
  2. 중복되는 부분 문제(Overlapping Subproblem)
    동일한 작은 문제를 반복적으로 해결해야 함

예시

(문제 링크 추가 예정)

다이나믹 프로그래밍을 이용한 소스코드를 작성하는 방법 두가지

1. Top-down : 메모이제이션 (Memoization)

재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

2. Bottom-up

단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

 

다이나믹 프로그래밍 문제에 접근하는 방법

  1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
  2. 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
  3. 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려
  4. 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다
  5. 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다

다이나믹 프로그래밍 vs 분할 정복

  • 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
    • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
  • 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
    • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
    • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음
  • 분할 정복의 대표적인 예시인 퀵 정렬을 살펴보자.
    • 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
    • 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음

 

참고 

'🧐 coding interview/🧠 concept'의 다른글

  • 현재글[PS] Dynamic programming : 동적 프로그래밍
댓글

티스토리툴바