알고리즘

Dynamic Programming #1

강원대학교 컴퓨터공학과 최우혁

지난 시간에…

• 행렬 곱셈Matrix Multiplication
• 분할: n × n 크기의 행렬 A, B를 각각 n / 2 ⨉ n / 2 크기의 부분 행렬 4개로 분할
• 정복: 부분 행렬간의 곱을 구한 후 더함

​

2

지난 시간에…

• 점화식의 점근적 복잡도Asymptotic Complexity
• 입력 크기를 정수의 거듭제곱으로 구한 점근적 복잡도가 유연하다면, 입력 크기를 일반적으로 두고 구한 점근적 복잡도와 같음
• 마스터 정리

​

3

지난 시간에…

• 분할 정복 적용 시 고려사항
• 큰 문제가 상수 개의 충분히 작은 문제로 분할되지 않는다면 분할 정복을 하지 않는 것이 좋음

4

강의 순서

• 동적 계획법?
• 이항 계수Binomial Coefficient
• 최장 길이 공통 부분열Longest Common Subsequence
• 연쇄 행렬 곱셈Matrix-Chain Multiplication

5

이번 시간에…

• 동적 계획법?
• 동적 계획법의 어원, 특징 및 문제 해결 절차 등을 소개
• 이항 계수Binomial Coefficient
• 이항 계수를 구하는 분할 정복 및 동적 계획법 알고리즘을 설계 및 분석
• 최장 길이 공통 부분열Longest Common Subsequence
• 연쇄 행렬 곱셈Matrix-Chain Multiplication

6

동적 계획법?

7

어원

동적 계획법?

• 응용수학자 Richard Ernest Bellman이 고안한 수학, 컴퓨터 과학, 경제학 분야의 문제 해결 방법

​

​

8

나는 RAND에서 1950년의 가을을 보냈다. 여기에서 내게 주어진 첫 과제는 다단계Multi-stage 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다. '동적 계획법'이라는 이름이 어디에서 왔는지 궁금하지 않은가? 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다. 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다. 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다. 사람들이 그 앞에서 연구라는 단어를 쓰면 그는 완전히 미치다시피 했다. 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장 이었다. 그래서, 나는 윌슨과 공군으로부터 내가 수학을 연구하고 있다는 사실을 숨길 필요가 있었다. 어떤 단어를 선택해야 했을까? 처음에는 Planning. Decision Making, Thinking 등의 단어를 고려했었다. 하지만, 몇 가지 이유로 해당 단어들이 좋은 선택이 아님을 깨달았고, 대신 사람들이 알지 못하게 Programming이라는 단어를 선택했다. 또한 나는 이 방법이 다단계Multi-stage로 이루어져 있고, 시가변적Time-varying이며, 동적Dynamic이라는 개념이 전달되길 원했다. 특히, 동적Dynamic이라는 형용사는 어떤 단어와 조합해도 긍정적인 의미가 있다고 생각했다. 그래서, 동적 계획법Dynamic Programming이 좋은 이름이라고 생각했으며, 내가 하는 연구를 윌슨과 공군으로부터 숨기는 데 사용했다.

​

- Richard E. Bellman의 자서전, 태풍의 눈Eyes of Hurricane 중

Richard Ernest Bellman, 응용수학자

동적 계획법Dynamic Programming, 벨만 방정식Bellman Equation, 차원의 저주Curse of Dimensionality 등을 제시

어원

동적 계획법?

• 어원에서는 Dynamic과 (Computer) Programming과는 큰 관련이 없음
• 하지만, 후에 동적 시스템Dynamical System을 최적화하기 위한 최적 제어 기법Optimal Control에서 동적 계획법을 활용
• 동적 시스템: 현재 시점의 출력값이 현재 시점의 입력값 뿐 아니라 과거 시점의 입력값들의 영향을 받는 시스템
• 궁금하시면 다음 해 가을 학기에 제 인공지능 수업을…

9

Richard Ernest Bellman, 응용수학자

동적 계획법Dynamic Programming, 벨만 방정식Bellman Equation, 차원의 저주Curse of Dimensionality 등을 제시

특징

동적 계획법?

• 큰 문제를 작은 문제로 분할
• 작은 문제를 해결하여 테이블 또는 변수 등에 저장
• 저장된 작은 문제의 해답을 합쳐서 큰 문제의 해답을 계산하는 재귀 관계식Recursive Property를 정의
• 분할 정복의 점화식Recurrence Relation은 알고리즘의 복잡도를 표현
• 동적 계획법의 재귀 관계식Recursive Property은 문제의 해답을 계산

10

Memoization vs. Tabulation

동적 계획법?

• Memoization
• 하향식Top-Down: 큰 문제를 그보다 조금 작은 문제로 분할하여 해결
• 보통, 재귀 알고리즘으로 구현됨
• Tabulation
• 상향식Bottom-Up: 가장 작은 문제의 해답을 통합하여 그보다 더 큰 문제를 해결
• 보통, 반복 알고리즘으로 구현됨

11

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 분할 정복

12

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 분할 정복
• 큰 피보나치 수를 좀 더 작은 피보나치 수로 나눠서 계산

13

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 분할 정복
• 큰 피보나치 수를 좀 더 작은 피보나치 수로 나눠서 계산
• 시간 복잡도: Ω(√2ⁿ)
• 공간 복잡도: Θ(1)

14

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Memoization

​

15

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Memoization
• 분할 정복과 유사하게 큰 피보나치 수를 좀 더 작은 피보나치 수로 나눠서 계산

​

16

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Memoization
• 분할 정복과 유사하게 큰 피보나치 수를 좀 더 작은 피보나치 수로 나눠서 계산
• 피보나치 수를 저장/재사용하는 캐쉬 C를 활용

17

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Memoization
• 분할 정복과 유사하게 큰 피보나치 수를 좀 더 작은 피보나치 수로 나눠서 계산
• 피보나치 수를 저장/재사용하는 캐쉬 C를 활용
• 시간 복잡도: Θ(n)
• 공간 복잡도: Θ(n)

18

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Divide & Conquer
• 이미 계산한 피보나치 수를 중복해서 계산

• Memoization
• 이미 계산한 피보나치 수는 저장하고 재사용

19

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Tabulation

​

20

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Tabulation
• 가장 작은 피보나치 수부터 점차 큰 피보나치 수로 차례대로 계산

​

21

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Tabulation
• 가장 작은 피보나치 수부터 점차 큰 피보나치 수로 차례대로 계산
• 피보나치 수를 저장하는 위한 배열 C를 활용

​

22

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• Tabulation
• 가장 작은 피보나치 수부터 점차 큰 피보나치 수로 차례대로 계산
• 피보나치 수를 저장하는 위한 배열 C를 활용
• 시간 복잡도: Θ(n)
• 공간 복잡도: Θ(n)

23

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 개선된 Tabulation

24

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 개선된 Tabulation
• 모든 피보나치 수를 저장하는 대신, n - 1, n - 2 번째의 피보나치 수만 유지

25

Memoization vs. Tabulation: 예. 피보나치 수

동적 계획법?

• 개선된 Tabulation
• 모든 피보나치 수를 저장하는 대신, n - 1, n - 2 번째의 피보나치 수만 유지
• 시간 복잡도: Θ(n)
• 공간 복잡도: Θ(1)

26

Memoization vs. Tabulation: Pros & Cons

동적 계획법?

• Memoization은 상당 부분 분할 정복과 유사하므로, 이 수업에서는 Tabulation에 집중

27

최적 부분 구조: 예

동적 계획법?

• 서울에서 출발해 부산까지 가는 최단 경로의 길이

28

최적 부분 구조: 예

동적 계획법?

• 서울에서 출발해 부산까지 가는 최단 경로의 길이
• 서울에서 출발해 대구까지 가는 최단 경로의 길이

​

29

최적 부분 구조Optimal Substructure

동적 계획법?

• 큰 문제에 대한 최적의 해답이 큰 문제를 분할한 작은 문제에 대한 최적의 해답을 포함
• 동적 계획법은 최적 부분 구조를 만족하는 최적화 문제Optimization Problem를 해결하는데 활용
• 최적화 문제: 여러 해답들 중 주어진 조건을 만족하는 최적의 해답을 찾는 문제
• 예. 전쌍 최단 경로 문제All-Pairs Shortest Path Problem: 한 지점에서 다른 지점까지 가는 최단 경로의 거리를 찾기
• 예. 연쇄 행렬 곱셈Matrix-Chain Multiplication: 여러 개의 행렬을 곱할 때 최소의 원소 단위 곱셈의 횟수를 찾기

30

최적 부분 구조: 예

동적 계획법?

• 서울에서 출발해 부산까지 가는 최단 경로의 길이
• 서울에서 출발해 대구까지 가는 최단 경로의 길이
• 대구에서 출발해 부산까지 가는 최단 경로의 길이

31

최적 부분 구조: 예

동적 계획법?

• 큰 문제: 서울에서 출발해 부산까지 가는 최단 경로의 길이
• 작은 문제 1: 서울에서 출발해 대구까지 가는 최단 경로의 길이
• 작은 문제 2: 대구에서 출발해 부산까지 가는 최단 경로의 길이

32

최적 부분 구조와 동적 계획법

동적 계획법?

• 큰 문제를 작은 문제로 분할
• 작은 문제에 대한 최적의 해답을 테이블 또는 변수 등에 저장
• 저장된 작은 문제의 최적의 해답을 합쳐서 큰 문제의 최적의 해답을 계산하는 재귀 관계식Recursive Property를 정의

33

분할 정복 vs. 동적 계획법

동적 계획법?

• 분할 정복: 하향식Top-down 접근 방법
• 큰 문제를 작은 문제로 나눠서 해결한 후에 필요한 경우 합침
• 나눠진 문제들 간에 관계가 없거나 적은 경우에 유용
• 예. 합병 정렬: 각 부분 배열만 정렬하면 됨
• 동적 계획법(w/ Tabulation): 상향식Bottom-up
• 큰 문제를 작은 문제로 나눈 후, 작은 문제의 해답을 저장/재사용해서 큰 문제의 해답으로 합침
• 나눠진 문제들 간에 관계가 뚜렷한 경우에 유용
• 예. 피보나치 수열: 작은 문제의 답이 보다 큰 문제를 해결하기 위해 재사용되어야 함

34

코딩 테스트와 동적 계획법

동적 계획법?

• 코딩 테스트 문제에서 분할 정복과 동적 계획법 둘 다 적용 가능한 문제는 보통 동적 계획법이 훨씬 빠르게 문제를 해결할 수 있음
• 동적 계획법이 아니라면 제 시간에 풀 수 없도록 의도한 문제도 많음
• 하지만, 동적 계획법을 적용하기 위한 재귀 관계식을 세우는 것은 충분한 경험이 없다면 쉬운 일이 아님
• 동적 계획법을 사용해야 하는 문제들을 많이 풀어 보는 수 밖에 없다고…

35

이항 계수Binomial Coefficient

36

이항 계수?

이항 계수Binomial Coefficient

• 주어진 n개의 원소 중에서 k개의 원소를 순서 없이 선택하는 방법의 수( = 조합Combinations)

​

​

​

​

37

이항 계수?

이항 계수Binomial Coefficient

• 예. 10명으로 구성된 팀에서 경기에 나갈 선수 5명을 선발하는 방법
• 10명 중에서 5명을 순서와 상관없이 선발
• 따라서, 10개의 원소 중 5개로 원소를 뽑는 조합의 수를 구하는 문제

38

문제 정의

이항 계수Binomial Coefficient

• 이항 계수 C(n, k)를 계산하라
• 입력: 양의 정수 n, k
• 출력: 이항 계수 C(n, k)

​

​

39

재귀 관계식

이항 계수Binomial Coefficient

• 동적 계획법을 적용하기 위해서는 큰 문제의 해답을 그보다 작은 문제의 해답으로 표현할 수 있는 재귀 관계식을 세워야 함

40

재귀 관계식

이항 계수Binomial Coefficient

• 동적 계획법을 적용하기 위해서는 큰 문제의 해답을 그보다 작은 문제의 해답으로 표현할 수 있는 재귀 관계식을 세워야 함

41

분할 정복 알고리즘: 의사 코드

이항 계수Binomial Coefficient

• 재귀 관계식을 그대로 옮긴 형태

42

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 분할 정복으로 구현한 이항 계수 알고리즘은 피보나치 수열의 분할 정복 알고리즘과 동일한 문제가 있음
• 한 문제가 비슷한 크기의 문제 두 개로 분할

43

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 분할 정복으로 구현한 이항 계수 알고리즘은 피보나치 수열의 분할 정복 알고리즘과 동일한 문제가 있음
• 한 문제가 비슷한 크기의 문제 두 개로 분할
• 이미 계산한 이항 계수를 중복하여 계산

44

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 입력 크기: n, k
• 단위 연산: 덧셈

​

​

45

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• T(n, k): C(n, k)를 계산하기 위해 필요한 덧셈의 횟수

​

​

​

46

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• T(n, k): C(n, k)를 계산하기 위해 필요한 덧셈의 횟수
• C(n-1, k-1)과 C(n-1, k) 계산에 필요한 덧셈 횟수: T(n-1, k-1) + T(n-1, k)

​

47

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• T(n, k): C(n, k)를 계산하기 위해 필요한 덧셈의 횟수
• C(n-1, k-1)과 C(n-1, k) 계산에 필요한 덧셈 횟수: T(n-1, k-1) + T(n-1, k)
• C(n-1, k-1)과 C(n-1, k)를 더하는 횟수: 1회

​

​

48

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 입력이 n이외에도 k에 의존적이라 점화식의 해를 구하기는 까다로움
• 하지만, (1) 한 번의 호출에서 k가 1만큼 감소, (2) k가 0이 될 때까지 2번씩 호출함을 보았을 때, 대략 O(2^k) 정도가 될 것으로 예상됨
• k는 n만큼 커질 수 있으므로 아마도 O(2ⁿ)?

49

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 실제 복잡도: T(n) = 2C(n, k) - 1

​

50

분할 정복 알고리즘: 분석

이항 계수Binomial Coefficient

• 실제 복잡도: T(n) = 2C(n, k) - 1

​

51

동적 계획법 알고리즘: 아이디어

이항 계수Binomial Coefficient

• 2차원 배열 B를 만들고, C(i, j)의 결과를 B[i][j]에 저장

​

​

• 작은 입력 (즉, B[1][0])부터 차례대로 계산해서, 최종적으로 B[n][k]를 계산

52

동적 계획법 알고리즘: 의사 코드

이항 계수Binomial Coefficient

53

이항 계수 C(n, k)에서 k ≤ n 이므로,

현재 구하려는 C(i, k)에서 k ≤ i 여야 함

동적 계획법 알고리즘: 분석 - 시간 복잡도

이항 계수Binomial Coefficient

• 입력 크기: n, k
• 단위 연산: B[i][j]에 연산 결과를 저장
• 즉, for-j 루프의실행 횟수

​

54

동적 계획법 알고리즘: 분석 - 시간 복잡도

이항 계수Binomial Coefficient

55

동적 계획법 알고리즘: 분석 - 시간 복잡도

이항 계수Binomial Coefficient

56

동적 계획법 알고리즘: 분석 - 시간 복잡도

이항 계수Binomial Coefficient

57

동적 계획법 알고리즘: 분석 - 시간 복잡도

이항 계수Binomial Coefficient

58

동적 계획법 알고리즘: 분석 - 공간 복잡도

이항 계수Binomial Coefficient

• n ⨉ (k + 1) 크기의 2차원 배열에 결과를 저장 ∈ Θ(nk)

​

59

공간 복잡도의 개선

이항 계수Binomial Coefficient

60

공간 복잡도의 개선

이항 계수Binomial Coefficient

61

공간 복잡도의 개선

이항 계수Binomial Coefficient

62

공간 복잡도의 개선

이항 계수Binomial Coefficient

63

공간 복잡도의 개선

이항 계수Binomial Coefficient

64

공간 복잡도의 개선

이항 계수Binomial Coefficient

• B[i][j]를 계산하기 위해서는, B[i-1][j], B[i-1][j-1]의 값만 필요
• B[i-2], B[i-3] 등에 존재하는 이항 계수의 값은 필요하지 않음
• 따라서, B[i-1]에 존재하는 이항 계수의 값을 저장하는 길이 k + 1의 1차원 배열만으로도 설계 가능
• 즉, 공간 복잡도 Θ(k)

65

공간 복잡도의 개선: 아이디어

이항 계수Binomial Coefficient

• 1차원 배열 B를 만들고, C(i, j)의 결과를 B[j]에 저장

​

​

​

• 그럴싸해 보이지만, 사실 심각한 문제가 있음

66

공간 복잡도의 개선: 아이디어

이항 계수Binomial Coefficient

• j 의 값을 0부터 min(i, k) 까지 증가시키면서 이항 계수를 계산할 시, B[j] 계산에 이미 업데이트가 된 B[j-1] 값이 사용됨

​

​

​

67

공간 복잡도의 개선: 아이디어

이항 계수Binomial Coefficient

• j 의 값을 min(i, k) 부터 0까지 감소시키면서 이항 계수를 계산할 시에는 정상적으로 작동

​

​

​

68

공간 복잡도의 개선: 의사 코드

이항 계수Binomial Coefficient

​

​

​

69

j의 값을 감소시키면서

이항 계수를 계산

공간 복잡도의 개선: 제언

이항 계수Binomial Coefficient

• 이처럼, Tabulation을 활용한 동적 계획법은 공간 복잡도를 최적화 할 수 있는 경우가 존재
• 처음부터 공간 복잡도를 최적화한 설계를 생각해내는 건 어려움
• 초기 설계에서는 최적화를 생각하지 말고, 일단 문제 해결에만 집중
• 이후에 최적화 등을 (가능하다면) 고려

70

다음 시간에…

• 동적 계획법?
• 이항 계수Binomial Coefficient
• 최장 길이 공통 부분열Longest Common Subsequence
• 두 수열에서 공통된 부분 수열 중 중 가장 긴 부분 수열의 길이를 찾는 방법을 소개
• 연쇄 행렬 곱셈Matrix-Chain Multiplication
• 여러 개의 행렬을 곱할 때, 원소 단위 곱셈 횟수를 최소로 할 수 있는 곱셈 순서를 찾는 알고리즘을 학습

71

알고리즘

Dynamic Programming #1

강원대학교 컴퓨터공학과 최우혁

강의 순서

• 동적 계획법?
• 이항 계수Binomial Coefficient
• 최장 길이 공통 부분열Longest Common Subsequence
• 연쇄 행렬 곱셈Matrix-Chain Multiplication

73

지난 시간에…

• 동적 계획법?
• 큰 문제를 작은 문제로 분할하고, 작은 문제에 대한 해답을 저장/재사용하여 큰 문제의 해답을 내는 문제 해결 방법
• 최적 부분 구조(큰 문제에 대한 해답이 큰 문제를 분할한 작은 문제에 대한 해답을 포함)를 만족하는 최적화 문제를 푸는 데 활용
• Memoization: 분할 정복과 유사하게 하향식Top-Down 문제 해결 방법으로, 큰 문제를 보다 작은 문제로 분할하여 해결
• Tabulation: 상향식Bottom-Up 문제 해결 방법으로, 가장 작은 문제부터 해결해나가면서 큰 문제를 해결

74

지난 시간에…

• 이항 계수Binomial Coefficient

​

​

• 재귀 관계식을 배열로 표현

75

이번 시간에…

• 동적 계획법?
• 이항 계수Binomial Coefficient
• 최장 길이 공통 부분열Longest Common Subsequence
• 두 문자열에서 공통된 부분 문자열 중 가장 긴 부분 문자열의 길이를 찾는 방법을 소개
• 연쇄 행렬 곱셈Matrix-Chain Multiplication
• 여러 개의 행렬을 곱할 때, 원소 단위 곱셈 횟수를 최소로 할 수 있는 곱셈 순서를 찾는 알고리즘을 학습

76

최장 길이 부분열Longest Common Subsequence

77

공통 문자열Common Substring

최장 길이 공통 부분열Longest Common Subsequence

• 두 문자열에서 공통으로 존재하는 연속된 부분 문자열
• 예.

​

​

• 길이 1인 공통 문자열: B, C, D, F
• 길이 2인 공통 문자열: BC, CD
• 길이 3인 공통 문자열: BCD
• 길이 4인 공통 문자열: ?

78

공통 부분열Common Subsequence

최장 길이 공통 부분열Longest Common Subsequence

• 두 문자열에서 공통으로 존재하는 연속되지 않은 부분 문자열
• 예.

​

​

• 길이 1인 공통 부분열: B, C, D, F
• 길이 2인 공통 부분열: BC, BD, BF, CD, CF, DF
• 길이 3인 공통 부분열: BCD, BDF, BCF, CDF
• 길이 4인 공통 부분열: BCDF

79

용도

최장 길이 공통 부분열Longest Common Subsequence

• 두 문서의 다른 정도를 파악
• 유전자 염기 서열의 비교
• 데이터 압축(반복적으로 등장하는 최장 길이 공통 부분열은 제거)
• 표절 감지

80

문제 정의

최장 길이 공통 부분열Longest Common Subsequence

• 두 문자열 A, B에 대해서 최장 길이 공통 부분열의 길이를 찾아라
• 입력: 문자열 A, 문자열 B, 문자열 A의 길이 m, 문자열 B의 길이 n
• 출력: 최장 길이 공통 부분열의 길이

​

​

​

81

무차별 대입Brute-Force 알고리즘

최장 길이 공통 부분열Longest Common Subsequence

• 문자열 A, B에 대해서 부분 문자열을 모두 만들어서 비교
• 길이 m의 문자열 A로 만들 수 있는 모든 부분 문자열의 개수: 2^m
• 길이 n의 문자열 B로 만들수 있는 모든 부분 문자열의 개수: 2ⁿ
• 2^m2ⁿ = 2^{m + n}
• 당연히, 실현 불가능한 알고리즘

82

아이디어

최장 길이 공통 부분열Longest Common Subsequence

• 경우 1. A[6] = B[5]: A[1⋯6]와 B[1⋯5]의 LCS의 길이는 A[1⋯5]와 B[1⋯4] 에서 찾은 LCS의 길이보다 1 긺

83

아이디어

최장 길이 공통 부분열Longest Common Subsequence

• 경우 2. A[6] ≠ B[5]: A[1⋯6]와 B[1⋯5]의 LCS의 길이는 A[1⋯5]와 B[1⋯5]의 LCS의 길이, A[1⋯6]와 B[1⋯4]의 LCS의 길이 중 긴 것과 같음

84

아이디어

최장 길이 공통 부분열Longest Common Subsequence

• A[1⋯i]와 B[1⋯j]에서 찾은 LCS는 그보다 작은 A[1⋯i-1]와 B[1⋯j] 또는 A[1⋯i]와 B[1⋯j-1]에서 찾은 LCS를 포함

85

아이디어

최장 길이 공통 부분열Longest Common Subsequence

• A[1⋯i]와 B[1⋯j]에서 찾은 LCS는 그보다 작은 A[1⋯i-1]와 B[1⋯j] 또는 A[1⋯i]와 B[1⋯j-1]에서 찾은 LCS를 포함
• 최적 부분 구조: 큰 문제에 대한 최적의 해답이, 큰 문제를 분할한 작은 문제에 대한 최적의 해답을 포함

86

재귀 관계식

최장 길이 공통 부분열Longest Common Subsequence

• 배열 L[i][j]: 문자열 A[1⋯i]과 문자열 B[1⋯j]의 LCS의 길이를 저장

​

87

재귀 관계식

최장 길이 공통 부분열Longest Common Subsequence

• 배열 L[i][j]: 문자열 A[1⋯i]과 문자열 B[1⋯j]의 LCS의 길이를 저장
• 경우 1. A[i] = B[j]: A[1⋯i]와 B[1⋯j]의 LCS의 길이는 A[1⋯i-1]와 B[1⋯j-1]의 LCS의 길이보다 1 긺

​

88

재귀 관계식

최장 길이 공통 부분열Longest Common Subsequence

• 배열 L[i][j]: 문자열 A[1⋯i]과 문자열 B[1⋯j]의 LCS의 길이를 저장
• 경우 1. A[i] = B[j]: A[1⋯i]와 B[1⋯j]의 LCS의 길이는 A[1⋯i-1]와 B[1⋯j-1]의 LCS의 길이보다 1 긺
• 경우 2. A[i] ≠ B[j]: A[1⋯i]와 B[1⋯j]의 LCS의 길이는 A[1⋯i-1]와 B[1⋯j]의 LCS의 길이, A[1⋯i]와 B[1⋯j-1]의 LCS의 길이 중 긴 것과 같음

​

89

재귀 관계식

최장 길이 공통 부분열Longest Common Subsequence

• 배열 L[i][j]: 문자열 A[1⋯i]과 문자열 B[1⋯j]의 LCS의 길이를 저장
• 경우 1. A[i] = B[j]: A[1⋯i]와 B[1⋯j]의 LCS의 길이는 A[1⋯i-1]와 B[1⋯j-1]의 LCS의 길이보다 1 긺
• 경우 2. A[i] ≠ B[j]: A[1⋯i]와 B[1⋯j]의 LCS의 길이는 A[1⋯i-1]와 B[1⋯j]의 LCS의 길이, A[1⋯i]와 B[1⋯j-1]의 LCS의 길이 중 긴 것과 같음
• 그 외. i = 0 또는 j = 0: 문자열의 길이가 0이므로 LCS의 길이는 0

​

90

의사 코드

최장 길이 공통 부분열Longest Common Subsequence

91

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

92

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

93

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

94

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

95

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

96

의사 코드: 예.

최장 길이 공통 부분열Longest Common Subsequence

97

분석: 시간 복잡도

최장 길이 공통 부분열Longest Common Subsequence

• 입력 크기: m, n
• 단위 연산: L[i][j]에 연산 결과를 저장
• 즉, for-i 및 for-j 루프의실행 횟수

​

98

분석: 시간 복잡도

최장 길이 공통 부분열Longest Common Subsequence

• for-i 루프의 실행 횟수: m + 1
• for-j 루프의 실행 횟수: n + 1
• (m + 1) ⨉ (n + 1) ∈ Θ(mn)

99

분석: 공간 복잡도

최장 길이 공통 부분열Longest Common Subsequence

• (m + 1) ⨉ (n + 1) 크기의 2차원 배열에 결과를 저장 ∈ Θ(mn)

100

공간 복잡도의 개선

최장 길이 공통 부분열Longest Common Subsequence

​

​

• L[i][j] 계산에는 L[i-1][j-1], L[i][j-1], L[i-1][j]만이 활용되며, L[i-2], L[i-3] 등의 값들은 사용되지 않음

101

공간 복잡도의 개선

최장 길이 공통 부분열Longest Common Subsequence

​

​

• 따라서, 이항 계수와 마찬가지로, 2차원 배열을 사용하는 대신 바로 전 행의 값들을 저장하는 1차원 배열로 설계할 수 있음

102

공간 복잡도의 개선: 의사 코드

최장 길이 공통 부분열Longest Common Subsequence

103

연쇄 행렬 곱셈Matrix-Chain Multiplication

104

행렬 곱셈의 원소 단위 곱셈 횟수

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 2 ⨉ 4 행렬 A와 4 ⨉ 3 행렬 B의 곱은 2 ⨉ 3 행렬 C
• 행렬 C의 각 원소는 A의 열 원소 4개와 B의 행 원소 4개의 내적Dot Product으로 구성 = 4회의 원소 단위 곱셈 필요
• 행렬 C의 모든 원소 계산에 필요한 원소 단위 곱셈 수는 2 ⨉ 3 (행렬 C의 원소 수) ⨉ 4 (행렬 C의 원소당 원소 단위 곱셈 수) = 24

105

행렬 곱셈의 원소 단위 곱셈 횟수

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 2 ⨉ 4 행렬 A와 4 ⨉ 3 행렬 B의 곱은 2 ⨉ 3 행렬 C
• 행렬 C의 각 원소는 A의 열 원소 4개와 B의 행 원소 4개의 내적Dot Product으로 구성 = 4회의 원소 단위 곱셈 필요
• 행렬 C의 모든 원소 계산에 필요한 원소 단위 곱셈 수는 2 ⨉ 3 (행렬 C의 원소 수) ⨉ 4 (행렬 C의 원소당 원소 단위 곱셈 수) = 24
• (i ⨉ j 행렬) ⨉ (j × k 행렬) = (i ⨉ k 행렬) 시, i ⨉ j ⨉ k 회 원소 단위 곱셈

106

세 개 이상의 행렬 곱셈

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 결합 법칙: 세 개 이상의 행렬을 곱셈할 시, 두 행렬 간의 곱셈을 적용하는 순서는 상관 없음

​

• 단, 곱셈의 교환 법칙은 성립하지 않음

​

​

107

세 개 이상의 행렬 곱셈

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 결합 법칙을 적용하는 순서에 따라, 원소 단위 곱셈의 횟수가 크게 달라짐
• 예.

108

문제 정의

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 곱하는 데 필요한 원소 단위 곱셈의 최소 횟수를 구하라
• 입력 및 매개변수: 행렬의 개수 n, 각 행렬의 행 및 열의 수
• 출력: 원소 단위 곱셈의 최소 횟수 (+ 최적의 곱셈 순서)

​

109

무차별 대입Brute-force 알고리즘

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 모든 가능한 곱셈 방법을 찾은 후에, 그 중 가장 작은 원소 단위 곱셈 횟수를 선택
• T(n): n개의 행렬을 곱하는 모든 순서의 가짓수
• A₁(A₂A₃⋯A_n-1A_n): T(n-1)
• (A₁A₂A₃⋯A_n-1)A_n: T(n-1)
• 잘 모르겠으나 일단 추가적인 연산이 존재할 것

​

110

무차별 대입Brute-force 알고리즘

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 모든 가능한 곱셈 방법을 찾은 후에, 그 중 가장 작은 원소 단위 곱셈 횟수를 선택
• T(n): n개의 행렬을 곱하는 모든 순서의 가짓수
• T(n-1) + T(n-1) = 2T(n-1) ∈ Ω(2ⁿ)

111

아이디어

연쇄 행렬 곱셈Matrix-Chain Multiplication

112

아이디어

연쇄 행렬 곱셈Matrix-Chain Multiplication

113

A₂A₃A₄를

곱하는

최적의 순서

아이디어

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 최적(= 최소의 원소 단위 곱셈 횟수)의 순서로 곱하는 것은, 그보다 작은 행렬을 최적의 순서로 곱하는 것을 포함

114

아이디어

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 최적(= 최소의 원소 단위 곱셈 횟수)의 순서로 곱하는 것은, 그보다 작은 행렬을 최적의 순서로 곱하는 것을 포함
• 최적 부분 구조: 큰 문제에 대한 최적의 해답이, 큰 문제를 분할한 작은 문제에 대한 최적의 해답을 포함

115

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 곱하는 최소의 원소 단위 곱셈 횟수

​

​

116

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 곱하는 최소의 원소 단위 곱셈 횟수

​

• n개의 행렬을 두 부분으로 나누고, 각 부분에 포함된 행렬들을 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수

​

117

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 곱하는 최소의 원소 단위 곱셈 횟수

​

• n개의 행렬을 두 부분으로 나누고, 각 부분에 포함된 행렬들을 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수
• 나눠진 두 부분의 곱으로 구성된 행렬을 곱하는 데 필요한 원소 단위 곱셈 횟수

118

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• n개의 행렬을 곱하는 최소의 원소 단위 곱셈 횟수

​

• n개의 행렬을 두 부분으로 나누고, 각 부분에 포함된 행렬들을 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수
• 나눠진 두 부분의 곱으로 구성된 행렬을 곱하는 데 필요한 원소 단위 곱셈 횟수

119

두 부분으로 나누는 경우들 중 최소의 원소 단위 곱셈 횟수를 찾아야 함

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• D[i]: 연속된 행렬의 행과 열 정보를 담는 배열로, A_i의 열 개수 또는 A_i+1의 행 개수를 의미
• M[i][j]: A_i⋯A_j를 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수

​

120

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• D[i]: 연속된 행렬의 행과 열 정보를 담는 배열로, A_i의 열 개수 또는 A_i+1의 행 개수를 의미
• M[i][j]: A_i⋯A_j를 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수

​

121

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• D[i]: 연속된 행렬의 행과 열 정보를 담는 배열로, A_i의 열 개수 또는 A_i+1의 행 개수를 의미
• M[i][j]: A_i⋯A_j를 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수

​

122

재귀 관계식

연쇄 행렬 곱셈Matrix-Chain Multiplication

• D[i]: 연속된 행렬의 행과 열 정보를 담는 배열로, A_i의 열 개수 또는 A_i+1의 행 개수를 의미
• M[i][j]: A_i⋯A_j를 곱하는 데 필요한 최소의 원소 단위 곱셈 횟수

​

123

의사 코드

연쇄 행렬 곱셈Matrix-Chain Multiplication

124

하나의 행렬을 곱하는

횟수는 없으므로 0으로 초기화

연쇄 행렬 곱셈의 길이: l + 1

연쇄 행렬 곱셈의 시작 위치: i

연쇄 행렬 곱셈의 종료 위치: j

• 예. l = 1, A₁A₂, A₂A₃, A₄A₅, ⋯
• 예. l = 2, A₁A₂A₃, A₂A₃A₄,⋯

A_i⋯A_j개의 행렬을 두 부분으로 나누는 모든 방법에 대해, 최소 원소 단위 곱셈 횟수를 구함

의사 코드: 예. 초기 상태

연쇄 행렬 곱셈Matrix-Chain Multiplication

125

의사 코드: 예. l = 1

연쇄 행렬 곱셈Matrix-Chain Multiplication

126

의사 코드: 예. l = 1

연쇄 행렬 곱셈Matrix-Chain Multiplication

127

의사 코드: 예. l = 1

연쇄 행렬 곱셈Matrix-Chain Multiplication

128

의사 코드: 예. l = 2

연쇄 행렬 곱셈Matrix-Chain Multiplication

129

의사 코드: 예. l = 2

연쇄 행렬 곱셈Matrix-Chain Multiplication

130

의사 코드: 예. l = 2

연쇄 행렬 곱셈Matrix-Chain Multiplication

131

의사 코드: 예. l = 3

연쇄 행렬 곱셈Matrix-Chain Multiplication

132

의사 코드: 예. l = 4

연쇄 행렬 곱셈Matrix-Chain Multiplication

133

분석

연쇄 행렬 곱셈Matrix-Chain Multiplication

• 입력 크기: n
• 단위 연산: 원소 단위 곱셈 횟수의 계산
• 즉, for-l, for-i, for-k 루프의 실행 횟수

134