[크래프톤 정글 5기] week03 알고리즘 주차 열다섯번째 날, DP, 그리디, LCS

DP(Dynamic Programming, 동적 계획법)

- 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다.

- DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다.

- “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용”

- DP라는 이름은 그냥 멋있어 보여서 지은 이름이다.

 

DP를 쓰는 이유

- 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다.

--->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다.

--->>> fibo(6)를 실행했을 때 반복적으로 실행되는 fi(4), fi(3) 등의 값을 리스트에 미리 저장해 둔다. 그리고 이미 계산된 함수가 다시 호출되면 리스트에서 값을 꺼내 쓴다. 이렇게 연산횟수를 획기적으로 줄일 수 있다.

 

DP의 사용 조건

1. Overlapping Subproblems(겹치는 부분 문제)

2. Optimal Substructure(최적 부분 구조)

 

Overlapping Subproblems(겹치는 부분 문제)

- DP는 문제를 나누고, 그 결과 값들을 재활용해 전체 값을 구한다.

- 따라서 동일한(해결로직이 같은) 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다.

 

Optimal Substructure(최적 부분 구조)

- “부분 문제의 최적 결과 값”을 이용해, “전체 문제의 최적 결과”를 낼 수 있는 경우

 

최적 부분 구조 예시

 

- 위 그림에서 A -> B의 최단 경로를 찾으려고 한다. 만약 경로 중에서 AX2와 BX2가 가장 짧은 경로라면, A -> B의 최단 경로도 AX2 - BX2 이다.

- 이렇게 부분 문제에서 구한 최적 결과가 전체 문제의 정답으로 이루어진다면 DP를 사용할 수 있다.

 

DP와 분할 정복의 차이점

- DP에서 문제를 분할하면, 각 문제는 같은 논리로직을 가져야 한다. ex ) 피보나치, fi(6)과 fi(5), fi(4)는 입력값만 다르고 동일한 논리구조

DP ::: 1+2+3+4 -> (1+2)+(3+4) 이렇게 문제를 분할해도 둘다 덧셈 연산이므로 논리가 동일하다.

분할 정복 ::: 1*2+3/4 -> (1*2)+(3/4) 이렇게 문제를 분할했더니 두 문제의 해결방법이 다르다.

 

점화식 : 인접한 항들 사이의 관계식

 

메모이제이션(Memoization)

- 한 번 구한 결과를 어딘가에(리스트, 딕셔너리 등) 저장해두고, 같은 식을 호출하면 저장한 값을 그대로 가져오는 기법. 캐싱(Caching)이라고도 한다.

- 한 번 구한 정보를 리스트에 저장함으로써 메모이제이션을 구현할 수 있다. ( 때에 따라 딕셔너리 등을 사용할 수도 있음 )

- 메모이제이션은 “탑다운 방식에 국한”되어 사용되는 표현이다. 바텀업 방식에서는 “DP테이블” 이라고 한다.

- 메모"이"제이션 이다.

 

DP, 탑다운 방식(Top-Down, 하향식)

- 재귀 함수를 이용하여 DP코드를 작성하는 방법

- 큰 문제부터 작은 문제로 나눠가며 답을 도출해 간다

 

DP, 바텀업 방식(Bottom-Up, 상향식)

- 반복문을 이용하여 DP코드를 작성하는 방법

- 작은 문제부터 차근차근 답을 도출해 간다

- 바텀업 방식에서 사용되는 결과 저장용 리스트는 “DP테이블” 이라고 한다.

 

그리디 알고리즘(Greedy Algorithm, 탐욕법)

- 각 단계에서 항상 최적이라고 생각되는 것을 선택하며 진행하여, 최종적인 해답에 도달하는 알고리즘

- 항상 최적의 값을 “보장”하진 않고 최적의 값의 “근사한 값”을 목표로 한다.

- 주로 문제를 분할하여 분할한 문제들에 대한 최적해를 구하고, 이를 결합해 전체 문제의 최적해를 구한다.

 

그리디 알고리즘을 사용하기 위한 두가지 조건

탐욕 선택 속성(Greedy Choice Property)

- 각 단계에서 "항상 최선의 선택”을 했을 때, 전체 문제에 대한 최적해를 구할 수 있어야 한다.

 

최적 부분 구조(Optimal Substructure)

- 부분 문제의 최적해를 모아 전체 문제의 최적해가 될 수 있어야 한다.

 

LCS(Longest Common Subsequence / String, 최장 부분 수열 / 문자열)

- Subsequence, Substring 모두 LCS 라고 한다.

- LCS를 구하는 것이, DP로 해결할 수 있는 문제이자 알고리즘이다.

- 공통 부분 문자열 중 "가장 길이가 긴" 문자열

- Substring(부분 문자열) 또는 Subsequence(부분 수열)를 구하는 것이다.

- 두 수열/문자열에서 0개 이상의 문자를 빼서 이어 붙였을 때 나올 수 있는 가장 긴 문자열

 

Substring : 전체 문자열에서 연속된 부분 문자열

ex) ABCDEFGHI 에서 Substring은 ABC, DEFG, ABCDEF, GHI, … 등이 있다.

 

Subsequence : 전체 문자열에서 꼭 연속된 문자열인 것은 아닌 부분 문자열

ex) ABCDEFGHI 에서 Subsequence 는 ABD, AEFGH, AFI, … 등이 있다.

(단, 앞에서부터가 아니라 순서가 뒤바뀐 IHE, BIDEHF 와 같은 문자열은 부분 문자열이 될 수 없다)

 

공통 부분 문자열 중, “가장 길이가 긴” 부분 문자열을 찾는다.

ex) ABCDEF 와 ACDGHI 와의 공통 Subsequence 중 가장 길이가 긴 것은

ABCDEF / AZGCDGHI 에서 ACD 이다.

 

## 수열, 문자열은 그냥 표현하는 말이고, 숫자형태든 문자열 형태든 Substring 또는 Subsequence의 규칙을 따른다는 것만 기억하자.