# 다이나믹 프로그래밍 2

DP를 활용하는 다양한 문제유형이 있는데요, 같이 한 번 알아볼까요?

📌**최장 증가 부분 수열(LIS, Longest Increasing Subsequence)**

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

* 예를 들어, { 6, **2**, **5**, 1, **7**, 4, **8**, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이 됩니다.
* { 2, 5 }, { 2, 7 } 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 { 2, 5, 7, 8 } 입니다.

{% embed url="<https://www.acmicpc.net/problem/11053>" %}

첫번째 인덱스부터 수열의 길이의 최댓값을 저장해 나갑니다.\
수열 a = {10, 20, 10, 30, 20, 50}이 있을 때, 4번째 숫자(30)까지의 수열의 길이의 최댓값을 구해봅시다.

첫번째 숫자부터 검사를 해 나갑니다.\
자기 자신(30)보다 작은 숫자들 중 가장 큰 길이를 구하고 그 길이에 +1을 하면 됩니다.

| 수열 | 10 | 20 | 10 | 30 | 20 | 50 |
| -- | -- | -- | -- | -- | -- | -- |
| 길이 | 1  | 2  | 1  | 3  | 2  | 4  |

```python
x = int(input())

arr = list(map(int, input().split()))
dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
        #증가하기만 하면 일단 갱신시켜본다.
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))
```

위 LIS 성질을 이용해 아래 문제를 풀어봅시다.

{% embed url="<https://www.acmicpc.net/problem/14002>" %}

LIS 규칙에 따르면 가장 긴 길이는 앞에서 나온 수에 +1을 하였음을 알 수 있습니다. \
따라서 위 표에서 맨 뒤부터 추적하여 LIS 값인 4부터 시작하여 4, 3, 2, 1을 차례대로 추적하면 됩니다.

```python
n=int(input())
A=list(map(int,input().split()))
#LIS 로직
dp=[1]*n
for i in range(1,n):
    for j in range(i):
        if A[i]>A[j]: dp[i]=max(dp[i],dp[j]+1)


ans=[]

std=max(dp) 
print(std)

for i in range(n-1,-1,-1):
        if dp[i]==std:
            ans.append(A[i])
            std-=1

for i in ans[::-1]:
    print(i,end=' ')

```

📌**최장 공통 부분수열(LCS, Longest Common Subsequence)**

**공통 부분 문자열 중 가장 길이가 긴 문자열**을 말합니다. 이 때, 전체 문자열에서 **꼭 연속된 문자열일 필요는 없습니다.**

* 예를 들어 ABCDEF 와 ACDGHI 와의 **공통 Subsequence 중 가장 길이가 긴 것은 A**B**CD**EF / **A**ZG**CD**GHI 에서 **ACD** 입니다.

{% embed url="<https://www.acmicpc.net/problem/9251>" %}

문제에 나온 ACAYKP, CAPCAK의 예시를 들어봅시다..\
앞에 나온 문자를 S1, 뒤에 나온 문자를 S2라고 합시다.

일단 S1을 기준으로 비교합니다. S1의 A 과 S2의 C, CA, CAP, CAPC, CAPCA, CAPACAK 를 비교한 후 S1을 하나 늘려 비교하기 시작합니다. S1의 AC와 ...\
이 과정을 S1이 끝날 때까지 반복합니다.&#x20;

이 때 DP 테이블을 채우는 과정은 다음과 같습니다.\
S1의 A와 S2를 비교하는 과정을 볼까요?

\
S1\[0]과 S2\[0]은 달라 0입니다.

S1\[0]과 S2\[1]은 A로 같기 때문에 1을 증가해줍니다.

S1\[0]과 S2\[2]는 다릅니다. 이럴 경우에도 여전히 A와 CAP의 공통부분은 1개이므로, 1로 유지합니다.

|   | C | A | P | C | A | K |
| - | - | - | - | - | - | - |
| A | 0 | 1 | 1 | 1 | 1 | 1 |

...\
이런 규칙을 계속 따라 나가다 보면

다음 표와 같은 결과가 나옴을 알 수 있습니다.

|   | C | A | P | C | A | K |
| - | - | - | - | - | - | - |
| A | 0 | 1 | 1 | 1 | 1 | 1 |
| C | 1 | 1 | 1 | 2 | 2 | 2 |
| A | 1 | 2 | 2 | 2 | 3 | 3 |
| Y | 1 | 2 | 2 | 2 | 3 | 3 |
| K | 1 | 2 | 2 | 2 | 3 | 4 |
| P | 1 | 2 | 3 | 3 | 3 | 4 |

```python
A=input()
B=input()
dp=[[0]*1001 for _ in range(1001)]

ans=0
for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1]==B[j-1]: dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        ans=max(ans, dp[i][j])
print(ans)
```

📌**KNAPSACK(14863)** 보류 -고난이도 토스에서 한 번

## 풀어볼 문제

{% embed url="<https://www.acmicpc.net/problem/1915>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://koalas-organization.gitbook.io/koala_codingtest_study/greedy_and_dp/dp2.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.