이번 문제는 백준의 골드 4 문제 줄 세우기 문제이다.
문제를 한 번 차근차근 읽어보자.
아이들을 번호대로 줄 세우려고 한다.
최대 200명의 아이가 주어지며, 순서가 뒤죽박죽으로 주어질 때
아이들의 위치를 최소 횟수로 바꿔 번호순으로 정렬해달라고 한다.
어떻게 문제를 풀어야 할까?
정렬 알고리즘 구현?
정렬 알고리즘을 직접 구현한다면 어떨까?
시간 복잡도가 낮은 정렬 알고리즘을 직접 구현해서, 위치가 교환되는
횟수를 세어주면 과연 최소 횟수가 보장될까?
이는 정렬 방식 마다 한 번 생각을 해볼 필요가 있다.
먼저 O(NlogN)의 퀵 정렬을 한 번 생각해보자.
예시의 3 7 5 2 6 1 4를 퀵 정렬로 정렬한다면?
2 4 1 3 6 5 7 1 Pass에서 다음과 같이 정렬될 것이다.
이미 4회의 이동이 일어났기 때문에 최소를 보장할 수 없다.
그렇다면 O(NlogN)의 또다른 방식인 병합 정렬은 어떨까?
3 7 5 2 6 1 4를 또 한 번 예시로 생각해보자.
3 7 2 5 1 6 4 끝까지 분할했을 때, 첫 정렬은 이렇게 일어난다.
총 2회의 이동이 발생했다.
하지만, 추가적으로 병합하며 정렬을 하려면 4회를 분명 넘게된다.
즉 이 방법 또한 최소를 보장할 수 없다.
O(N)만에 정렬이 가능한 기수 정렬(Radix sort)을 생각해보더라도,
시간이 덜 걸린다 뿐이지 자기 자리에 없는 수를 모두 돌려놓는 셈이니,
이동 횟수는 4회를 훌쩍 넘어간다.
이 방식은 잘못된 것 같다.
결국은 DP
사실 곰곰히 생각을 해보다가 문제의 알고리즘 분류를 보게 되었다.
이 문제는 동적 계획법 문제라고 한다.
동적 계획법이면 이전 단계의 결과를 현재 단계에 적용할 수 있다는 말인데,
과연 이 문제에 어떻게 적용시킬 수 있을까?
생각해보면 우리는 오름차순으로 어차피 정렬을 해야 한다.
그럼 이미 오름차순으로 정렬된 부분은 건들지 않아도 되는 것이다!
이것과 관련된 개념으로 LIS(최장 증가 부분 수열) 가 떠오른다.
증가하는 가장 긴 부분 수열은 이미 오름차순으로 정렬된 상태이다.
그럼 주어진 수열에서, 해당 부분만 제외하고 나머지만 옮기면?
오름차순으로 모두 정렬될 것이다.
자세한 구현 코드는 아래와 같다.
cin >> num;
for (int i = 0; i < num; i++)
cin >> kids_line[i];
int lis = 0;
for (int i = 0; i < num; i++){
dp[i] = 1;
for (int j = 0; j <= i; j++)
if (kids_line[i] > kids_line[j])
dp[i] = max(dp[i], dp[j] + 1);
// LIS 알고리즘
lis = max(lis, dp[i]);
}
cout << num - lis;
return 0;사실 최장 증가 부분 수열에 대해서 떠올리기까지 꽤 오랜 시간이 걸렸다.
해당 개념을 알지 못해도 풀 수 있을 정도로 실력을 늘려야 할 것 같다.