[11053] 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

 

www.acmicpc.net

---

🤔 문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

🤨 제한 사항

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

😀 입출력 예

입력	결과
6 10 20 10 30 20 50	4

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
split()	문자열을 나눠서 배열로 반환합니다.
map()	리스트의 요소를 지정된 함수로 처리합니다.
list()	리스트를 만듭니다.
range()	간단히 정수 범위를 표현할 수 있습니다.
max()	매개변수로 들어온 인자값 중 최대값을 반환합니다.

 

👩‍🏫 어떻게 풀어요?

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

저는 문제 제대로 안 읽었다가, 입력 값을 전부 set으로 받아서 다시 정렬하는 대참사를 발생 시켰습니다. 😭

해당 문제는 얼핏 보면 동적 프로그래밍을 사용하지 않는 것처럼 보이지만,

사실은 동적 프로그래밍 기법을 사용하는 문제입니다!

차근차근 한 단계씩 살펴보면서 이 문제가 어떻게 동적 프로그래밍을 사용하고, 해결해야 하는지를 한번 보겠습니다.

 

1 단계

	[0]	[1]	[2]	[3]	[4]	[5]
A[]	10	20	10	30	20	50
memo[]	1	1	1	1	1	1

먼저 생각을 해봅시다 ! (Let's Thinking)

A의 각 숫자는 이전의 가장 긴 수열보다 짧다면 전부 1의 값을 가지고 있을겁니다. 최초에는 그런 수열은 존재하지 않으니까 모든 숫자가 1의 값을 갖겠죠?

그렇다면 메모(메모이제이션) 배열에 그 경로값을 기억하게 초기화 해줍시다.

 

2 단계

	[0]	[1]	[2]	[3]	[4]	[5]
A[]	10	20	10	30	20	50
memo[]	1	2	1	1	1	1

초기화도 했다면 하나씩 경로를 구해야겠죠?

먼저, A[0]에 존재하는 10은 어차피 첫번째이고 memo[0]도 1로 초기화 됐으니 볼 필요가 없습니다. 그러니까 패스!

A[1]부터 보도록 하겠습니다. 그 이전 배열은 A[0]만 존재 하므로 A[0]의 값만 A[1]과 비교해 버리면 되겠죠?

10 < 20 이기 때문에 memo[1]은 1을 더해서 2로 만들어 줍시다.

 

3 단계

	[0]	[1]	[2]	[3]	[4]	[5]
A[]	10	20	10	30	20	50
memo[]	1	2	1	1	1	1

그 다음은 A[2]와 이전 값들을 비교해 보겠습니다.

10 < 10 이니까 변화가 없고, 20 < 10 이니까 변화가 없습니다. 그러면 다음 배열로 넘어가 봅시다.

 

4 단계

	[0]	[1]	[2]	[3]	[4]	[5]
A[]	10	20	10	30	20	50
memo[]	1	2	1	2	1	1

다음은 A[3]와 이전 값들을 비교해 보겠습니다.

10 < 30 이니까 경로를 1 증가시켜줘야 겠네요!!

	[0]	[1]	[2]	[3]	[4]	[5]
A[]	10	20	10	30	20	50
memo[]	1	2	1	3	1	1

20 < 30 이니까 이번에도 경로를 증가시켜 줘야겠죠?

마지막으로 10 < 30 이니까 경로를 증가시킬 필요가 없으므로 해당 반복은 여기서 종료합니다.

 

 

😵 유도

그런데 혹시 눈치 채셨나요? 단순히 이전단계의 배열들 값들을 비교하는 것으로 동적 프로그래밍을 구현할 수 있다는 것을요. 

한번 다시 볼게요.

우린 1단계에서 A[0]은 어차피 기본경로도 1로 초기화 되어 있어서 볼필요가 없음을 봤어요.

그리고 2단계에서는 A[1]을 이전 배열값들과 비교하며 memo[1]의 크기를 늘렸고요.

그렇다면,

 

memo = [1 for _ in range(입력받은 크기)]
 
for i in range(1, len(A)) :
 
    for j in range (0, i) :

 

이렇게 2중 for문을 작성하되, i는 1 ~ A 배열 크기 직전 까지 돌리고, j는 0 ~ i의 직전까지 돌리면 위의 단계를 차례대로 비교할 수 있겠죠? for문 바깥에는 memo를 입력받은 크기만큼 1로 초기화를 해주고요.

그 다음,

 

memo = [1 for _ in range(입력받은 크기)]
 
for i in range(1, len(A)) :
 
    for j in range (0, i) :
 
        if A[j] < A[i] :
 
            memo[i] = max (memo[i], memo[j] + 1)

 

2중 반복으로 돌아가면서 현재 선택된 A 배열 이전의 값들을 차례대로 비교하며 큰 경우에는

memo[i]에 max를 사용하여 현재 선택된 배열의 memo값과 이전 단계에 해당하는 memo 배열값을 비교하고 가장 큰 숫자를 넣습니다.

 

위의 4단계 예시를 보시면 

10 < 30 이랑 비교해서 30이 더 크기 때문에 10의 memo에 해당하는 1에 + 1한 값과 30의 memo에 해당하는 1을 비교하여 2를 집어 넣는것이 max 과정을 거쳐서 그렇습니다.

 

+1을 추가로 하는 이유는, 어쨋든 이전 A배열 값이 현재 A값 보다 작다면 점점 커지는 수열이 존재함을 나타내야 하고, 배열 값 각각 1개씩을 비교하기 때문에 더도 말고 덜도 말고 1을 증가시켜주는 것입니다.

 

 

😫 아니 그래서 이게 왜 동적 프로그래밍(DP) 인데요?

이게 왜 동적 프로그래밍이냐고 의문을 가지는 분들이 계실거에요.

 

왜냐하면 대표적인 동적 프로그래밍 문제인 피보나치 수열 같은 경우

fib(4) = fib(3) + fib(2)

이런식으로 알고리즘이 되어 있고, 모든 값을 뒤지지 않고 미리 메모이제이션에 저장한 값을 꺼내서 빠르게 연산하는 문제였기 때문이죠.

 

그래서 가장 긴 증가하는 부분 수열은 피보나치 수열과는 다르게 그런 부분이 없는 것처럼 보입니다.

하지만 우리는 이미 max()에서 해당 부분을 만족했답니다.

피보나치 수열	fib(n) = fib(n-1) + fib(n-2)
가장 긴 증가하는 부분 수열	memo(i) = max(memo[i], memo[j] + 1)

위의 4단계에서 20 < 30 일때 max는 max(2, 2 + 1) 이런식으로 나타나 있을거에요. 우리는 2단계에서 구했던 20의 memo값 덕분에 2 + 1을 얻을 수 있었죠. 메모리를 사용하여 이전 값을 저장하고 꺼내 썻기 때문에 이 문제를 동적 프로그래밍 기법으로 풀 수 있는 것이랍니다.

 

👾트리스티의 답

1 2 3 4 5 6 7 8 9 10 11 12

import sys   n = int(sys.stdin.readline().split()[0]) a = list(map(int, sys.stdin.readline().split()))   memo = [1 for _ in range(n)] for i in range(1, len(a)) :     for j in range(0, i) :         if a[j] < a[i] :             memo[i] = max(memo[i], memo[j] + 1)   print(max(memo)) Colored by Color Scripter

cs

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!