• 여기에서 다루는 내용은 전통적인 동적 계획법의 정의와도 다르고 유도하는 방식도 다르고 하여간 전부 야매입니다
• 이거 발표하는 빙한테 야매라고 혼났어영 ㅇㅅㅇ
• 여기 나온대로 학교 시험 봤다가 틀려서 학점 빵꾸나도 난몰라요
• 이 내용을 쫄깃하게 설명한 책이 (아마도) 7월 10일 전에 나올겁니다. 나오면 한권 사주세요...

• Dynamic 하고도, Programming 하고도 아무 관련 없는 알고리즘 설계 패러다임
  • 전산학 역사상 제일 잘못 지은 이름이라고 생각합니다
• 한 마디로 말하자면: 문제를 여러 조각들로 나누고, 이 때 여러 번 계산되는 문제들을 메모리에 저장해서 속도를 올린다
• 프로그래밍 대회에서는 참 중요하죠

• 재귀 호출: 문제를 여러 조각으로 쪼개 재귀적으로 해결하는 방법
• 완전 탐색: 재귀 호출을 이용해 최적화 문제 풀기
• 메모이제이션: 시간과 공간 트레이드오프로 동적 계획법 알고리즘 만들기
• 경우의 수 세기와 확률 문제 DP 로 풀기
• 다른 테크닉들 (시간이 되면..)

오늘 다루는 분량이 많으니 한 입에 다 먹겠다고 생각하지 마시고, 한 번에 할 수 있는 만큼만 꼭꼭 씹어드세요. 절반만 이해해도 오늘 성공!

• 다 아시는 얘길테지만 한 번 하고 넘어갑시다

• 컴퓨터가 하는 많은 일들은 작은 조각들로 쪼갤 수 있죠

• 문자열 길이 재기: 첫 글자 세고, 두 번째 글자 세고, 세 번째 글자 세고..
• 정렬: 제일 작은 원소 찾고, 두 번째로 작은 원소 찾고, 세 번째로 작은 원소 찾고..
• 재귀 호출 함수: 하나의 큰 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤, 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

1 // 필수 조건: n >= 1
2 // 1 부터 n 까지의 자연수의 합을 반환한다
3 int sum(int n) {
4   int ret = 0;
5   for(int i = 1; i <= n; ++i)
6     ret += i;
7   return ret;
8 }

• 각 숫자를 한 개의 조각이라고 하면, $n$ 개의 조각으로 쪼갤 수 있지요
• 재귀 호출 함수는 한 개의 조각을 수행하고, 나머지를 재귀호출해서 해결합니다

1 int recursiveSum(int n) {
2   if(n == 1) return 1; // 더 못 쪼개겠네
3   return n + recursiveSum(n-1);
4 }

• $sum(n)=n+sum(n-1)$ 을 이용하면 되니까
• 기저 사례 (base case): 첫 줄에 있는 if 문. 더 이상 쪼개지지 않는 최소의 입력을 처리하죠

 1 int wrongSum(int n) {
 2   if(n == 2) return 3; // 1+2
 3   return n + wrongSum(n-1);
 4 }
 5 
 6 int correctSum(int n) {
 7   if(n == 0) return 0;
 8   return n + correctSum(n-1);
 9 }
10 
11 int correctSum2(int n) {
12   if(n == 0) return 0;
13   if(n == 1) return 1;
14   if(n == 2) return 3;
15   return n + correctSum2(n-1);
16 }

1 for(int i = 0; i < n; ++i)
2   for(int j = i+1; j < n; ++j)
3     for(int k = j+1; k < n; ++k)
4         cout << i << " " << j << " " << k << endl;

• $n$ 개의 원소 중에서 3개를 고르는 모든 방법
• 4개를 해야 하면 어쩌지? 4중 for문을 쓰나?
• 5개를 해야 하면 어쩌지? 5중 for문을 쓰나?

• 이 코드 조각이 하는 작업을 3개로 나누자
  • 한 조각에서 한 개의 원소 고르기
• 한 개 골랐으면 나머지는 재귀호출해서 자기한테 떠넘기자
• 재귀호출할 때 어떤 정보를 넘겨줘야 할까?
  • 원소들의 총 개수
  • 더 골라야 할 원소들의 개수
  • 지금까지 고른 원소들의 번호

 1 // n: 전체 원소의 수
 2 // picked: 지금까지 고른 원소들의 번호
 3 // toPick: 더 고를 원소의 수
 4 // 일 때, 앞으로 toPick 개의 원소를 고르는 모든 방법을 출력한다.
 5 void pick(int n, vector<int>& picked, int toPick) {
 6     // 기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다
 7     if(toPick == 0) {
 8         printPicked(picked);
 9         return;
10     }
11 
12     // 고를 수 있는 가장 작은 번호를 계산한다
13     int smallest = picked.empty() ? 0 : picked.back() + 1;
14     // 이 단계에서 원소 하나를 고른다
15     for(int next = smallest; next < n; ++next) {
16         picked.push_back(next);
17         pick(elements, picked, toPick - 1);
18         picked.pop_back();
19     }
20 }

• 문제 (problem) 과 부분 문제 (subproblem)
• 어느 쪽이 재귀호출에서 얘기하는 '문제'일까?
  • 입력으로 주어지는 자연수 수열을 정렬하라.
  • ${16,7,9,1,31}$ 을 정렬하라.
• 문제 란 수행해야 할 작업과 작업을 적용할 자료의 조합
• 부분 문제 란 문제를 구성하는 조각 중 하나를 떼어내고 남은 문제

• 문제의 답이 여러 개 있고 그 중 가장 좋은 답을 찾는 문제
  • 우리집에서 구글코리아 오피스까지 오는 제일 짧은 경로는?
  • 오늘 사온 간식을 다 같이 나눠먹되 내가 제일 많이 먹는 방법은?
• 이런 건 아니다
  • 이항 계수 구하기 (여러 개의 이항 계수 중 제일 좋은 답 구하기??)
• 최적화 문제를 푸는 방법은 다양하지만 그 중 제일 기본적인 방법은 무식하게 푸는 것입니다

• 답이 여러 개 있어서 어느 게 더 좋은지 모르겠다고? 그럼 다 만들어 보지 뭐
• 컴퓨터가 잘하는게 계산 빠른 것밖에 더 없으니 유용합니다
• 재귀호출로 구현하는게 제일 쫄깃하지요

• 모든 도시를 다 돌아보고 싶습니다
• 도시 사이에 이동하는 시간이 서로 다릅니다
• 어느 순서대로 도시들을 방문해야 제일 빨리 돌아볼 수 있을까요?

 1 int n; // 도시의 수
 2 int distance[10][10]; // 두 도시간의 거리를 저장하는 배열
 3 
 4 // 주어진 경로의 길이를 반환하는 함수
 5 int getPathLength(const vector<int>& path);
 6 // 주어진 경로에 해당 도시가 이미 포함되어 있는지를 반환하는 함수
 7 bool isVisited(const vector<int>& path, int city);
 8 
 9 // curPath: 지금까지 만든 경로 위에 있는 도시들의 번호
10 // 라고 할 때, 만들 수 있는 경로 중 가장 짧은 것을 출력한다
11 int shortestPath(vector<int>& curPath) {
12     // 기저 사례: 이미 경로가 완성되었을 때 현재 길이를 반환
13     if(curPath.size() == n) return getPathLength(curPath);
14     int ret = 987654321;
15     for(int next = 0; next < n; ++next) {
16         if(isVisited(curPath, next)) continue;
17         curPath.push_back(next);
18         ret = min(ret, shortestPath(curPath));
19         curPath.pop_back();
20     }
21 }

한 부분 문제는 한 번만 해결됨	한 부분 문제가 여러 번 중복으로 해결됨

• 이런 현상을 중복되는 부분 문제 (overlapping subproblems) 라고 부릅니다

\[ \left({n\atop r}\right)=\begin{cases} \left({n-1\atop r-1}\right)+\left({n-1\atop r}\right)\\ 1 & (r=0\mbox{ or }n=r)\end{cases}\]

구현하는 건 간단하죠?

1 int bino(int n, int r) {
2     // 기저 사례: n=r or r=0
3     if(r == 0 || n == r) return 1;
4     return bino(n-1, r-1) + bino(n-1, r);
5 }

• bino(25,12) 를 계산하려면 1천만번의 함수 호출이 필요하다고?
• 의사양반 내 코드가 ㄱㅈ란 말이요

1 int cache[100][100];
2 int bino(int n, int r) {
3     if(n == r || r == 0) return 1;
4     int& ret = cache[n][r];
5     if(ret != -1) return ret;
6     return ret = bino(n-1, r-1) + bino(n-1, r);
7 }
8 ..
9 memset(cache, -1, sizeof(cache));

• 함수의 반환값을 저장해 둘 캐시를 만들어 놓자
• 한 번 계산한 값은 캐시에 저장해 두고
• 함수가 호출될 때마다 저장된 적이 있는지 캐시에 확인하기
• 간단하죠? 이런 기법을 메모이제이션 (memoization) 이라고 부릅니다

1 int counter = 0;
2 int count() {
3     return counter++;
4 }

• 이런 함수에 쓰는 바보짓을 할 순 없죠..
• 전역 변수, 클래스의 멤버 변수, 파일 입력, 키보드 입력에 영향받는 함수는 안된다
• 함수 반환값이 항상 함수의 입력에 의해서만 계산되는 함수
• 멋있게는 참조적 투명한 (referential transparent) 함수에만 써먹을 수 있죠

6
1 2
3 7 4
9 4 1 7
2 7 5 9 4

• 맨 위의 숫자에서 시작해 한 칸씩 아래로 내려가기
• 왼쪽이나 오른쪽 숫자로 내려갈 수 있음
• 경로에서 만나는 숫자의 최대 합은 얼마일까?
• 재귀 호출: 문제를 $n$ 조각 내서, 한 조각마다 한 칸씩 내려가자

 1 // MAX_NUMBER: 한 칸에 들어갈 숫자의 최대값
 2 int n, triangle[100][100];
 3 int cache[100][100][MAX_NUMBER*100+1];
 4 
 5 // (y,x) 위치까지 내려오기 전에 만난 숫자들의 합이 sum 일 때
 6 // 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로를 반환한다
 7 int path1(int y, int x, int sum) {
 8     // 기저 사례: 맨 아래 줄까지 도달했을 경우
 9     if(y == n-1) return sum + triangle[y][x];
10 
11     // 메모이제이션
12     int& ret = cache[y][x][sum];
13     if(ret != -1) return ret;
14 
15     sum += triangle[y][x];
16     return ret = max(path1(y+1, x+1, sum), path1(y+1, x, sum));
17 }

1
2 4
8 16 32
64 128 256 512
1024 2048 4096 8192 16384

• 모든 경로는 서로 합이 다르다!
• 두 부분 문제가 겹칠 일이 없어요

• path1() 의 입력 $y$, $x$, $sum$ 은 두 부류로 나눌 수 있다
  • $y$, $x$: 부분 문제의 정의 = 앞으로 풀어야 할 조각들
  • $sum$: 지금까지 해결한 조각들의 결과
• 이 때 $(y,x)$ 에서 내려가는 최대 경로 랑 $sum$ 이랑은 상관이 없지요
• 지금까지 어떤 경로로 내려왔건간에 path1() 는 $(y,x)$ 에서 내려가는 최대 경로만 찾거든요

• 문제와 분할 방식이 가지는 성질
• 부분 문제의 최적해만 갖고 있으면 전체 문제의 최적해를 구성해낼 수 있다
  • 다르게 말해, 부분 문제는 항상 최적해만 구하면 된다!
• 성립하지 않는 예:
  • 맨 윗줄에서 아랫줄까지 내려오면서 같은 숫자를 두번 만나면 안된다
  • 이 위에서 어떤 수를 만났느냐에 따라 다른 답을 반환해야 할 수도 있다!

• path1(y,x,sum): $(y,x)$ 까지 내려오는 경로의 합이 $sum$ 이었을 때 전체 경로의 최대 합

• path2(y,x): $(y,x)$ 에서 맨 아래까지 내려가는 경로 중 최대 합

• 이전 조각들에 관한 정보가 없어졌음에 유의합시다:

  • 이전 경로의 합 $sum$ 도 없어졌고
  • 반환 값에 이전 경로의 합은 아예 안 들어감
• 이와 같은 변화는 최적 부분 구조가 성립해서 가능하죠
  • 이전 조각과 상관 없이 최대 경로로만 내려가면 되니까

 1 int n, triangle[100][100];
 2 int cache2[100][100];
 3 // (y,x) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는
 4 // 최대 경로의 합을 반환한다
 5 int path2(int y, int x) {
 6     // 기저 사례
 7     if(y == n-1) return triangle[y][x];
 8 
 9     int& ret = cache2[y][x];
10     if(ret != -1) return ret;
11 
12     return ret = max(path2(y+1, x), path2(y+1, x+1)) +
13         triangle[y][x];
14 }

• 이제 $O(n^2)$! 우왕ㅋ굳ㅋ

\[ path2(y,x)=\begin{cases} \mathit{t}\left[y,x\right]+\max\begin{cases} path2(y+1,x)\\ \mathit{path2}(y+1,x+1)\end{cases} & (y<n-1)\\ t\left[y,x\right] & (y=n-1)\end{cases}\]

• 재귀 함수가 답을 어떻게 계산하는지를 수학식으로 쓴 것
• 실제 코드를 쓸 필요 없이 부분 문제의 정의와 계산 방법을 간략하게 표현할 수 있어서 책에선 자주 씁니다

1. 모든 답을 만들어서 제일 좋은 답을 찾는 완전 탐색 알고리즘을 설계합니다.
2. 부분 문제 정의에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 이를 위해 입력을 조작하거나 형태를 바꿔야 할 수도 있습니다. 재귀 호출은 이전의 선택과는 관련 없이 앞으로 남은 선택에 관련된 답만을 반환합니다.
3. 메모이제이션을 적용합니다.
4. Profit

Disclaimer: 물론 이것이 전부는 아니고, 경우에 따라서 다를 수도 있고, 운운..

$2 \times N$ 크기의 사각형을 $2 \times 1$ 크기의 타일로 채우는 방법의 수

• 동적 계획법은 경우의 수를 세거나 확률을 계산하는 문제에도 흔히 사용됩니다.
  • 처음에 예로 들었던 이항 계수도 사실 경우의 수를 계산하는 문제니까요.

• 모든 방법은 맨 왼쪽 세로줄이 어떻게 덮여 있냐로 나눌 수 있지요

• 분할에 항상 성립해야 하는 두 가지 조건:
  • 두 가지 분류는 모든 타일링 방법을 포함한다
  • 모든 타일링 방법은 두 분류 중 정확히 한 개에 속한다

 1 int cache[101];
 2 
 3 // 2*width 크기의 사각형을 채우는 방법의 수를 반환한다
 4 int tiling(int width) {
 5     // 기저 사례: width 가 1 또는 0 일 때
 6     if(width <= 1) return 1;
 7     int& ret = cache[width];
 8     if(ret != -1) return ret;
 9     return ret = tiling(width-2) + tiling(width-1);
10 }

• $O(n)$ 개의 부분 문제를 각각 $O(1)$ 시간에 계산하므로 전체 시간 복잡도는 $O(n)$

• 깊이가 $n$ 미터인 우물의 바닥에서 달팽이가 기어 올라온다
• 날이 맑으면 하루에 2미터, 비가 내리면 1미터 기어올라갈 수 있다
• 장마라, 앞으로 $m$ 일간 비가 올 확률은 75%, 맑을 확률은 25%
• $m$ 일 안에 우물을 벗어날 수 있는 확률은?

• $climb(d,t)=$앞으로 d 일간 t 미터를 기어오를 수 있는 확률은?
• 역시 두 가지 사건으로 나눌 수 있다
  • 첫날 비가 온다: $climb(d-1,t-1)$
  • 첫날 비가 오지 않는다: $climb(d-1,t-2)$
• 점화식

\[ climb(d,t) = \begin{cases} 0.75 \times climb(d-1,t-1) \\\\ + 0.5 \times climb(d-1,t-2) \end{cases}\]

• $n$ 개의 - 와 $m$ 개의 o 로 구성된 모든 모스 신호 (Morse code) 를 담은 사전이 있다고 합시다

    --oo
    -o-o
    -oo-
    o--o
    o-o-
    oo--

• 이 중 $k$ ($1 \le k \le 1,000,000,000$) 번째 신호는?

• 사전 순서대로 신호를 하나씩 생성해 나가다가 $k$ 번째 것을 반환하는 사치를 부릴 수는 없죠
• 똑같이 생성해 나가되 중간에 필요 없는 답들은 건너뜁니다.
• 1000번째 답을 출력해야 하는데, - 로 시작하는 신호가 600개 있다
  • 이 경우 - 로 시작하는 신호들은 만들 필요 없이 만든 셈 치고 넘어가면 되죠
  • 이것을 위해서는 답의 수를 셀 수 있어야 합니다

• 답의 수는 이항 계수로 계산 가능 $\left( {n+m} \atop n \right) $

\[ \left({n+m\atop n}\right)\begin{cases} \left.\begin{array}{c} \mathtt{-----ooooo}\\ \mathtt{----o-oooo}\\ \mathtt{\vdots}\\ \mathtt{-ooooo----}\end{array}\right\} \left({n+m-1\atop n-1}\right)\\ \left.\begin{array}{c} \mathtt{o-----oooo}\\ \mathtt{o----o-ooo}\\ \vdots\\ \mathtt{ooooo-----}\end{array}\right\} \left({n+m-1\atop n}\right)\end{cases}\]

• $skip = k-1$: $skip$ 은 우리가 원하는 신호 $X$ 앞에 오는 신호의 수
• 첫 글자가 - 인 신호의 수 $D= \left( {n+m-1}\atop{n-1}\right)$ 와 $skip$ 을 비교하자
  • $skip \ge D$: 모든 - 신호들이 $X$ 앞에 오므로 - 신호들을 전부 건너뛰자. $X$ 의 첫 글자는 o. 이 때 o신호중 $skip - D$ 개를 건너뛰고 출력
  • $skip \lt D$: 모든 - 신호들을 건너뛰어서는 안된다. $X$ 의 첫 글자는 -. -신호중 $skip$ 개를 건너뛰고 출력

 1 // n개의 -, m개의 o 로 구성된 신호 중 k번째 신호를 반환한다
 2 // (k 는 0 부터 시작)
 3 string kth(int n, int m, int k) {
 4     if(n == 0 && m == 0) return "";
 5     // dashes: - 로 시작하는 신호의 수
 6     int dashes = bino[n+m-1][n-1];
 7     if(n > 0 && k < dashes)
 8         return "-" + kth(n-1, m, k);
 9     return "o" + kth(n, m-1, k - dashes);
10 }

1. 모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계합니다. 이 때 재귀호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성이 성립해야 합니다.
   1. 모든 경우는 이 선택지에 포함됨
   2. 어떤 경우도 두 개 이상의 선택지에 포함되지 않음
2. 최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄입니다. 재귀 호출 함수는 앞으로 남아 있는 조각들을 채우는 경우의 수만을 반환해야 합니다.
3. 메모이제이션을 적용합니다.
4. Profit

1. 답들을 사전 순서대로 만들어가는 완전 탐색 알고리즘을 설계하고, 메모이제이션을 적용해 경우의 수를 세는 동적 계획법 알고리즘으로 바꿉니다.
2. 각 선택지를 하나하나 고려하며, 이 선택지를 선택했을 때 만들어지는 답의 수 $M$ 과 건너 뛰어야 할 답의 수 $skip$ 을 비교합니다.
   1. $M \le skip$: $M$ 개의 답은 모두 우리가 원하는 답보다 앞에 있으므로, 이들을 건너뜁니다. $skip=skip-M$ 이 됩니다.
   2. $M gt skip$: $M$ 개의 답 중에 우리가 원하는 답이 있으므로, 이들을 선택합니다. $M$ 개의 답 중에 $skip$ 개를 건너뛴 것이 우리가 원하는 답입니다. 이 선택지를 답에 추가하고 재귀호출로 답의 나머지 부분을 만듭니다.

• 오목의 간단 버전인 셈이죠
• 같은 무늬를 가로 세로 대각선으로 3칸 만들면 이기고, 승부가 나지 않고 판이 꽉 차면 비긴다
• 문제: 내가 놓을 차례인 게임판이 주어진다. 양쪽이 모두 '완벽하게' 플레이할때 누가 이길까?

• 상대방이 어떻게 플레이하더라도, 나만 잘 하면 이길 수 있다 => 승리
• 내가 어떻게 플레이하더라도, 상대방이 잘 하면 내가 질 수밖에 없다 => 패배

• 게임의 '상태' 가 주어질 때, 게임의 승패를 반환하는 함수를 정의하자
  • F(state) = 현재 상태에서, 이번 차례인 사람이 반드시 승리할 수 있는 방법이 있는가?

• 상대방이 결과적으로 '잘 해봐야 지는' 결과가 있다면 당연히 그걸 택한다
• 만약 그런 결과가 하나도 없다면 나는 무조건 진다
  • 내가 뭘 해도, 상대방이 적절히 플레이하면 난 지니까 ㅜㅜ

 1 map<vector<string>, int> cache;
 2 // 내가 이길 수 있으면 1 을, 비길 수 있으면 0 을, 지면 -1 을 리턴한다
 3 int canWin(vector<string>& board, char turn) {
 4   // 기저 사례: 마지막에 상대가 둬서 한줄이 만들어진 경우
 5   if(isFinished(board, 'o'+'x'-turn)) return -1;
 6   if(cache.count(board)) return cache[board];
 7   int& ret = cache[board];
 8   // 각 반환값 중 상대가 이기는 결과 (1) 보다 비기는 결과 (0),
 9   // 비기는 결과보다 상대가 지는 결과 (-1)를 원한다:
10   // 모든 반환값의 min 을 취하자
11   int minValue = 2;
12   for(int y = 0; y < 3; ++y)
13     for(int x = 0; x < 3; ++x) {
14       if(board[y][x] == '.') {
15         board[y][x] = turn;
16         minValue = min(minValue, canWin(board, 'o'+'x'-turn));
17         board[y][x] = '.';
18       }
19     }
20   // 플레이할수 없거나, 어떻게 해도 비기는 것이 최선인 경우
21   if(minValue == 2 || minValue == 0) return ret = 0;
22   // 최선이 상대가 이기는 거라면 난 무조건 지고, 상대가 지는 거라면 난 이긴다
23   return ret = -minValue;
24 }

1. 상태가 주어질 때 이번 차례인 사람이 이기는지 반환하는 함수를 구성한다 a. 한번에 이길 수 있는 경우가 기저 사례
2. 할 수 있는 모든 동작을 다 하고, 재귀호출한다. a. 하나라도 상대가 지는 결과가 나오면 내가 이기고 b. 전부 다 상대가 이기는 결과가 나오면 나는 진다
3. 메모이제이션을 적용한다

1 int complexFunction(const string& aString);
2 double moreComplexFunction(const vector<bool>& aBoolVector);
3 long long evenMoreComplexFunction(const vector<int>& anIntVector);
4 double oops(double aDouble);

• 위와 같은 함수들을 어떻게 메모이제이션할까요?

1 map<string,int> cache1;
2 map<vector<bool>,int> cache2;
3 map<vector<int>,long long> cache3;
4 map<double,double> cache4;

• 때에 따라선 이렇게 할 수도 있지만 (그렇다고 map<double,double> 쓰면 안되지만요)
• 대개 더 나은 방법이 있습니다

1 // [0,n-1] 범위의 정수에 대응시켜 준다
2 int bijection(const vector<int>& input);
3 
4 long long cache[MAX_N];
5 long long evenMoreComplexFunction(const vector<int>& anIntVector) {
6     long long& ret = cache[bijection(anIntVector)];
7     if(ret != -1) return ret;
8     ...
9 }

• $n$ 가지 입력이 가능하다고 할 때, 입력을 $[0,n-1]$ 범위의 정수와 1:1 대응하는 함수를 만듭니다
• 그러면 그냥 1차원 배열을 써서 메모이제이션할 수 있지요.

• Common patterns:
  • 입력이 특정 문자열/배열의 일부이다
  • 입력이 bool 값의 배열이다
  • 입력이 $[1,2,\cdots,N]$ 의 순열이다

        0123456789A$
    S = abracadabra$
    A =      adabra$
    B =   racada   $

• 입력 문자열 $A$ 가 항상 어떤 문자열 $S$ 의 suffix 라고 하면
  • $A$ 를 전달하는 대신에 $S$ 내에서 $A$ 의 시작 위치만을 전달 => 1차원!
• $B$ 가 어떤 문자열 $S$ 의 연속된 일부라고 하면
  • $B$ 를 전달하는 대신에 $S$ 내의 시작과 끝 위치를 전달 => 2차원!

\[ [ true, true, false, false, true, true ] \]

\[ = 110011_{2} = 51 \]

• 입력을 $n$자리의 이진수로 보면 $[0,2^{n}-1]$ 범위의 정수가 됨!

 1 vector<bool> A;
 2 int B;
 3 
 4 if(A[idx]) ;
 5 if(B & (1 << idx)) ;
 6 
 7 A[idx] = true;
 8 B |= (1 << idx);
 9 
10 A[idx] = false;
11 B &= ~(1 << idx);

• 애초에 배열을 만들 필요 없이 정수형을 쓰면 좋습니다
• 알고 보면 정수형을 쓰는 게 더 강력해요
• 아니면 bitset 을 쓰는 방법을 배워도 좋습니다

1 2 3 4 5 6
1 2 3 4 6 5
1 2 3 5 4 6
...
6 5 4 3 2 1

• $n!$ 개의 permutation
• permutation 이 주어질 때 사전에서 몇 번째에 오는지 반환하는 함수를 만들 수 있다

• 아까 봤지요?
• $O(n!)$ 시간이 걸려서 $n \gt 10$ 쯤 되면 느려집니다
• 어떻게 하면 메모이제이션을 할 수 있을까요?

 1 int n; // 도시의 수
 2 int distance[10][10]; // 두 도시간의 거리를 저장하는 배열
 3 
 4 // 주어진 경로의 길이를 반환하는 함수
 5 int getPathLength(const vector<int>& path);
 6 // 주어진 경로에 해당 도시가 이미 포함되어 있는지를 반환하는 함수
 7 bool isVisited(const vector<int>& path, int city);
 8 
 9 // curPath: 지금까지 만든 경로 위에 있는 도시들의 번호
10 // 라고 할 때, 만들 수 있는 경로 중 가장 짧은 것을 출력한다
11 int shortestPath(vector<int>& curPath) {
12     // 기저 사례: 이미 경로가 완성되었을 때 현재 길이를 반환
13     if(curPath.size() == n) return getPathLength(curPath);
14     int ret = 987654321;
15     for(int next = 0; next < n; ++next) {
16         if(isVisited(curPath, next)) continue;
17         curPath.push_back(next);
18         ret = min(ret, shortestPath(curPath));
19         curPath.pop_back();
20     }
21 }

• 지금까지 한 선택 (지금까지 방문한 경로들) 에 관한 정보를 최소한으로 줄입시다

1. 방문한 경로의 길이 계산 (getPathLength)
   • shortestPath 가 전체 경로 대신 앞으로 지나는 경로의 길이만 반환하도록 바꾸면 이 정보는 필요없어진다
   • 대신 지금 위치가 어디인지만 알면 된다 (curPath.back())
2. 어떤 도시를 전에 방문했는지 확인 (isVisited)
   • 이걸 무시할 수는 없지만, '어느 순서대로 방문했는지' 정보는 필요 없다
   • 각 도시별로 방문했는지 여부를 나타내는 bool 배열을 받아볼까?

• $O(n!)$ 가지의 값을 갖는 $curPath$ 정수 배열을 $n \times 2^{n}$ 가지의 값을 갖는 (정수, bool 배열) 입력으로 바꾸면
  • $n$ 이 커질 수록 급격히 두 함수의 차이는 커진다
  • $n=15$ 면 250만배쯤 차이남

 1 const int MAX = 15;
 2 int n, dist[MAX][MAX];
 3 int cache[MAX][1<<MAX];
 4 
 5 // 현재 위치가 here 이고, visited 가 지금까지 방문한 도시들의 집합일 때
 6 // 남은 도시들을 방문할 수 있는 최단 경로의 길이를 반환한다
 7 int go(int here, int visited) {
 8   // 기저 사례: 전부 방문한 경우
 9   if(visited == (1<<n)-1) return 0;
10   // 메모이제이션
11   int& ret = cache[here][visited];
12   if(ret > 0) return ret;
13   ret = 987654321;
14   for(int there = 0; there < n; ++there)
15     if((visited & (1<<there)) == 0) {
16         int cand = go(there, visited + (1<<there)) +
17             dist[here][there]);
18         ret = min(ret, cand);
19     }
20   return ret;
21 }

• 질문은 빙에게 해주세요 ^ㅁ^/