BOJ_11053 가장 긴 증가하는 부분 수열

• TOC {:toc}

이 글은 백준 온라인 저지의 11053번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.06 (Python)

import sys
input = sys.stdin.readline

input()
C = {}
S = map(int, input().split())
# S 안의 x에 대해서
for x in S:
    c = 0
    # 지금까지 생성된 key를 순회하면서
    for m in C.keys():
        # 입력받은 값보다 작은 key m에 대해
        if x > m:
            # m의 count와 현재 c 중 큰 값을 c 값으로 입력한다.
            c = max(c, C[m])
    # x의 count 값을 c + 1로 지정한다.
    C[x] = c + 1
print(max(C.values()))

아이디어 & 풀이

{10, 20, 40, 50, 30, 40, 50, 60, 70}를 예시로 입력을 순회할 때 수열을 계산하는 과정을 봐보자.

• 우선 수가 감소하면 새로운 부분 수열이 생성된다.
  • 10, 20, 40, 50이 생기고
  • 30이 입력돼서 수가 감소하면 30, 40, 50, ...이 새로 생긴다.
• 이때 새로 생성된 정확한 길이를 알기 위해서는 이전에 입력된 수 중 어떤 수들이 해당 수열에 이어질 수 있는지 알아야 한다.
  • 해당 예시의 경우 {10, 20}에서 이어질 수 있어 실제로 이 부분 수열은 {10, 20, 30, 40, ...}이다.
• 수가 증가하면 그 수보다 최댓값이 작은 부분 수열에 해당 값이 추가된다.
  • 30이 입력된 직후 40이 입력됐을 때 이 수는 이전에 생성된 {10, 20, 40, 50}의 최댓값보다는 작기 때문에 이어지지 않고, {30}에만 이어진다.
  • 60, 70이 입력됐을 때는 두 수열 모두에 {10, 20, 40, 50, 60, 70}, {10, 20, 30, 40, 50, 60, 70}와 같이 추가된다.
• 60을 입력받았을 때, 첫 번째 수열은 60까지 수가 다섯 개고, 두 번째 수열은 여섯 개이기 때문에 첫 번째 수열은 가장 긴 수열이 될 수 없다.

이로부터 알 수 있는 포인트는 다음과 같다.

• 새로 시작되는 부분 수열의 정확한 길이를 파악하기 위해서는 이전에 입력받은 값들에 대한 정보가 있어야 한다.
• 특정 값을 입력받았을 때 해당 값보다 이전까지 입력된 부분 수열 중 ‘가장 긴’ 부분 수열의 길이만 알면 된다.
• 값을 입력받을 때마다, 이전에 입력받은 가장 긴 부분 수열의 길이에 1을 더해서 그 값에 대해 저장하면 된다.

이를 해결하기 위한 방법은 다음과 같다.

• 입력한 수를 key로 하는 딕셔너리를 생성한다.
• 각 key는 해당 수까지 증가하는 부분 수열의 길이(count)의 최댓값을 value로 갖는다.
• 수를 입력받았을 때 그 값보다 작은 수의 count 값 중 최댓값을 구한다.
• 그 값에서 1 증가한 값을 입력한 수의 count로 입력한다.

디버그

• 마지막에 C[x]에 값을 넣을 때 c를 1 증가시켜주는 것을 깜빡했다.

피드백

• 리스트와 slice 표기법을 이용해서 간결하게 작성할 수도 있다 (풀이 1).

2022.04.04 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, nums] = input;
const seq = nums.split(" ").map((n) => parseInt(n));

function main() {
    const longest = [];

    seq.forEach((num) => {
        const i = longest.findIndex((n) => n >= num);
        if (i === -1) longest.push(num);
        else longest[i] = num;
    });

    return longest.length;
}

console.log(main());

참고 답안 1

import sys
input = sys.stdin.readline

N = int(input())
S = list(map(int, input().split()))
P = [0] * 1001

# S안의 x에 대해서
for x in S:
    # P의 x + 1번째(인덱스 x) 원소를
    # P의 x번(인덱스 x - 1)까지의 최댓값 + 1로 바꾼다.
    P[x] = max(P[:x]) + 1

print(max(P))

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").trim().split("\n");

const N = parseInt(input[0]);
const seq = input[1].split(" ").map((a) => parseInt(a));
seq.unshift(0); 

const count = [0];

// seq 안의 N개의 수를 처음부터 순회하면서
for (let i = 1; i <= N; i++) {
  // 해당 인덱스의 count 값을 1로 초기화 하고
  count[i] = 1;
  // 현재 인덱스 i의 이전 j까지 순회하면서
  for (let j = 1; j < i; j++) {
    // 이전(j) 값이 현재 값보다 작고
    // 현재 count값이 이전 숫자의 count 값 + 1보다 작으면
    if (seq[j] < seq[i] && count[j] + 1 > count[i]) {
      // 현재 count 값을 이전 count 값 + 1로 변경
      count[i] = count[j] + 1;
    }
  }
}

const res = Math.max(...count);

console.log(res);

참고 답안 2

# 풀이 2-1
input()
S = list(map(int, input().split()))
P = [S[0]]

# 입력받은 수 x에 대해서
for x in S:
    # 부분 수열의 마지막 수보다 크면
    if x > P[-1]:
        # 부분 수열에 더한다.
        P.append(x)
    # 작으면
    else:
        # P를 역으로 순화하면서
        i = len(P) - 1
        while i > 0:
            # 해당 인덱스의 값이 x보다 작아지는 i에서 break하고
            if P[i - 1] < x:
                break
            i -= 1
        # 그다음 값을 x로 바꾼다.
        P[i] = x

print(len(P))

# 풀이 2-2
from bisect import bisect_left

input()
S = list(map(int, input().split()))
P = [S[0]]

for x in S:
    # P의 마지막 원소가 n보다 작으면
    if P[-1] < x:
        # n을 P에 추가한다.
        P.append(x)
    else:
        # n이 list_arr 안에 정렬되어 들어갈 위치를 구해
        # 해당 위치의 값을 n으로 바꾼다.
        P[bisect_left(P, x)] = x

print(len(P))

아이디어 & 풀이

구성한 리스트 P가 가장 긴 부분 수열을 나타낸다.

해당 리스트 자체가 완벽하게 현재 가장 긴 부분 수열을 나타내는 것은 아니지만 해당 리스트의 길이는 가장 긴 부분 수열의 길이와 같다.

• 입력된 값 x가 P의 중간에 들어가야 하면 해당 위치(정렬했을 때 x가 들어가야 할 위치)의 원소를 ‘바꾼다’.
  • 이전에 입력된 자신보다 작은 수에서 이어져 새로운 수열을 만들어가는 것과 같다.
• 입력한 수들이 만드는 수열이 이전에 입력된 가장 긴 부분 수열보다 길어지면 이전에 입력했던 모든 수를 바꾸고 P에 새로운 원소로 추가되기 때문에 가장 긴 부분 수열을 바꿀 수 있다.
• 이전에 입력된 수열을 넘어가지 못하면 중간 원소는 바뀌었지만, 이전의 부분 수열이 더 길고 이전 부분 수열의 길이가 가장 긴 부분 수열의 길이와 같다.

입력값 x가 P에서 들어갈 위치를 찾을 때 다른 탐색 방법을 이용해 조금 더 빨리 실행할 수도 있다.

• bisect를 이용하거나 (풀이 2-2)
• 이진 탐색 등의 탐색을 직접 구현한다.