Longest Common Subsequence in Dynamic Programming (3/3)

Contents

1️⃣ 이친수 구하기 (Finding Binary Numbers - Pinary Numbers)
2️⃣ 2*N 타일 채우기 (Definition and Input of 2 * n Tiling Problem)
3️⃣ 최장 공통 부분 순서 (Longest Common Subsequence, LCS)

Summary

동적 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법으로, 재귀적 접근으로 인해 함수 호출이 많이 중복될 때 최적의 해법을 제공한다. 큰 문제의 최적 해법이 작은 부분 문제들의 최적 해법을 포함하는 구조라면 동적 프로그래밍을 적용할 수 있다.

✅부분 순서 문제 (Subsequence Problems)

이친수 구하기 (Find Pinary Numbers)
- 이친수 중 특정 조건을 만족하는 수의 개수를 찾는다.
- 0으로 끝나는 이친수와 1로 끝나는 이친수를 구분하여 DP 테이블에 저장한다.
2 N 타일 채우기 (Fill 2 N Tiles)
- 2 x N 크기의 타일을 1 x 1 또는 2 x 1 타일로 채우는 방법의 수를 구한다.
- 일부 타일을 채운 경우의 방법의 수를 DP 테이블에 저장한다.
최장 공통 부분 순서 (Longest Common Subsequence)
- 두 문자열에 공통적으로 포함된 부분 순서 중 가장 긴 것을 찾는다.
- 두 문자열의 일부에 대해 최장 공통 부분 순서의 길이를 DP 테이블에 저장한다.

✅결론 (Conclusion)

동적 프로그래밍은 반복되는 부분 문제를 저장하여 효율적으로 문제를 해결하는 접근 방식이다. 이 방식을 통해 계산 속도를 향상시키고 메모리 사용을 최적화할 수 있다.

1️⃣ 이친수 구하기 (Finding Binary Numbers - Pinary Numbers)

💡요약: 이친수(Pinary Numbers)란 무엇인지 알아보자. 이친수는 0과 1로 이루어진 숫자 중, 특정 조건을 만족하는 이진수를 의미한다. 최장 공통 부분 순서를 배우기 전에, 이친수와 2*N 타일 채우기 문제를 먼저 공부할 예정이다.

✅ 이친수의 조건 (Condition of Pinary Number)

0과 1로 이루어진 이진수여야 한다.
0으로 시작하지 않는다 (Does not start with 0).
1이 연속해서 두 번 나타나지 않는다 (1 does not appear consecutively).

이 조건을 만족하면 이친수라고 한다.

💡예시

이친수 예시: 1, 10, 100, 101, 1000, 1001
이친수가 아닌 예시: 00110, 11001

이친수 구하기 #1 : 입력과 출력 (Finding Pinary Numbers - Input and Output)

💡요약: N자리 수에 대해 가능한 이친수의 개수를 구하는 문제이다. 입력은 자리 수 N이며, 출력은 해당 자리 수에 대한 이친수의 개수이다.

✅ N자리인 5의 이친수 갯수가 5개인 이유

첫 자리(왼쪽)는 항상 1로 시작한다.
1이 두 번 연속으로 나오면 안 된다. 즉, "11"은 금지이다.

✅ 가능한 5자리 이친수 나열하기

10000: 첫 자리는 1로 시작하고, 나머지는 모두 0이므로 규칙에 맞다.
10001: 첫 자리는 1로 시작하고, 중간에 1이 두 번 연속 나오지 않으므로 규칙에 맞다.
10010: 첫 자리는 1로 시작하고, 중간에 "11"이 나오지 않으므로 규칙에 맞다.
10100: 첫 자리는 1로 시작하고, 중간에 "11"이 없으므로 규칙에 맞다.
10101: 첫 자리는 1로 시작하고, 중간에 "11"이 없으므로 규칙에 맞다.

💡결론: 이렇게 5자리를 가지면서 이친수의 규칙을 모두 지키는 경우는 총 5개뿐이다. 그렇기 때문에 5자리 이친수는 총 5개가 되는 것이다. 이친수 문제는 자리 수가 커질수록 가능한 경우의 수가 점점 더 복잡해지기 때문에 동적 프로그래밍을 사용해 효율적으로 계산할 수 있습다.

이친수 구하기 #2 : 문제 분석하기 (Finding Pinary Numbers - Problem Analysis)

💡요약: 이친수의 개수를 구하는 데 필요한 요소를 설명하고, 문제 해결을 위한 분석 과정을 단계별로 나누어 알아본다.

✅자리수의 중요성

이친수의 개수를 구할 때 가장 중요한 요소는 **자리수 (Number of digits)**이다. 자리수에 따라 이친수가 가지는 모양과 개수가 결정되기 때문에 이를 기준으로 나누어 계산한다.

✅ 끝나는 숫자에 따른 구분

이친수는 0으로 끝나는 경우와 1로 끝나는 경우로 나누어 생각한다. 이러한 구분을 통해 계산의 단계를 나눌 수 있다. 예를 들어, 끝이 1인 경우 그 앞자리는 항상 0이 되며, 끝이 0인 경우 자유롭게 0 또는 1이 나올 수 있게된다.

✅ 2차원 배열 점화식 선언 (2D Array Formula Declaration)

문제를 해결하기 위해 **D[N][2]**와 같은 형태의 2차원 배열을 선언한다. 여기서 D[N][0]은 N자리 이친수 중 끝이 0인 경우의 개수를, D[N][1]은 끝이 1인 경우의 개수를 의미한다. 이렇게 하면 각 자리수마다 이친수의 개수를 효율적으로 계산할 수 있게 된다.

✅ 여러 가지 점화식 가능성 (Multiple Possible Formulas)

이친수를 구하는 점화식은 한 가지 방법으로만 구성되지 않고 다양한 방법으로 표현할 수 있다. 이는 문제 풀이 방식에 유연성을 제공하며, 여러 방식을 통해 최적의 방법을 찾을 수 있다.

이친수 구하기 #3 : 점화식 (Finding Pinary Numbers - Recursive Relations)

💡요약: 이친수의 점화식 정의와 관계를 알아본다. 이친수를 구할 때, 끝자리가 0인 경우와 1인 경우로 나누어 각 경우의 수를 어떻게 계산할 수 있는지 설명하고 있다.

✅ 점화식의 정의 (Definition of the Formula)

D[i][0]: 길이가 i이고, 0으로 끝나는 이친수의 개수이다.
D[i][1]: 길이가 i이고, 1로 끝나는 이친수의 개수이다.
이를 통해, 이친수의 자리수와 끝자리에 따라 각각의 경우의 수를 나누어 계산할 수 있다.

✅ 점화식의 관계 (Relationship of the Formula)

D[i][0] = D[i-1][0] + D[i-1][1]
길이가 i이고 끝이 0으로 끝나는 이친수는 이전 단계에서 0으로 끝나거나 1로 끝나는 경우 모두 가능하므로, 두 경우의 수를 합친다.
D[i][1] = D[i-1][0]
길이가 i이고 끝이 1로 끝나는 이친수는 이전 단계에서 0으로 끝난 경우만 가능하다. 이는 1이 연속해서 두 번 나오는 경우를 방지하기 위해서이다.

🤔위 점화식이 전하려는 핵심 메세지

이친수의 개수를 효율적으로 구하기 위해 끝자리에 따라 점화식을 정의하고 사용하는 방법이 핵심 메세지이다. 위에서 배웠듯이 이친수를 계산할 때, 0으로 끝나는 경우와 1로 끝나는 경우를 나누어 각각의 경우의 수를 다른 방식으로 계산한다. 이를 통해 중복 계산을 줄이고 조건에 맞는 이친수만을 빠르게 구할 수 있는 방식을 보여준다.

끝자리에 따른 규칙을 설정함으로써 이친수를 동적 프로그래밍 방식으로 계산할 수 있으며, 이를 통해 불필요한 계산을 피하고 효율성을 높일 수 있게 된다.
이미지에서는 0으로 끝나는 경우와 1로 끝나는 경우의 관계를 명확히 하여 이친수 계산의 논리를 시각적으로 전달하고 있다.

이친수 구하기 #4 : DP테이블 (Finding Pinary Numbers - DF Table)

💡요약: 이친수를 구하기 위해 점화식을 사용하여 DP 테이블을 채우는 방법을 알아보자. DP테이블을 사용하면 각 자리수별로 0으로 끝나는 이친수와 1로 끝나는 이친수의 개수를 저장하여 문제를 효율적으로 해결할 수 있다. 최종적으로, D[5][0] + D[5][1] = 5로, 5자리 이친수의 총 개수를 구한다.

✅ DP 테이블은 각 자리수에서 0으로 끝나는 이친수와 1로 끝나는 이친수의 개수를 저장하는 2차원 배열이다.

배열 구조:
- D[i][0]: i자리의 숫자 중 0으로 끝나는 이친수의 개수.
- D[i][1]: i자리의 숫자 중 1로 끝나는 이친수의 개수.

✅ 점화식 재설명

D[i][0] = D[i−1][0] + D[i−1][1] i자리에서 0으로 끝나는 이친수는, 이전 자리수가 0으로 끝나는 경우와 1로 끝나는 경우에서 파생된다.
D[i][1] = D[i−1][0] i자리에서 1로 끝나는 이친수는, 이전 자리수가 반드시 0으로 끝나야만 생성된다.

✅ 테이블 채우기: 이전 자리수의 값들을 기반으로 현재 자리수를 채워나가는 방식으로 이루어진다.

1자리 숫자: D[1][0]=0 1자리 숫자는 0으로 끝날 수 없다, D[1][1] = 1: 1자리 숫자는 1로만 끝날 수 있다.

✅ 테이블 채우기 (자리수가 2일 때):

D[2][0]: 2자리에서 0으로 끝나는 이친수는 이전 자리수의 D[1][0] + D[1][1]이다.
- 계산: D[2][0] = 0 + 1 = 1
D[2][1]: 2자리에서 1로 끝나는 이친수는 이전 자리수의 D[1][0]이다.
- 계산: D[2][1]=0

✅ 테이블 채우기 (자리수가 3일 때):

D[3][0]: D[3][0] = D[2][0] + D[2][1]
- 계산: D[3][0] = 1 + 1 = 2
D[3][1]: D[3][1]=D[2][0]
- 계산: D[3][1]=1

이친수 구하기 #5 : 의사코드 (Finding Pinary Numbers - Pseudocode)

💡요약: DP 테이블을 사용하여 이친수를 효율적으로 구할 수 있다. D[i][0]과 D[i][1]의 값을 이전 자리수의 값에 기반하여 계산한다. 최종적으로 D[N][0] + D[N][1]을 더해 N자리 이친수의 개수를 출력한다.

✅ D 배열의 정의: D[i][0]은 길이 i에서 끝이 0으로 끝나는 이친수의 개수를 나타내고, D[i][1]은 길이 i에서 끝이 1로 끝나는 이친수의 개수를 나타낸다.

✅N (자리수): 구하고자 하는 이친수의 자리수를 N으로 설정한다.

✅초기값 설정:

D[1][1] = 1: 1자리 이친수 중에서 끝이 1로 끝나는 이친수는 1개이다. (1)
D[1][0] = 0: 이친수는 0으로 시작할 수 없기 때문에 1자리 이친수 중 끝이 0으로 끝나는 경우는 없다.

✅반복문 (for loop): 2부터 N까지 반복하면서 DP 테이블을 채워간다.

D[i][0]: 길이 i에서 끝이 0으로 끝나는 이친수는 i-1 자리에서 끝이 0인 이친수 + 끝이 1인 이친수의 개수를 더한 것이다.
D[i][1]: 길이 i에서 끝이 1로 끝나는 이친수는 i-1 자리에서 끝이 0인 이친수의 개수이다. 이는 두 번 연속 1이 나올 수 없다는 규칙을 반영한다.

✅최종 출력: D[N][0]과 D[N][1]을 더해 N자리 이친수의 총 개수를 구한다.

2️⃣ 2N 타일 채우기 (Definition and Input of 2 n Tiling Problem)

💡요약: 2^n 크기의 직사각형을 1*2 또는 2*1 크기의 타일로 채우는 방법의 수를 구하는 문제를 알아보자. 예시로 2*5 크기의 직사각형이 다양한 타일 조합으로 채워지는 방법이 주어졌다.

✅ 문제 정의

2 * n 크기의 직사각형을 채우는 방법의 수를 구하는 프로그램을 작성해야 한다.
사용할 수 있는 타일의 크기는 1*2 타일과 2 *1 타일이다.
이 문제에서는 여러 개의 조합을 사용하여 모든 공간을 빈틈없이 채우는 방법의 수를 계산하는 것이 목표이다.

✅ 입력

첫 번째 줄에는 N의 값이 주어진다.
N은 1 이상 1000 이하의 정수이다.

✅결론

이 문제는 Dynamic Programming (동적 프로그래밍) 기법을 사용하여 해결할 수 있으며, 작은 타일을 조합하여 큰 직사각형을 채우는 방식이다.

2n 타일 채우기 #1 :출력 설명 (Output Explanation for 2 n Tiling Problem)

💡요약: 타일을 채우는 방법의 수를 구한 후에, 그 값을 10,007로 나눈 나머지를 출력하는 것이 이 문제의 핵심이다.

✅ 출력에서 중요한 부분:

방법의 수가 아주 커질 수 있기 때문에, 우리가 구한 방법의 수를 10,007로 나눈 나머지만 출력한다. 이렇게 하는 이유는, 숫자가 너무 커지면 다루기가 어렵기 때문에 적당한 크기로 유지하려는 것이 목적이다.
결과값을 10,007로 나눈 나머지만 남기는 것은 단순히 계산 결과가 너무 크지 않도록 조절하기 위한 "일종의 규칙"이라고 생각하면 된다. 그래서 최종 답은 항상 10,007보다 작은 숫자가 되게된다.

✅ 예제 설명:

`예제 1`

입력: N = 9 (2 * 9 크기의 직사각형을 채우는 방법을 찾으라는 뜻)
채울 수 있는 방법의 수는 계산해보면 총 55가지이다.
그런데 55를 10,007로 나눈 나머지는 55가 된다(10,007보다 작아서 그대로 55가 남음).
출력: 55

`예제 2`

입력: N = 2 (2 * 2 크기의 직사각형을 채우는 방법을 찾으라는 뜻)
채울 수 있는 방법의 수는 계산해보면 총 2가지가 된다.
이 2를 10,007로 나눈 나머지는 그대로 2이다.
출력: 2

2n 타일 채우기 #2 :문제 분석 (Problem Analysis for 2 n Tiling Problem)

💡요약: 2N 크기의 직사각형을 1*2 또는 2*1 크기의 타일로 채우는 경우의 수를 점화식을 통해 정의하는 내용을 알아본다. 이를 해결하기 위해 어떻게 접근하는지를 단계별로 설명한다.

✅ 점화식 정의 (Define Recurrence Formula): 2 X N 크기의 직사각형을 1 X 2 또는 2 X 1 크기의 타일로 채우는 경우의 수를 구하는 점화식 D[N]을 정의한다.

여기서 **D[N]**은 N 길이의 2*N 직사각형을 채우는 경우의 수를 의미한다. 예를 들어, 길이가 2일 때와 3일 때의 경우의 수를 구한 결과를 바탕으로 점차 길이를 늘려가며 전체 경우의 수를 찾아낼 수 있다.

✅ 누적 접근법 (Cumulative Approach): 1부터 N-1 크기에 직사각형과 관련된 경우의 수를 모두 구해 놓았다고 가정하고 문제에 접근한다.

이 문제는 작은 크기의 경우의 수를 구한 후 점점 큰 크기로 확장해가며 계산하는 방식이다. 처음부터 모든 경우의 수를 구하기보다는, N이 증가하면서 작은 문제를 해결해가는 방식으로 접근한다.

2n 타일 채우기 #3 : 점화식 (Recursive Relations for 2 n Tiling Problem)

💡요약: 2*N 크기의 직사각형을 채우기 위해 사용하는 점화식 D[N] = D[N−1] + D[N−2]의 원리를 설명한다. N 길이의 직사각형을 타일로 채우는 경우를 N-1과 N-2 길이에서 타일을 추가하는 방식으로 나눠서 생각한다.

✅점화식의 기본 원리 (Basic Principle of the Recurrence Formula):

2*N 크기의 직사각형을 채우는 경우의 수를 D[N]이라 한다.
D[N]을 구하는 방법은 두 가지 경우로 나눌 수 있다:
1. N-1 길이까지 타일이 채워진 경우:이 경우, 세로로 된 1 * 2 타일 하나를 추가하여 N 길이를 채울 수 있다.
2. N-2 길이까지 타일이 채워진 경우: 이 경우, 가로로 된 2 * 1 타일 두 개를 추가하여 N 길이를 채울 수 있다.

✅ 점화식 구성 (Formation of Recurrence Formula):

N 길이를 채우는 경우는 이 두 가지 경우의 수를 합친 것이다.
따라서, **D[N] = D[N-1] + D[N-2]**가 된다. 이는 N-1과 N-2에서의 경우의 수를 합쳐서 N 길이를 채우는 경우의 수를 계산하는 방식이다.

✅중복 방지 (Avoiding Duplicates):

N-2 길이에서 세로 타일 2개를 사용해 N 길이를 채우는 방법은 N-1 길이 경우에 이미 포함되었으므로 중복을 방지한다.

2n 타일 채우기 #3 : DP테이블 (DP Table for 2 n Tiling Problem)

💡요약: 2*N 타일 문제를 해결하기 위해 동적 프로그래밍(DP) 테이블을 채우는 과정을 알아보자. DP 테이블에서 각 칸은 타일을 채울 수 있는 경우의 수를 나타내며, 점화식 D[N]=D[N−1]+D[N−2]을 사용하여 테이블을 채워나간다.

✅DP 테이블의 역할 (Role of DP Table):

DP 테이블은 각 길이 N에서 타일을 채울 수 있는 방법의 수를 저장한다.
예를 들어, 길이가 3일 때 D[3] = D[2] + D[1] = 3이라는 값이 저장된다.

✅점화식 적용 (Applying Recurrence Formula)

각 칸의 값은 이전 두 칸의 값을 더하여 계산된다.
예를 들어, D[3]는 D[2] + D[1] = 2 + 1 = 3 으로 계산된다. 같은 방식으로 D[4], D[5] 등도 계산된다.

✅ 최종 값 계산 (Final Value Calculation):

원하는 길이의 경우의 수를 구하려면, 해당 길이의 칸을 참조합니다.
예를 들어, 길이 9의 경우의 수는 D[9] = 55 이다.

✅모듈 연산 (Modulo Operation):

문제의 조건에 따라, 결과를 10,007로 나눈 나머지를 저장한다.
이렇게 하면 큰 숫자를 다룰 때 오버플로우를 방지할 수 있다.\

2n 타일 채우기 #4 : 의사코드 (Pseudocode for 2 n Tiling Problem)

💡요약: 2*N 크기의 직사각형을 1*2 또는 2*1 타일로 채우는 경우의 수를 동적 프로그래밍(DP)으로 구하는 의사코드를 알아본다. 각 길이에 따라 타일을 채우는 방식의 수를 계산하여 DP 테이블에 저장하는 방법을 설명한다.

✅모듈로 연산 (Modulo Operation) 설정

결과가 너무 커질 수 있으므로, 출력 값이 10,007로 나눈 나머지로 표현되도록 설정

✅초기 값 설정 (Initial Values)

길이가 2*1일 때 채울 수 있는 방법은 1가지(세로 타일 1개)이다.
길이가 2*2일 때 채울 수 있는 방법은 2가지(세로 타일 2개 또는 가로 타일 2개)이다.

✅점화식 적용 (Applying the Recurrence Formula)

길이 N을 채우는 방법의 수는 길이 N-1을 채우는 방법에 세로 타일을 추가하는 경우와, 길이 N-2을 채우는 방법에 가로 타일 2개를 추가하는 경우의 합이다. 이를 점화식으로 풀면 아래와 같다.
점화식: D[i] = D[i−1] + D[i−2]

✅ 결과 출력 (Output the Result)

최종적으로 D[N] 값이 우리가 원하는 결과가 된다.
결과는 항상 10,007로 나눈 나머지로 표현한다.

2n 타일 채우기 #5 : 파이썬 코드 (Python for 2 n Tiling Problem)

✅모듈로 설정 mod = 10007: 너무 큰 숫자가 나오는 것을 방지하기 위해 결과를 10,007로 나눈 나머지를 저장한다.

✅입력값 설정 N = int(input()): 사용자로부터 직사각형의 길이 N을 입력받는다.

✅DP테이블 초기화 D = [0]*(1001)

D라는 리스트를 만들어, 각 길이에 따른 경우의 수를 저장할 공간을 확보한다.
문제 조건에서 N≤1000 이므로 리스트의 크기를 1001로 설정하였다.

✅기본 값 설정 D[1] = 1 D[2] = 2

D[1] 과 D[2] 의 값을 기본으로 설정한다.
- D[1] = 1 : 길이가 2*1일 때는 세로 타일 1개로 채울 수 있다.
- D[2] = 2: 길이가 2*2일 때는 세로 타일 2개 또는 가로 타일 2개로 채울 수 있다.

✅점화식 계산

for i in range(3, N + 1):
    D[i] = (D[i - 1] + D[i - 2]) % mod

길이가 3부터 N까지의 경우의 수를 반복문을 통해 계산한다.
점화식: D[i] = D[i−1] + D[i−2]
길이 N을 채우는 방법은 길이 N-1N−1을 채운 뒤 세로 타일을 추가하는 경우와 길이 N-2를 채운 뒤 가로 타일 2개를 추가하는 경우로 나뉜다.
결과는 항상 10,007로 나눈 나머지로 저장된다.

✅결과 출력 print(D[N]) 최종적으로 D[N]의 값을 출력한다. 이는 주어진 길이 N의 직사각형을 채울 수 있는 모든 경우의 수이다.

3️⃣ 최장 공통 부분 순서 (Longest Common Subsequence, LCS)

💡요약: 두 문자열에 공통으로 포함된 부분 순서 중 가장 긴 것을 찾는 최장 공통 부분 순서 (LCS) 를 알아본다.

문자열이 연속할 필요는 없지만 순서는 같아야 한다.

✅문제 목표:

두 문자열에서 공통적으로 들어있는 부분 순서 중 가장 긴 것을 찾는 것이 목표이다.
여기서 **부분 순서 (subsequence)**는 문자열에서 연속하지 않아도 되는 순서를 의미한다.

✅부분 순서의 예시:

예를 들어, 문자열 <abcbdab>에서 <bcdb>는 부분 순서이다.
여기서 문자들은 연속할 필요가 없지만, 순서가 동일해야 한다.

✅ 공통 부분 순서의 예시:

두 문자열 <abcbdab>와 <bdcaba>의 공통 부분 순서 중 하나는 <bca>이다.

✅최장 공통 부분 순서 (Longest Common Subsequence, LCS):

두 문자열 간의 공통 부분 순서 중 가장 긴 것을 LCS라고 한다.
예를 들어, <abcbdab>와 <bdcaba>의 최장 공통 부분 순서는 <bcba>이다.

최장 공통 부분 순서 #1: 최적 부분 구조 설명 (Longest Common Subsequence, LCS)

💡요약: 이 세 가지 경우를 통해 최장 공통 부분 순서 문제를 재귀적으로 해결할 수 있다. 작은 문제의 해법이 전체 큰 문제의 해법에 포함되는 구조라서, 이 문제를 동적 프로그래밍으로 효율적으로 해결할 수 있다.

두 문자열 X_m Y_n의 최장 공통 부분 순서 (LCS)를 구하는 방법을 설명하고 있다. 최장 공통 부분 순서의 길이를 k라고 할 때, 이 LCS는 여러 개가 있을 수 있다. 그중 하나를 Z_k로 정의한다. 이미지가 전하려는 내용은, 작은 문제의 해답이 큰 문제의 해답에 포함되는 구조를 통해 동적 프로그래밍을 적용할 수 있다는 점이다. 이를 위해, 세 가지 경우로 나누어 LCS의 구조를 분석한다.

✅첫 번째 경우: xm = yn인 경우

- 이때, zk = xm = yn 이며, Zk−1 은 Xm−1과 Yn−1의 LCS이다.
  - 즉, 두 문자열의 마지막 문자가 같으면, 이 마지막 문자를 포함한 상태에서 나머지 부분 문자열의 LCS를 구하면 된다.

✅두 번째 경우: xm ≠ yn 이고 zk ≠ xm인 경우

- 이 경우, Zk는 Xm−1과 Yn의 LCS이다.
  - 즉, 첫 번째 문자열의 마지막 문자를 제외한 나머지와 두 번째 문자열의 LCS를 구하면 된다.

✅세 번째 경우: xm ≠ yn 이고 zk ≠ yn 인 경우

- 이 경우, Zk는 Xm과 Yn−1의 LCS이다.
  - 즉, 두 번째 문자열의 마지막 문자를 제외한 나머지와 첫 번째 문자열의 LCS를 구하면 된다.

💡결론: 두 문자열의 LCS를 구할 때, 마지막 문자의 관계에 따라 작은 문제로 쪼개어 해결하는 방법을 설명하였다. 이를 통해 동적 프로그래밍을 적용할 수 있는 최적 부분 구조가 형성되게 된다.

최장 공통 부분 순서 #2: 최적 부분 구조 설명 (Longest Common Subsequence, LCS)

💡요약: 최장 공통 부분 순서를 구하기 위해 사용하는 세 가지 경우의 점화식을 알아보자. 이를 통해 DP 테이블을 채워 나가면서 최종적으로 LCS의 길이를 구할 수 있게된다.

첫 번째 경우 (First Case): 하나의 문자열이 비어 있으면 공통 부분의 길이는 0.
두 번째 경우 (Second Case): 현재 문자가 같다면, 이전 공통 부분 길이에 1을 더함.
세 번째 경우 (Third Case): 현재 문자가 다르면, 이전 두 값 중 큰 값을 사용함.

✅ 첫 번째 경우 (First Case): i = 0 또는 j = 0인 경우

설명: 이 경우는 첫 번째 문자열이나 두 번째 문자열 중 하나가 빈 문자열일 때이다.
값: c_ij = 0으로 설정한다.
이유: 공통 부분이 없으므로 길이는 0가 된다.

✅두 번째 경우 (Second Case): i, j > 0이고 x_i = y_j인 경우

설명: 두 문자열의 현재 문자가 같을 때 발생한다.
값: c_ij = c_{i-1, j-1} + 1
이유: 현재 문자가 같으므로, 이전까지의 공통 부분 길이에 1을 더한다.

✅세 번째 경우 (Third Case): i, j > 0이고 x_i ≠ y_j인 경우

설명: 두 문자열의 현재 문자가 다를 때 발생한다.
값: c_ij = max(c_{i-1, j}, c_{i, j-1})
이유: 문자가 다르므로, 이전 단계에서 얻은 공통 부분 길이 중 큰 값을 선택한다.

최장 공통 부분 순서 #3 재귀를 사용한 의사코드 (Longest Common Subsequence - Recursive Pseudocode)

💡요약: 두 문자열의 최장 공통 부분 순서(LCS)를 구하는 재귀적 접근 방식을 알아보자. 이 코드의 핵심은 LCS의 길이를 구하기 위해 문자열의 각 문자들을 하나씩 비교하며, 경우에 따라 재귀적으로 함수를 호출하는 것이다. 하지만 **"엄청난 중복 호출이 발생한다"**는 점이 문제이다.

빈 문자열이 포함된 경우 (If there is an empty string): LCS 길이는 0
현재 문자가 같을 경우 (If current characters are the same): 이전 단계의 LCS 길이에 1을 더한다.
현재 문자가 다를 경우 (If current characters are different): 두 가지 경우의 결과 중 더 큰 LCS 값을 선택한다.

✅LCS(m, n) 문자열 X의 m번째 문자와 문자열 Y의 n번째 문자를 비교하면서 최장 공통 부분 순서의 길이를 재귀적으로 계산하는 함수이다.

✅if (m = 0 or n = 0) return 0 m 또는 n이 0이면, 두 문자열 중 하나가 빈 문자열이므로 공통 부분이 없음을 나타내며 0을 반환한다. 하나의 문자열이라도 빈 문자열이 되면, 더 이상 비교할 문자가 없기 때문이다.

✅else if (x_m = y_n) return LCS(m - 1, n - 1) + 1 x_m이 y_n과 같으면, 현재 문자가 같다는 의미이므로, LCS(m-1, n-1) 결과에 1을 더해 반환한다. 두 문자가 같으므로, 공통 부분 순서의 길이가 1 증가하게 된다. 그 전 단계까지의 LCS 길이에 1을 더하여 업데이트한다.

✅else return max(LCS(m - 1, n), LCS(m, n - 1)) x_m이 y_n과 다를 경우, LCS(m - 1, n)과 LCS(m, n - 1) 중 더 큰 값을 선택해 반환한다. 문자가 다르면, 두 가지 선택지가 있다. X의 이전 문자까지와 Y를 비교하거나, X와 Y의 이전 문자까지 비교하는 것이다. 이 두 가지 중 큰 값을 선택한다

최장 공통 부분 순서 #4 : 중복 호출 트리 (Longest Common Subsequence - Call Tree with Redundant Calls)

LCS(3,4)는 전체 문자열의 LCS를 구하기 위한 호출이다. 이 호출은 더 작은 하위 문제들로 나뉘어지고, 각 하위 문제는 재귀적으로 또 다른 하위 문제를 호출하게 된다.
트리에서 파란색 상자(LCS(1,1))로 강조된 부분이 바로 중복된 호출이다. 이 호출은 여러 경로를 통해 반복적으로 계산되고 있다.
예를 들어, LCS(1,1)은 LCS(3,4), LCS(2,3), LCS(3,3) 등 여러 경로에서 호출된다. 그러나 동일한 결과를 반환하는 동일한 호출이므로 한 번만 계산해도 충분하다.
이러한 중복 호출은 재귀적 접근의 비효율성을 초래하게 된다. 특히, 두 문자열의 길이가 길어질수록 중복된 계산이 급격히 증가하여 시간 복잡도가 커지게 된다.

💡해결법 이러한 중복 호출 문제를 해결하기 위해선 동적 프로그래밍(DP)을 적용하면 된다. DP는 이미 계산된 결과를 저장(메모이제이션)하여 같은 부분 문제를 반복적으로 계산하지 않도록 한다. 이를 통해 효율성을 크게 향상시킬 수 있게 된다.

최장 공통 부분 순서 #5 : DP 의사코드(Longest Common Subsequence - Pseudocode)

💡요약: 동적 프로그래밍을 사용하여 LCS를 구할 때의 반복되는 중복 계산을 줄이고, 효율적으로 답을 구하는 방식을 알아보자. 2차원 테이블 C를 사용하여 두 문자열의 각 위치에 대한 LCS 길이를 저장함으로써, 재귀적 호출에서 발생하는 중복 계산을 방지한다.

기본 설정
```
  for i ← 0 to m
      C[i, 0] ← 0
  for j ← 0 to n
      C[0, j] ← 0
```
- 두 문자열의 LCS를 계산하기 위해 2차원 DP 테이블 C를 초기화한다.
- 첫 번째 행(C[i, 0])과 첫 번째 열(C[0, j])은 모두 0으로 설정한다. 이는 한 문자열이 길이가 0일 때, LCS의 길이가 0이라는 것을 의미한다.
메인 루프
```
  for i ← 1 to m
      for j ← 1 to n
```
- 각 문자 비교를 위해 두 중첩 반복문을 사용한다. i와 j는 각각 두 문자열의 인덱스를 나타낸다.
문자 비교 및 값 설정
```
  if (x_i = y_j)
      C[i, j] ← C[i-1, j-1] + 1
  else
      C[i, j] ← max(C[i-1, j], C[i, j-1])
```
- 만약 두 문자열의 현재 문자가 같다면, 이전까지의 LCS 길이에 1을 더해 현재 C[i, j] 위치에 저장한다.
- 만약 문자가 다르다면, 이전 값들 중 큰 값을 선택하여 C[i, j]에 저장한다. 즉, max(C[i-1, j], C[i, j-1])를 통해 현재 위치에서의 최장 공통 부분 순서를 구한다.
결과 반환
```
  return C[m, n]
```
- 최종 결과는 DP 테이블 C[m, n]에 저장된 값으로, 이는 두 문자열의 최장 공통 부분 순서의 길이이다.

Longest Common Subsequence in Dynamic Programming (3/3)

Summary

1️⃣ 이친수 구하기 (Finding Binary Numbers - Pinary Numbers)

💡예시