[C++ STL] list(연결리스트)

연결리스트(list)

연결리스트는 배열의 각 요소가 값만 갖고있는 것이 아니라 다음 요소를 가리키는 포인터를 함께 가지고 있다. 이는 배열에서 중간에 추가 혹은 삭제할 때 뒤의 원소를 쭉 밀거나 뒤의 원소를 쭉 당겨와야하는 단점을 보완한 것이다. 배열의 요소들을 직접 미는 것이 아닌 포인터값만 변경해주는 것으로 임의의 위치에 추가/삭제 연산을 할 수 있다. C++에서는 list라는 자료형으로 연결리스트가 구현되어 있다.

 

 

 

리스트 각 요소는 포인터로 연결되어있기 때문에 메모리 상에 연속적으로 존재하지 않아도 된다. 그래서 각 요소에 접근할 때도 포인터를 이용해서 순서대로 접근해야한다. 이를 아래의 예제를 통해 소개한다.

 

• 리스트 선언
• 양 끝의 요소 삭제(삽입)
• 임의의 위치에 새로운 요소 추가(삭제)
• 리스트의 각 요소 출력

#include<iostream>
#include<list>

using namespace std;

int main() {

	//리스트 선언
	list<int> b;
	//리스트 포인터 선언
	list<int>::iterator iter = b.begin();

	//뒤쪽으로 요소 추가하기
	for (int i = 0; i < 5; i++) {
		b.push_back(i);
	}

	//양 끝의 요소 제거하기
	b.pop_back();
	b.pop_front();

	//중간에 요소 추가하기 (삭제는 함수만 erase로 바꿈)
	iter = b.begin();
	int k = 2; //두번째 자리에 8 추가하기
	for (int i = 0; i < k - 1; ++i) {
		++iter;
	}

	b.insert(iter, 8);

	//전체 요소 출력하기

	for (iter = b.begin(); iter != b.end(); iter++) {
		cout << *iter << " ";
	}
	return 0;
}

 

예제 (요세푸스 문제)

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 두 명이 남을 때까지 사람을 제거하면 마지막에 남은 두 사람은 몇 번과 몇 번인가?

 

입력: test case 갯수, N, K

출력: 남은 두 사람의 번호

 

#include<iostream>
#include<list>

using namespace std;


void josephus(int n, int k);
int main() {


	int T;
	pair<int, int> data[1001];

	//input
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> data[i].first >> data[i].second;

	}

	//compute
	for (int i = 0; i < T; i++) {

		int n = data[i].first;
		int k = data[i].second;
		josephus(n, k);
	}

	return 0;

	}


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) {
    	// erase함수의 return은 삭제한 다음 원소를 가리키는 iterator반환
		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;
}

Reference

프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 구종만