[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C/C++)
백준 온라인 저지(BOJ) 11053번 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
* 사용언어 : C언어, C++
1. 문제
주어진 수열에 대해서 가장 긴 증가하는 부분 수열의 길이를 출력
2. 풀이
Dynamic Programming으로 푸는 대표적인 문제로 LIS(Longest Increasing Subsequence)라고 부릅니다.
비슷한 결의 문제로 ① 감소 버전, ② 바이토닉 버전(증가하다가 감소)도 있습니다.
LIS는 개발자 만화에서 사용될 정도로 아주 대표적인 DP문제 중 하나입니다.
만만하게 보고 혼자서 풀어보려고 고민해봤는데 아이디어가 안 떠올라서
아래 나무위키 링크에서 풀이법을 공부한 뒤 풀어봤습니다.
최장 증가 부분 수열
최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주
namu.wiki
(아래 작성한 풀이는 O(N^2) 풀이법으로 O(NlogN) 풀이는 위 링크에서 참고 바랍니다)
제가 이해한대로 다시 설명해보겠습니다.
1차원 배열 a에 모든 수를 입력받고 같은 크기의 배열 dp를 선언합니다.
dp[i]에는 1부터 i번까지 가장 긴 증가하는 부분 수열의 길이가 기록됩니다.
dp[i]를 계산할 때는 1부터 i - 1까지의 숫자를 탐색(index j)하고, 아래 두 조건을 확인합니다.
1) a[j]가 a[i]보다 작은 경우
2) dp[j] + 1이 현재 dp[i]보다 큰 경우
만약 위 두 조건을 만족하면 dp[i]를 dp[j] + 1로 업데이트합니다.
1부터 N까지 모든 탐색을 마쳤다면, dp 배열의 모든 값 중 가장 큰 값을 출력하면 됩니다.
주의할 점은 후반부에 첫 번째 숫자보다 더 작은 숫자로 LIS를 시작할 수 있기 때문에
a[0]과 dp[0]은 첫 번째 숫자가 아닌 0으로 초기화해야 합니다.
관련하여 문제 풀이에 도움이 되었던 반례 2가지 공유드리며 설명 마치겠습니다.
1
10
(정답 1)
9
3 5 7 9 1 3 5 6 7
(정답 5)
3. 코드
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11053_가장 긴 증가하는 부분 수열
1120KB 0ms
*/
#include <cstdio>
const int LM = 1001;
int a[LM], dp[LM], N, max;
int main() {
#ifdef _WIN32
freopen("input.txt", "r", stdin);
#endif // _WIN32
scanf("%d", &N);
for (int i = 1; i <= N; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i; ++j) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
}
if (dp[i] > max) max = dp[i];
}
printf("%d\n", max);
return 0;
}