류나의 갓생살기

20대의 마지막을 갓생으로 장식하기

Programming/Algorithms

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

Ryuna (류준범) 2022. 3. 31. 23:10

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

목차

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

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

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

 - vector vs. list

 - 문제풀이

2. 스택과 큐, 데크

 - C++ STL의 stack, queue

 - C++ STL의 deque

 - 문제풀이

참고한 자료

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

https://book.algospot.com/

 

알고리즘 문제 해결 전략

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 <알고리즘 문제 해결 전략>은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드

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)?

Recently, I noticed some people mentioning that std::list::size() has a linear complexity. According to some sources, this is in fact implementation dependent as the standard doesn't say what the

stackoverflow.com

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

조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하

algospot.com

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

#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

Mismatched Brackets 문제 정보 문제 Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas ha

algospot.com

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

#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

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

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

#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번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

스택을 직접 구현해보는 문제입니다. 물론 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번: 큐

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

#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번: 덱

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

#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번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고

www.acmicpc.net

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

#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;
}

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

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