바이토닉 수열: LIS와 LDS의 만남, 모든 경우를 탐구하다

BOJ 11054번 문제, '가장 긴 바이토닉 부분 수열'을 풀면서 겪었던 시행착오와 그 과정을 통해 얻은 학습 내용을 정리해보려고 합니다. 처음에는 바이토닉 수열의 정의를 곡해하여 문제 접근 방식 자체에 오류가 있었지만, 공부를 통해 올바른 DP 구조를 이해하고 코드를 개선할 수 있었습니다.

학습 주제

• 공부 주제: 가장 긴 바이토닉 부분 수열 (BOJ 11054번)
• 대화 제목: 바이토닉 수열
• 학습 날짜: 2026년 2월 13일

질문과 탐구

처음에는 '바이토닉 수열'이라는 단어를 듣고, 증가하다가 감소하는 형태이므로 당연히 수열의 '최대값'이 그 중심이 될 것이라고 생각했습니다. 그래서 전체 수열에서 최대값을 찾고, 그 값을 기준으로 왼쪽에서 최장 증가 부분 수열(LIS)과 오른쪽에서 최장 감소 부분 수열(LDS)을 구한 뒤 합치면 될 것이라고 판단했습니다.

하지만 ChatGPT는 이 접근 방식이 틀렸다고 지적했습니다. 그 이유는 다음과 같았습니다.

• 최대값이 중심이 아닐 수 있다: 부분수열 문제에서는 중간의 어떤 값이든 선택하지 않을 수 있기 때문에, 전체 최대값이 반드시 바이토닉 수열의 중심이 된다는 보장이 없다는 점을 알게 되었습니다. 예를 들어 1 5 2 3 4 2 1이라는 수열에서 최대값은 5지만, 최적의 바이토닉 부분 수열은 1 2 3 4 2 1이며 이때의 중심은 4입니다.
• 모든 위치가 중심 후보가 되어야 한다: 따라서 바이토닉 수열의 중심은 특정 값이 아니라, 수열 내의 모든 위치 i가 될 수 있다는 점을 이해해야 했습니다.

이러한 의문점에서 출발하여 '왜 최대값으로만 생각하면 안 되는가?', 'LDS 계산 시 방향성은 어떻게 되는가?', 'DP의 정의와 계산 순서는 어떻게 일치해야 하는가?' 등의 질문을 던지며 탐구를 이어갔습니다.

핵심 학습 내용

1. 바이토닉 수열의 올바른 정의와 DP 구조

• 바이토닉 수열: 어떤 지점을 기준으로 증가하다가 감소하는 수열입니다. 중요한 것은 이 '어떤 지점'이 입력 수열의 전역 최대값이 아닐 수도 있으며, 임의의 인덱스가 될 수 있다는 점입니다.
• DP 구조:
  • LIS[i]: i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이. (왼쪽에서 오른쪽으로 계산)
  • LDS[i]: i번째 원소를 시작으로 하는 최장 감소 부분 수열의 길이. (오른쪽에서 왼쪽으로 계산)
• 결합: 각 i를 중심으로 LIS[i] + LDS[i] - 1을 계산합니다. -1을 하는 이유는 중심 원소 A[i]가 LIS와 LDS에 모두 포함되어 중복되기 때문입니다. 최종 답은 모든 i에 대해 계산된 LIS[i] + LDS[i] - 1 값 중 최댓값입니다.

2. LDS 계산의 방향성

처음에는 LDS를 LIS처럼 왼쪽에서 오른쪽으로 계산하려 했으나, 이는 수학적으로 불가능하다는 것을 깨달았습니다.

• LDS[i] = max(LDS[j] + 1) (where j > i and A[j] < A[i])
• 위 정의에서 LDS[i]는 i보다 **오른쪽(j > i)**의 값을 참조해야 합니다.
• 따라서 i가 증가하는 방향(왼쪽 → 오른쪽)으로 계산하면 j > i인 LDS[j] 값은 아직 계산되지 않은 상태가 됩니다.
• 이 문제를 해결하기 위해 DP 계산 순서를 오른쪽 → 왼쪽으로 바꾸어야 합니다. 이렇게 하면 j > i인 LDS[j] 값이 이미 계산된 상태이므로 정의가 성립합니다.

3. 부분수열의 본질: 인덱스 선택 문제

부분수열 문제의 핵심은 값이 아니라 인덱스를 선택하는 문제라는 것을 배웠습니다. 1 100 2 3 4에서 LIS가 1 2 3 4가 되는 이유는, 100이라는 값이 좋은 값이더라도 인덱스 순서를 유지하며 더 긴 증가 수열을 만들기 위해 100을 건너뛸 수 있기 때문입니다.

이해한 내용

• 부분수열 vs 부분배열: 부분수열은 원본 수열의 일부 원소를 원래 순서를 유지하며 뽑아낸 것이고, 부분배열은 연속된 원소를 뽑아낸 것입니다. 부분수열은 중간 원소를 버릴 수 있다는 점에서 DP 문제에서 큰 유연성을 제공합니다.
• DP 정의의 중요성: DP를 짤 때, dp[i]의 정의가 무엇인지, 그리고 그 정의가 참조하는 다른 상태(dp[j])가 무엇인지 명확히 해야 합니다. 또한, dp[i]가 참조하는 상태들이 이미 계산되어 있어야 한다는 DP의 절대 법칙을 이해했습니다.
• 문제 정의를 입력 조건으로 혼동하는 오류: 바이토닉 수열의 정의("어떤 지점을 기준으로 증가하다가 감소")를 입력 수열 자체가 그러한 구조를 가지고 있다고 착각했던 것이 초기 오류의 근본 원인이었습니다. 문제는 '입력이 이미 산 모양'이 아니라, '입력에서 산 모양의 부분수열을 찾아야 한다'는 점이었습니다.

실전 적용

이 문제에서 배운 LIS + LDS 구조는 다양한 DP 문제에 적용될 수 있습니다.

• LIS, LCS, Edit Distance 등: 부분수열, 부분문자열 관련 DP 문제에서 핵심적인 아이디어를 제공합니다.
• 최대 부분합 문제: 각 i를 끝점으로 하는 최대 부분합을 계산하는 방식과 유사점을 가집니다.
• 코딩 테스트: BOJ 11054번과 같이 LIS/LDS를 결합하는 문제는 골드 티어 이상에서 자주 출제되므로, 이 구조를 완벽히 이해하고 있으면 문제 해결 속도를 크게 높일 수 있습니다.

실습 계획:

• LIS, LDS 기본 알고리즘을 따로 구현해보며 익숙해지기
• 다른 LIS, LDS 관련 BOJ 문제 풀기 (예: 11053번, 1965번)
• 이후 다른 DP 문제에 LIS/LDS 아이디어 적용 연습

추가 학습 계획

• LIS/LDS의 O(N log N) 구현: 현재는 O(N^2)으로 구현했지만, 이분 탐색을 활용한 O(N log N) 방법도 익혀두면 좋을 것 같습니다.
• 다양한 DP 패턴 학습: 구간 DP, 비트마스크 DP 등 다른 유형의 DP 문제들을 꾸준히 학습하여 문제 해결 능력을 확장하고 싶습니다.
• "DP는 상태 정의 싸움이다"라는 격언 되새기기: 앞으로 DP 문제를 풀 때마다 dp[i]의 정의를 명확히 하고, 그 정의가 다른 상태를 어떻게 참조하는지를 분석하는 습관을 들이겠습니다.

참고 자료

• BOJ 11054번 문제 페이지: https://www.acmicpc.net/problem/11054
• ChatGPT 대화 내용: