BAEKJOON 11053:가장 긴 증가하는 부분 수열 O(n²) for C

 가장 긴 증가하는 부분 수열

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

---

코드

#include <stdio.h>

int main(void){
	int size, max = 1;
    int data[1000], dp[1000];
    scanf("%d", &size);
    
    for(int i = 0; i < size; ++i){
    	scanf("%d", data + i);
        dp[i] = 1;
        
        for(int k = 0 ; k < i; ++k){
        	if(data[i] > data[k]){
            	if(dp[i] < dp[k] + 1){
                	dp[i] = dp[k] + 1;
                }
            }
        }
        
        if(dp[i] > max) max = dp[i];
        
    }
    
    printf("%d", max);
}

 

설명

 중요한 것이 내부 반복문[# 루프 인덱서로 k를 사용하는 구문]이다. 바깥 반복문[# 루프 인덱서로 i를 사용하는 구문]에서 인덱스 0부터 진행할 곳까지의 범위를 정해준다. 그 안쪽 두 조건문이 문제를 해결하는 핵심이다.

• data[i] > data[k]
• dp[i] < dp[k] + 1

 두 조건을 한번에 판단하면 이해하는데 어려움을 겪을 수 있으므로 먼저 data[i] > data[k]를 먼저 비교한다.

 예시 입력으로 받은 데이터를 기반으로 설명하면 다음과 같다.

 

i = 0

 각 요소는 부분 수열로 생각할 수 있으므로 기본적으로 길이는 1이다.

 

i = 1

 두 번째 반복으로 넘어가면 구문에 의해 다음처럼 진행된다.

data[i] > data[k] 구문에 의해 길이는 총 2가 된다.

 

i = 2

 

i = 3

 이제 여기에서 중요해진다. 이 부분에서부터 두 번째 조건이 필요한 것이다.

 첫 번째 조건만 따지면, i = 3인 부분에서 이전 데이터는 모두 현재 데이터[# 인덱스 3에 위치한 30]보다 작으므로 길이는 4가 된다. 이렇게 되어버리면 LIS[# Longest Increasing Subsequence]를 찾는 문제가 아니라, 현재 값보다 작은 모든 개수를 찾는 것 밖에 안된다. 그래서 두 번째 조건 dp[i] < dp[k] + 1 이 중요한 것이다.

 

 순서대로 가보자. k가 0일 때, 1일때는 30보다 작으므로 상관이 없다. 그러나 k = 2가 되었을 때, 분명 30보다는 작지만 그 이전 값인 20보단 큰 값이 되어야 하나, 10으로 작다. 때문에 k = 2까지일 때, dp 값도 비교를 해야한다.

if(data[k] < data[i]){
	dp[i] = dp[k] + 1;
}

 해당 조건으로 인덱스 0, 1에 대한 dp 값을 불러왔다. 따라서 i = 3, k = 0일 때, dp[i]의 값은 2가 된다. 여기에서, k = 1이 되었을 때, dp[k]를 만족하기 위해서는 dp[i] < dp[k] + 1을 따라야 한다. 이 코드를 넣게 되면

if(data[i] > data[k]){
	if(dp[i] < dp[k] + 1){
    	dp[i] = dp[k] + 1;
    }
}

 이런 구성의 조건이 만들어진다. 이 조건대로 하면 i = 3 k = 2일 때, data[i] > data[k]는 만족하더라도, dp[i] < dp[k] + 1은 만족하지 않기 때문에 dp[i]는 올바른 값을 가질 수 있다.

 

번외

 처음 코드를 구성할 때, i = 1 ~ n까지로 구성하고 max = 0으로 초기화해서 계속 문제가 실패했다. 차후에 n = 1일 때는 답으로 1이 나와야 하나 max가 1이 아닌 0으로 초기화되어 있다는 것을 알고 괜한 시간만 낭비했다.

---

 O(nlogn)에 대한 풀이도 있다고 하니, 한번 찾아봐야겠다.

 

# index