문제 설명
처음 N개의 자연수(1부터 N까지)로 이루어진 순열 형태의 배열이 주어집니다. 한 번의 연산으로 배열의 임의의 접두사(prefix), 즉 앞부분 일부를 뒤집을 수 있습니다. 이때 배열 전체가 오름차순으로 정렬되기 위해 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다.
예시
배열이 {1, 2, 4, 3}이라면, 오름차순으로 정렬하기 위해 최소 3번의 반전이 필요합니다.
- 배열 전체를 뒤집기 →
{3, 4, 2, 1} - 앞의 두 원소를 뒤집기 →
{4, 3, 2, 1} - 배열 전체를 다시 뒤집기 →
{1, 2, 3, 4}
접근 방법 (알고리즘)
이 문제는 상태 공간 탐색 문제로 볼 수 있으며, BFS(너비 우선 탐색)를 활용해 해결할 수 있습니다. BFS를 사용하면 가장 적은 연산 횟수로 목표 상태에 도달하는 경로를 보장할 수 있습니다.
- 주어진 배열의 숫자들을 하나의 문자열로 인코딩합니다. 그리고 배열을 정렬한 뒤 같은 방식으로 문자열을 만들어 목표(destination) 문자열로 저장합니다.
- 초기 순열에서 BFS를 시작합니다. 매 단계마다 현재 순열의 접두사를 뒤집어 만들 수 있는 모든 순열을 확인합니다.
- 아직 방문하지 않은 순열이라면, 지금까지 수행한 반전 횟수와 함께 큐(queue)에 넣습니다.
- 인코딩된 문자열이 목표 문자열과 동일해지면, 해당 상태에 도달하기까지 필요한 반전 횟수를 반환합니다.
- 즉, 가능한 모든 순열 상태를 탐색하며 그중 최소 반전 횟수를 답으로 반환하게 됩니다.
구현 예제 (C++)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
string start = "";
string destination = "", t, r;
// 초기 배열을 문자열로 인코딩
for (int i = 0; i < n; i++) {
start += to_string(a[i]);
}
// 배열을 정렬한 후 목표 문자열 생성
sort(a, a + n);
for (int i = 0; i < n; i++) {
destination += to_string(a[i]);
}
queue<pair<string, int>> qu;
pair<string, int> p;
qu.push(make_pair(start, 0));
// 이미 정렬된 경우
if (start == destination) {
return 0;
}
while (!qu.empty()) {
p = qu.front();
t = p.first;
qu.pop();
// 길이 2부터 n까지의 접두사를 뒤집어 새로운 상태 생성
for (int j = 2; j <= n; j++) {
r = t;
reverse(r.begin(), r.begin() + j);
if (r == destination) {
return p.second + 1;
}
qu.push(make_pair(r, p.second + 1));
}
}
}
int main() {
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Minimum reversal: 3
정리
이 알고리즘은 각 접두사 반전을 하나의 상태 전이로 간주하고, BFS를 통해 최단 경로(최소 반전 횟수)를 찾는 방식입니다. 다만 모든 순열 상태를 탐색해야 하므로 N이 커질 경우 시간 복잡도가 급격히 증가한다는 점을 유의해야 합니다. 따라서 이 접근법은 N이 작은 경우에 적합합니다.