[백준/종만북] 선형 자료 구조

OOING·2023년 8월 14일

백준+알고리즘 공부

목록 보기

11/75

📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.

동적 배열(Dynamic Array)

배열의 문제점
처음 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료를 넣을 수 없음

동적 배열의 특징

자료의 개수가 변함에 따라 크기가 변경
언어 차원에서 지원 X, 배열을 이용해 만들어 낸 별도의 자료 구조 -> 표준 라이브러리(C++ vector)에 포함, 배열의 일부 특성을 이어받음
원소들이 메모리의 연속된 위치에 저장
주어진 원소의 위치를 반환, 변경하는 동작을 O(1)에 수행
배열의 크기 변경 가능(resize()) : O(N)
배열의 맨 끝에 원소를 추가하여 크기(size)를 1 늘림(append()) : O(1)

resize() 연산

새 배열을 할당받고 기존 자료를 복사 -> O(N)에 구현 가능

append() 연산

❌ append()가 호출될 때마다 resize() 호출? -> 수행 시간이 O(N)이 되어버림!
✔️ 메모리를 할당받을 때 배열의 크기가 커질 때를 대비해 여유분의 메모리를 미리 할당받음

size : 실제 원소의 수
capacity : 이미 할당받은 메모리의 크기

동적 배열의 재할당 전략

현재 가진 원소의 개수에 비례해서 여유분을 확보 -> N번의 append() 연산을 수행하는데 O(N) 시간 걸림 -> 한 번의 append() 연산에는 평균적으로 O(1) 걸림

동적 배열의 최종 크기를 미리 짐작할 수 있다면, 동적 배열의 용량을 미리 늘려두어 재할당에 드는 비용을 없앨 수 있음

vector<int> v;
v.reserve(100) // vector v의 용량을 100으로 변경

연결 리스트

연결 리스트의 특징

특정 위치에서의 삽입과 삭제를 O(1)에 수행
원소들이 메모리의 여기저기 흩어져있어(연속 X) 이전과 다음원소를 가리키는 포인터를 가짐
첫 번쨰 노드(head)와 마지막 노드(tail)의 포인터를 가짐
표준 라이브러리(C++ list)에 포함

큐(Queue), 스택(Stack), 데크(Dequeue)

원래는 같은 장이 아닌데.. 내용이 적어서 그냥 합체

특징

큐(Queue) : FIFO(선입선출, 한 쪽 끝에서 자료를 넣고 반대쪽 끝에서 자료를 꺼냄)
스택(Stack) : LIFO(후입선출, 한쪽 끝에서만 자료를 넣고 뺄 수 있음(
데크(Dequeue) : 양쪽 끝에서 자료를 넣고 뺄 수 있음
자료를 넣는 작업은 push, 자료를 빼는 작업은 pop

1158 요세푸스 문제

List 이용

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

int n, k;

int main() {
	cin >> n >> k;
	list<int> l;

	for (int i = 0; i < n; i++) {
		l.emplace_back(i + 1);
	}
	list<int>::iterator it = l.begin();

	cout << "<";
	for (int i = 1; !l.empty(); i++) {
		if (i % k == 0) {
			cout << *it;
			it = l.erase(it++);	// iterator 삭제 후 위치 재정의 해야함
			if (l.empty()) break;
			cout << ", ";
		}
		else ++it;
		if (it == l.end()) it = l.begin();
	}
	cout << ">";
}

iterator 선언 : list\<int>::iterator it

그나저나 알고리즘 분류에 큐도 있네.. 큐로 할걸

List Iterators Incompatible

말 그대로 List의 iterator를 잘못 썼을 때 발생한다
위 코드의 주석을 보면 알겠지만 erase(it) 후 재정의를 하지 않아서.. 발생했다.

Queue 이용

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

int N, K;

int main() {
	cin >> N >> K;
	queue<int> q;

	for (int i = 0; i < N; i++) {
		q.push(i + 1);
	}
	cout << "<";
	for (int i = 1; !q.empty(); i++) {
		int front = q.front();
		q.pop();
		if (i % K != 0) q.push(front);
		else {
			cout << front;
			if (q.empty()) break;
			cout << ", ";
		}	
	}
	cout << ">";
}

iterator를 안 써도 돼서 더 간단한듯.

2504 괄호의 값

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

string s;
stack<char> st;
int ans = 0, temp = 1;

int bracket() {
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			st.push(s[i]);
			temp *= 2;
		}
		else if (s[i] == '[') {
			st.push(s[i]);
			temp *= 3;
		}
		else if (s[i] == ')') {
			if (st.empty() || st.top() != '(') return 0;
			else {
				if (s[i - 1] == '(') ans += temp;
				st.pop();
				temp /= 2;
			}
		}
		else {
			if (st.empty() || st.top() != '[') return 0;
			else {
				if (s[i - 1] == '[') ans += temp;
				st.pop();
				temp /= 3;
			}
		}
	}
	if (!st.empty()) return 0;
	return ans;
}

int main() {
	cin >> s;
	cout << bracket();
}