[C++/Python/BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (DP)& 반례

https://www.acmicpc.net/problem/11053

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

 

이 문제는 LIS(최장 증가 부분 수열)으로 

이와 비슷한 백준문제(같이 풀면 좋을 문제)에는

 

가장 긴 감소하는 부분 수열 [11722번]

 

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

 

상자넣기[1965번]

 

전깃줄[2565번]

2565번: 전깃줄

풀이 : https://what-am-i.tistory.com/378

[Python/백준]전깃줄(DP)

 

 

이 있다.

 

 

해설 : 

1) vector을 만들어 n개를 입력받는다.

2) for문을 돌린다.

3) for문 내부 - if문을 만족하는 값에 대하여 dp배열을 갱신한다.

4) max를 이용하여 최대길이를 알아낸다.

5) 출력한다.

 

코드 : 

 

 

#include<iostream>
#include<algorithm>  //max를 사용하기 위해서
#include<vector>
using namespace std;
int dp[1001];
int main(){
    int n; cin >> n;
    vector<int> v(n);
    for(auto& i:v) cin >> i;
    
    int ans = 0;
    for(int i=0;i<n;i++){
         dp[i] = 1; // 글자수는 최소 1이기때문에
        for(int j=0;j<i;j++){
            if(v[i]>v[j] && dp[i] < dp[j]+1){  // 값이 더 크고, 갱신했을때 커질경우 갱신
                 dp[i] = dp[j]+1;
            } 
        }
        ans = max(ans,dp[i]);
    }
    cout<<ans;
}

 

 

 

dp문제는 처음 생각이 어렵지 풀이를 보면 쉽다고 느껴진다.

 

시간복잡도는 이중 for문이기에 O(n^2)이다!

 

---

 

 

이렇게 풀었었고 몇달이 지난후

다시 답을 안보고 풀자니 몇시간이 걸렸다.

그래도 결국 해결했다는 것에 뿌듯했다.

틀린이유들과 그에 맞는 반례 , 고치는 과정을 쓰자면

 

 

<반례>

6

1 4 5 6 2 3

하면 답이 4가 나와야한다. 그러나 3이 나온다.

이유는 마지막 값이 최대라고 생각했기때문이다. 

새로 만든 코드는 dp[i]가 i을 맨 마지막 원소로 삼는 최장 증가 부분 순열의 길이라고 설정하였다.

그렇기에 마지막 값이 최대가 아니라 지금까지의 dp값중 최대값을 출력해야했다.

 

 

cout << *max_element(dp.begin(), dp.end())<<"\n";

 

dp를 벡터로 만들었기에 max_element라는 함수를 이용해 dp(벡터) 안의 값 중 최대값을 구할 수 있다.

 

 

그러나!

이렇게 했는데도 또 틀렸다 

ㄹㅇ 맞왜틀...

 

<반례>

2

6 4

하면 1이 나와야하는데 2가 나왔다. 이건 설정 문제였다.

MX의 기본값을 0으로 수정하여 고칠 수 있었다.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v;
vector<int> dp;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    v.resize(n);
    dp.resize(n);
     for(auto &i :v) cin >> i;
    dp[0] = 1;
    for (int i = 1; i < n; i++) {
        int MX = 0; // 최소 길이가 1이므로 
        for (int j = 0; j < i; j++) {
            if (v[i] > v[j]) {
                MX = max(MX, dp[j]);
            }
        }
        dp[i] = MX + 1;
    }
    cout << *max_element(dp.begin(), dp.end())<<"\n";

}

 

몇시간동안 끙끙대며 만든 내 코드이다

알고리즘 문제를 많이 답 코드 찾아가며 유형별로 많이 풀어보며 외워야겠다는 생각을 했었는데

생각을 바꿨다. 시간이 많이 걸리더라도 내가 스스로 풀어보는 힘을 키울것이다. 

 

 

 

 

---

 

 

Python 풀이 

 

if __name__=="__main__" :
    n = int(input())
    arr = list(map(int,input().split()))
    dp = [1]*n
    
    # dp[y] ; y를 마지막으로 하는 수열의 가장 긴 개수 
    # 가장 첫번째는 1개뿐이다.
    for i in range(n) :
        # 이전 수를 돌면서 
        for j in range(i) : 
            if arr[i] > arr[j] and dp[i] < dp[j]+1 :
                dp[i] = dp[j]+1
    print(max(dp))

 

세상 간단하다. 

 

dp 리스트를 1으로 초기화한후  ( 증가하는 수열의 길이가 적어도 1개니까) 

arr리스트를 모두 탐색한다. 

 

for i in range(n) : # i 를 마지막으로 하는 증가 수열의 길이를 알려고 한다. 

 

 

탐색을 하며 나보다 이전 수를 돌아보고 나보다 작고 해당 수의 dp값 +1 이 나의 dp값보다 크다면 갱신해주면 된다. 

 

 

 

 

 

 

 

 

 

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."