배열, 연결 리스트, 스택과 큐 기본 문제

이번 글에서는 지금까지 공부한 자료구조들(배열, 연결 리스트, 스택, 큐)을 활용하는 기본 문제를 풀어봅니다.

목차

1. 동적 배열과 연결 리스트

 - 동적 배열: C++ STL의 vector

 - 연결 리스트: C++ STL의 list

 - vector vs. list

 - 문제풀이

2. 스택과 큐, 데크

 - C++ STL의 stack, queue

 - C++ STL의 deque

 - 문제풀이

참고한 자료

알고리즘 문제 해결 전략, 구종만

https://book.algospot.com/

알고리즘 문제 해결 전략

---

동적 배열과 연결 리스트

동적 배열: C++ STL의 vector

동적 배열(dynamic array)을 알고리즘 문제풀이에 사용할 때는 C++ 표준 라이브러리의 <vector>를 이용합니다.

선언

vector<int> vec1;
vector<float> vec2(3); // {0, 0, 0} - float 자료형의 기본값 0으로 초기화
vector<char> vec3(2, "W"); // {"W", "W"}
vector<vector<int>> vec4; // 2차원 벡터

삽입

vector<int>::iterator it = vec1.begin(); // 반복자
it = vec1.insert(it, 1); // it는 새롭게 추가된 원소 1을 가리킨다
it = vec1.insert(it + 1, 2); // 1 뒤에 2를 삽입하고 it는 2를 가리킨다
vec3.push_back("L"); // {"W", "W", "L"}

vector의 어디든 삽입이 가능한 insert 메서드는 반복자를 사용하며 중간 위치 삽입의 경우 뒤의 모든 원소가 이동하기 때문에 효율적이지는 않습니다. push_back 메서드는 맨 뒤에만 삽입이 가능합니다.

삭제

vec2.erase(vec2.begin() + 2); // index가 2인 원소 삭제
vec2.erase(vec2.begin(), vec2.begin() + 2); // index가 0~1인 원소 삭제
vec3.pop_back(); // 맨 뒤의 원소 삭제
vec1.clear(); // 완전히 비우기

크기

vec2.size(); // 원소의 개수
vec2.capacity(); // 물리적 크기
vec2.reserve(10); // capacity가 10 미만인 경우 10으로 올림(재할당)

연결 리스트: C++ STL의 list

연결 리스트(linked list)를 알고리즘 문제풀이에 사용할 때는 C++ 표준 라이브러리의 <list>를 이용합니다.

선언

list<int> list1;
list<float> list2(3); // {0, 0, 0} - float 자료형의 기본값 0으로 초기화
list<char> list3(2, "W"); // {"W", "W"}

삽입

list<int>::iterator it = list1.begin(); // 반복자
it = list1.insert(it, 1); // it는 새롭게 추가된 원소 1을 가리킨다
it++; // it 반복자가 한 칸 뒤로 간다 (list 반복자는 int 덧셈이 안됨)
it = list1.insert(it, 2); // 1 뒤에 2를 삽입하고 it는 2를 가리킨다
list3.push_back("L"); // {"W", "W", "L"}
list3.push_front("L"); // {"L", "W", "W", "L"}

list의 어디든 삽입이 가능한 insert 메서드는 반복자를 사용하며 중간 위치 삽입의 경우에도 연결 리스트의 특성상 상수 시간 안에 실행됩니다. push_back, push_front 메서드는 각각 맨 뒤, 맨 앞에만 삽입이 가능합니다.

삭제

list<int>::iterator it = list2.begin();
advance(it, 2); // 반복자 it를 2칸 뒤로
it = list2.erase(it); // index가 2인 원소 삭제하고 it는 그 다음 원소 가리킴
it = list2.begin();
list<int>::iterator it2 = list2.begin();
advance(it2, 2);
list2.erase(it, it2); // index가 0~1인 원소 삭제
list3.pop_back(); // 맨 뒤의 원소 삭제
list3.pop_front(); // 맨 앞의 원소 삭제
list1.clear(); // 완전히 비우기

크기

list2.size(); // 원소의 개수
list2.resize(2); // size가 2를 넘는 경우, 맨 앞 2개 원소만 남기고 삭제하여 size를 2로 줄임
list2.resize(5, 1); // size가 5 미만인 경우, 여러 개의 1을 추가하여 size를 5로 늘림

참고사항 참고한 자료(알고리즘 문제 해결 전략)에는 C++의 size 메서드가 상수 시간이 아닌 선형 시간이라고 나와있지만, C++11부터는 상수 시간인 것이 맞다고 합니다.

https://stackoverflow.com/questions/228908/is-listsize-really-on

Is list::size() really O(n)?

vector vs. list

vector, list의 여러 연산의 시간복잡도를 비교하면 다음과 같습니다.

연산	vector	list
이전 또는 다음 원소 찾기	O(1)	O(1)
맨 뒤에 원소 추가 또는 삭제하기	O(1)	O(1)
맨 뒤 이외의 위치에 원소 추가 또는 삭제하기	O(n)	O(1)
임의의 위치의 원소 찾기	O(1)	O(n)
크기 구하기	O(1)	O(1) [C++11부터]

문제풀이

(알고스팟) 조세푸스 문제

https://algospot.com/judge/problem/read/JOSEPHUS

algospot.com :: JOSEPHUS

연결 리스트로 해결할 수 있는 대표적인 문제입니다.

#include <iostream>
#include <list>
using namespace std;

int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		int N, K;
		cin >> N >> K;

		// 리스트 만들기
		list<int> josephus;
		for (int j = 1; j <= N; j++) {
			josephus.push_back(j);
		}

		// 리스트에서 제거
		list<int>::iterator death = josephus.begin();
		for (int j = 0; j < N - 2; j++) {
			death = josephus.erase(death);
			if (death == josephus.end()) {
				death = josephus.begin();
			}
			for (int i = 0; i < K - 1; i++) {
				death++;
				if (death == josephus.end()) {
					death = josephus.begin();
				}
			}
		}

		// 남은 2명의 번호 출력
		cout << josephus.front() << " " << josephus.back() << endl;
	}

	return 0;
}

주의1 리스트를 만들 때 번호는 0이 아니라 1부터 시작해야 합니다.

주의2 리스트에서 erase를 하고 나서 이미 반복자가 한 칸을 넘어갔기 때문에 칸을 옮기는 작업을 K-1번만 수행해야 합니다.

주의3 맨 뒤로 간 반복자를 다시 맨 앞으로 옮기는 작업은 erase 직후와 칸을 옮긴 직후, 이렇게 두 번씩을 수행해야 합니다.

스택과 큐, 데크

C++ STL의 stack, queue

스택, 큐, 데크는 C++ 표준 라이브러리에 각각 <stack>, <queue>, <deque> 클래스로 구현되어 있습니다. 스택과 큐는 서로 유사한 인터페이스를 가지고 있고, 데크는 vector와 유사한 인터페이스를 갖고 있습니다.

선언

stack<int> s;
queue<int> q;

삽입

s.push();
q.push();

삭제

s.pop();
q.pop();

원소 확인

s.top();
q.front(); // 가장 오래된 원소
q.back(); // 가장 최근에 들어온 원소

크기

s.size();
q.size();

C++ STL의 deque

선언

deque<int> dq;

삽입

dq.push_front(n);
dq.push_back(n);

vector와 동일하게 insert 메서드도 지원합니다.

삭제

dq.pop_front();
dq.pop_back();

vector와 동일하게 erase 메서드도 지원합니다.

원소 확인

dq.front();
dq.back();

vector와 동일하게 at 메서드와 [] 연산자도 지원합니다.

크기

dq.size();

문제풀이

(알고스팟) 짝이 맞지 않는 괄호

https://algospot.com/judge/problem/read/BRACKETS2

algospot.com :: BRACKETS2

스택으로 해결할 수 있는 대표적인 문제입니다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		string str;
		cin >> str;
		stack<int> s;
		string ans = "YES";
		for (int j = 0; j < str.size(); j++) {
			switch (str[j]) {
			case '(':
				s.push(1);
				break;
			case '{':
				s.push(2);
				break;
			case '[':
				s.push(3);
				break;
			case ')':
				if (s.size() == 0 || s.top() != 1) ans = "NO";
				else s.pop();
				break;
			case '}':
				if (s.size() == 0 || s.top() != 2) ans = "NO";
				else s.pop();
				break;
			case ']':
				if (s.size() == 0 || s.top() != 3) ans = "NO";
				else s.pop();
				break;
			}
			if (ans == "NO") break;
		}
		if (s.size() > 0) ans = "NO";
		cout << ans << endl;
	}

	return 0;
}

주의1 닫는 괄호를 만났을 경우, top()을 호출하기 전에 size()가 0인지 검사하지 않으면 런타임 오류가 발생합니다.

주의2 for loop가 종료되고 나서 스택에 남은 원소가 있으면 실패입니다.

(BOJ) 요세푸스 문제 0

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

입출력 형식, 처음 죽는 사람의 번호가 다를 뿐 사실상 알고스팟의 '조세푸스 문제'와 같은 문제입니다. 큐 자료구조를 이용해서 문제를 풀어봅니다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    // N명의 사람으로 구성된 큐
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }
    
    // 요세푸스 순열 출력
    cout << "<";
    while (q.size() > 0) {
        for (int i = 0; i < K - 1; i++) {
            int t = q.front();
            q.pop();
            q.push(t);
        }
        cout << q.front();
        q.pop();
        if (q.size() > 0) cout << ", ";
        else break;
    }
    cout << ">" << endl;
    
    return 0;
}

(BOJ) 스택

https://www.acmicpc.net/problem/10828

10828번: 스택

스택을 직접 구현해보는 문제입니다. 물론 c++ <stack>을 써도 됩니다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    stack<int> s;

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;

        if (str == "pop") {
            if (s.empty()) cout << "-1" << endl;
            else {
                cout << s.top() << endl;
                s.pop();
            }
        }
        else if (str == "size") {
            cout << s.size() << endl;
        }
        else if (str == "empty") {
            if (s.empty()) cout << "1" << endl;
            else cout << "0" << endl;
        }
        else if (str == "top") {
            if (s.empty()) cout << "-1" << endl;
            else cout << s.top() << endl;
        }
        else {
            int a;
            cin >> a;
            s.push(a);
        }
    }

    return 0;
}

주의 string 입력을 받을 때 getline()으로 받으면 원하는 동작을 하지 않습니다. 이전 입력의 개행 문자가 cin에 남아있기 때문에 입력을 받지 않고 넘겨버립니다.

(BOJ) 큐

https://www.acmicpc.net/problem/10845

10845번: 큐

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    queue<int> q;

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;

        if (str == "pop") {
            if (q.empty()) cout << "-1" << endl;
            else {
                cout << q.front() << endl;
                q.pop();
            }
        }
        else if (str == "size") {
            cout << q.size() << endl;
        }
        else if (str == "empty") {
            if (q.empty()) cout << "1" << endl;
            else cout << "0" << endl;
        }
        else if (str == "front") {
            if (q.empty()) cout << "-1" << endl;
            else cout << q.front() << endl;
        }
        else if (str == "back") {
            if (q.empty()) cout << "-1" << endl;
            else cout << q.back() << endl;
        }
        else {
            int a;
            cin >> a;
            q.push(a);
        }
    }

    return 0;
}

(BOJ) 덱

https://www.acmicpc.net/problem/10866

10866번: 덱

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    deque<int> dq;

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;

        if (str == "push_front") {
            int a;
            cin >> a;
            dq.push_front(a);
        }
        else if (str == "push_back") {
            int a;
            cin >> a;
            dq.push_back(a);
        }
        else if (str == "pop_front") {
            if (dq.empty()) cout << "-1" << endl;
            else {
                cout << dq.front() << endl;
                dq.pop_front();
            }
        }
        else if (str == "pop_back") {
            if (dq.empty()) cout << "-1" << endl;
            else {
                cout << dq.back() << endl;
                dq.pop_back();
            }
        }
        else if (str == "size") {
            cout << dq.size() << endl;
        }
        else if (str == "empty") {
            if (dq.empty()) cout << "1" << endl;
            else cout << "0" << endl;
        }
        else if (str == "front") {
            if (dq.empty()) cout << "-1" << endl;
            else cout << dq.front() << endl;
        }
        else if (str == "back") {
            if (dq.empty()) cout << "-1" << endl;
            else cout << dq.back() << endl;
        }
    }

    return 0;
}

(BOJ) 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

알고스팟의 짝이 맞지 않는 괄호 문제와 유사합니다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	int C;
	cin >> C;

	for (int i = 0; i < C; i++) {
		string str;
		cin >> str;
		stack<int> s;
		string ans = "YES";
		for (int j = 0; j < str.size(); j++) {
			if (str[j] == '(') {
				s.push(1);
			}
			else {
				if (s.size() == 0) ans = "NO";
				else s.pop();
			}
			if (ans == "NO") break;
		}
		if (s.size() > 0) ans = "NO";
		cout << ans << endl;
	}

	return 0;
}

---

교재에 있지만 풀지 않은 문제(외계 신호 분석)가 있는데 해당 문제는 신경써야 할 요소가 많아서 나중에 다시 시도해 보려고 합니다.

다음 글에서부터는 '트리' 자료구조에 대해 알아보겠습니다~!