[알고리즘] 역추적(DP & 최단거리)

이론정리

문제풀이

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ci;
vector<int> path;

ci lis(int size, vector<int>& list) {
    vector<int> dp(size, 1); //수열길이 적어놓는거
    ci ans = {1, 0};

    for (int i = 1; i < size; i++) { //맨 끝이 될 node
        int index = -1;
        for(int j = 0; j < i; j++) { //첫 node부터 i-1번째 node까지 돌면서
        	//맨끝 node가 j node가 더 크고
            //맨 끝 node의 dp가 j의 dp + 1보다 작은경우 - 이거 검사하는게 진짜 중요
            if(list[i] > list[j] && dp[i] < dp[j] + 1) { 
                dp[i] = dp[j] + 1; 
                index = j;
            }
        }
        path[i] = index;
        if(ans.first < dp[i]) ans = {dp[i], i};
    }
    return ans;
}

int main() {
    int size;
    cin >> size;
    vector<int> list(size);
    path.assign(size, -1);

    for (int i = 0; i < size; i++) {
        cin >> list[i];
    }
    ci ans = lis(size, list);
    int index  = ans.second;
    cout << ans.first << "\n";

    vector<int> answer;

    while (index != -1) {
        answer.push_back(list[index]);
        index = path[index];
    }

    for (int i = answer.size() - 1; i >= 0; i--) {
        cout << answer[i] << " ";
    }
    return 0;
}

• 이전에는 이전에 검사했을때 가장 컸던 수보다 지금수가 더 크면 dp + 1하고, path를 찾는식으로 했었는데, 이러면 0번 index에서 시작하는 수열밖에 찾지못함

• 가장 긴 수열은 중간에서부터도 시작할 수 있기 때문에,매번 0~i-1번까지 돌면서 하나하나 i번째 끝수랑 비교해야함.

  1. 지금 j값이 i보다 작은게 맞는지(증가수열이니까 필수)
  2. j에 저장된 증가수열길이가 i에 있는것보다 큰게 맞는지

• 2번 비교사항이 중요한게, 0~i-1번에 저장된 증가수열길이랑 i-1번 비교하면서 계속 i번째의 최대 증가수열 길이를 바꿔주고 있는거임.

• 가장 길어질 수 있는 수열 뒤에 i번째 수를 붙여주는거!!