알고리즘 문제 해결 전략2 18장 선형 자료 구조(2)

18.5 문제: 조세푸스 문제

마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 할까요?

모든 문제는 기본 자료구조로 풀림. 배열, 연결링크드 리스트. 이 자료 구조는 메모리와 데이터로 만들어짐. 문제 풀이를 위해서 필요한 자료 구조를 선태갛기 위해서는 문제를 이해하고 제대로 정의해야 함.

각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력함.

 

18.6 풀이: 조세푸스 문제

조세푸스 문제는 연결 리스트로 풀 수 있는 전형적인 문제임. 한 사람이 죽을 때마다 포인터를 (K-1)번 옮기기 때문에, 전체 시간 복잡도는 O(NK)가 됨. 이 문제에서는 N, K가 모두 1000 이하의 값이기 때문에 충분히 시간 안에 수행할 수 있음. STL에서 list의 크기를 구하는 연산은 O(N)이기 때문에 size()를 호출하는 대신 리스트에 포함된 원소의 수를 n에 직접 유지하는 점도 눈여겨봄. 

void josephus(int n, int k) {
	list<int> survivors;
	for (int i = 1; i <= n; i++) survivors.push_back(i);
	list<int>::iterator kill = survivors.begin();
	while (n > 2) {
		kill = survivors.erase(kill);
		if (kill == survivors.end()) kill = survivors.begin();
		--n;
		for (int i = 0; i < k - 1; ++i) {
			++kill;
			if (kill == survivors.end()) kill = survivors.begin();
		}
	}
	cout << survivors.front() << " " << survivors.back() << endl;
}

 

조세푸스 문제 빠르게 풀기

대표적으로 k-1번 포인터를 옮기는 대신 (K-1)modN번 포인터를 옮기는 것이 있음. 이렇게 하면 시간 복잡도는 O(NK)에서 O(N^2)이 됨. K가 매우 클 때에는 유용함. 이 외 O(N) 시간이 걸리는 동적 계획법이나, 시뮬레이션을 한번에 여러 단계씩 해서 O(KlgN) 시간에 수행되는 알고리즘 등 다양한 방법이 존재함.