[백준 11053, 11054번] 가장 긴 증가하는 & 바이토닉 부분 수열

원본 링크

가장 긴 증가하는 부분 수열: https://www.acmicpc.net/problem/11053
가장 긴 바이토닉 부분 수열: https://www.acmicpc.net/problem/11054

Intro

이번에도 다시 돌아온 다이나믹 프로그래밍문제이다.
재밌는 것은, 11053번 문제를 풀게 되면, 약간의 눈칫밥(?)으로 11054번도 풀 수 있다는 것이다!
따라서, 여기서 두 개의 문제를 묶어서 소개하려 한다.

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

문제

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

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

입력

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

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

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

주 알고리즘 분류

• 다이나믹 프로그래밍

나만의 풀이

처음 봤을 땐 이거 어찌 풀어야하나 하고 고민했다. (역시 DP)
직관적으로는 그냥 이중 for loop 돌아서 무작정 찾을까 하는 생각도 했다.
물론 시간 측면에서 망해버릴 것이 뻔하므로... 조금 더 고민했다.

그래도 마땅히 기발한 방법이 떠오르지 않아서 힌트를 찾아보고 있었다.
그런데, 힌트에서도 사실 이중 for loop는 기본적으로 사용하고 있었다.
따라서 이중 루프문을 써서 코드를 짜니 어찌 풀리긴 했다.

일단, 기본적인 구조는 다음과 같다.
먼저 cntDP라는 메모이제이션용 리스트를 지정해주자.
이제, i번째 원소를 마지막으로 하는 수열의 최대 길이 cntDP[i]를 구해주면 된다.
단순히 생각하면, i번째 원소 이전의 j번째 원소와 비교해서, 차이가 있는 경우만 갱신을 하면 된다.
이때, 기존의 i번째 값과, j번째 값에 +1한 경우 중 큰 값을 넣으면 된다.
즉, cntDP[i] = max(cntDP[i], cntDP[j]+1)가 될 것이다.

코드로 구현하면 다음과 같이 만들 수 있다.

n = int(input())
a = list(map(int, input().split()))

cntDP = [1] * n

for i in range(n):  # 마지막 loop
    for j in range(i):  # 처음부터 그 직전까지 비교
        if a[j] < a[i]:  # 만일 원소간의 차이가 존재 시
            cntDP[i] = max(cntDP[i], cntDP[j]+1)  # 갱신

print(max(cntDP))

조금 더 찾아보니까 O(nlogn)으로 줄이는 방법도 있었다.
이진 탐색을 적절히 이용하면 위 복잡도로 줄일 수 있었다 나와있다.
여기서는 생략하지만 필요하면 찾아보기 바란다.

11054번; 가장 긴 바이토닉 부분 수열

문제

수열 S가 어떤 수 S_k를 기준으로 S_1 < S_2 < ... S_(k-1) < S_k > S_(k+1) > ... S_(N-1) > S_N을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

힌트

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

주 알고리즘 분류

• 다이나믹 프로그래밍

나만의 풀이

앞선 문제를 이해했으면, 이 문제를 금방 풀 수 있다.
여기선, 이론적인 접근에서 코드 순서로 구현하는 것이 아닌, 반대로 코드먼저 볼 생각이다 (!)

먼저 전체 코드는 다음과 같다.

n = int(input())
a = list(map(int, input().split()))

cntDP = [1] * n
crtDP = [1] * n

# 11053을 변형
for i in range(n):  
    for j in range(i):  
        if a[j] < a[i]:  
            cntDP[i] = max(cntDP[i], cntDP[j]+1)  # 갱신
        J, I = n-1-j, n-1-i
        if a[J] < a[I]:  # 역순 접근
            crtDP[I] = max(crtDP[I], crtDP[J] + 1)  # 갱신

# 최종 값을 찾는 과정
maxval = 0
for a, b in zip(cntDP, crtDP):
    if maxval < a+b: maxval = a+b
print(maxval-1)

앞선 코드랑 비교해보면 몇몇 달라진 점이 있다.
우선, crtDP라는 대충 이름 지은 리스트가 하나 추가됐다.
이게 있는 이유는, 역순으로 크기를 비교할 생각이기 때문이다.
아까, 바이토닉 부분 수열의 경우, 증가하는 경우 외에도 감소하는 경우도 생각해야 한다.
따라서, 일단 역순으로 앞선 과정을 수행해봤다.

역순 접근을 위해 기존의 loop에서 J와 I라는 값을 지정하고, 동일한 구조로 코드를 짰다.
따라서, crtDP에는 입력 data를 뒤집었을 때 가장 긴 증가하는 부분 수열을 찾기 위한 data로 할당될 것이다.
이후, 인사이트를 찾기 위해서 일부러 cntDP와 crtDP를 나란히 출력해봤다.
그런데, 앞선 예제 입력 기준으로 이런 결과를 얻었다.

[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
[1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

앞서 예제에서 7이라는 결과가 나온다는 사실을 알 수 있고, 예제에 의해 {1 5 2 1 4 3 4 5 2 1}라는 숫자가 선택됨을 우리는 알고 있다.
위 경우랑 대조해보면, 수열의 가장 꼭대기(중심)가 되는 '5'라는 원소가 뒤에서 3번째에 존재하는 사실을 알 수 있다.
그런데, 위 배열에서 해당 값들을 더하면 '8'이라는 값이 나온다.
여기서 1을 뺀 값이 7이 됨을 알 수 있다.

....이런 야매스러운 감각적인 접근법이 진짜인가 하고 가상의 테스트 케이스를 만들어서 검증해봤는데...

# 입력
20
1 1 2 1 3 3 1 4 2 3 1 5 1 2 4 1 1 2 1 1

# 정답 출력
8

# cntDP와 crtDP의 출력
[1, 1, 2, 1, 3, 3, 1, 4, 2, 3, 1, 5, 1, 2, 4, 1, 1, 2, 1, 1]
[1, 1, 2, 1, 3, 3, 1, 4, 2, 3, 1, 4, 1, 2, 3, 1, 1, 2, 1, 1]

가장 꼭대기에 해당되는 '5'를 기준으로 5 + 4 - 1 = 8로 계산되는 것을 확인했다.
머리로는 이해가 안 됐는데, 일단 본능적으로 코드를 짜고 제출해봤다.
.... 통과했다. (????????????????????)

오히려 너무 잘 풀린 덕에 문제가 생겼다.
코드는 완성했는데, 이해를 하지 못해서 머리를 앓고 있었다.
그리고 왜 이러한 방식이 맞았는지 조사도 해보고 생각도 해본 결과, 다행히도 원리를 알아내었다.
이제, 역으로 이론적인 내용을 설명하겠다.

앞선 문제에선 부분적으로 증가하는 수열을 구하는 과정만 살펴봤다.
그런데, 여기선 증가뿐만 아니라 감소하는 부분도 고려해야 한다.
따라서, 어떤 원소를 기준으로, 좌측은 증가, 우측은 감소 (물론 부분수열이)의 형태를 보이는 곳을 찾으면 된다.
부분 수열이 감소하는 형태는 증가의 경우를 뒤집어서 구할 수 있다.

가령, 앞선 추가 예제에서 최대가 되는 지점인 5가 있는 곳을 기준으로 생각해보자.
좌측은 {1, 2, 3, 4, 5}, 우측은 {5, 4, 2, 1} 로 구성되는 것을 알 수 있다.
그런데, 여기서 기준점은 5이므로, 중복된 원소 5를 제거해줘야 한다.
즉, 원하는 수열은 {1, 2, 3, 4, 5, 4, 2, 1} 이므로, max(증가 + 감소)에서 한 개를 빼면 된다.

감각적으로 접근한 방법이 사실 맞았다.

마치면서

이 글을 쓰게 된 이유가, 사실 11054번 문제 때문이다.
11053번 문제를 푼 지 하루~이틀 정도 뒤에 11054번 문제를 접했는데, 유형이 비슷하길래 일단 들고와서 살짝 수정만 했다가 어찌 풀렸었다.
알고리즘 문제를 풀다보면 간혹 이렇게 풀리는 경우도 많다.
(백준에는 아예 중복 문제를 모아놓은 문제집도 있더라.)
따라서 필요 시에는 과거 코드들도 참고해야 함을 상기하기 위해 이렇게 포스팅을 해 놓는다.