연결 리스트
노드 하나에
데이터가 들어가는 데이터 부분
다음 노드의 주소를 저장하는 Next
이전 노드의 주소를 저장하는 Previous(더블 링크드 리스트)
메모리가 허용하는 한도 안에서는 무한으로 확장할 수 있다.
배열처럼 인덱스로 찾을수 없기에 특정한 노드를 구해오는게 어렵다.
연결 리스트에서 인덱스로 탐색할 수 있도록 만들어 두긴 하지만
내부적으로 보면 결국 순차적으로 탐색하여 찾아내는 방식
내부에서 처리를 쉽게 하도록 실제 데이터는 없는 더미 노드인 Begin과 End를 생성해 둔다.
가령 리스트의 첫번째 노드를 구할때 Begin노드의 다음 노드를 받아와 접근하면 된다.
단순 연결 리스트:
다음 노드에 대한 참조만을 가짐
이중 연결 리스트:
다음 노드주소와 이전 노드의 참조를 가짐
뒤로 탐색하는게 빠르다는 점과 현재 노드를 삭제하는것이 훨씬 간단하다.
단순 연결 리스트보다 손상에 강하다.
원형 연결 리스트:
마지막 노드의 다음 주소를 리스트의 첫번째 노드를 가리키는 리스트
청크 리스트:
배열과 리스트의 장점을 합친 것. 리스트의 멤버가 배열이다.
스택
후입선출. 마지막에 넣은게 가장 첫번째로 나온다.(프링글스 통)
한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
제일 위에 있는 Top에 무엇이 들어있는지만 알 수 있는 자료구조
원칙적으로 중간에 있는 값은 접근할 수 없기 때문에, 만약 스택에서 그러한 상황에 놓인다면,
스택을 쓰지 말아야 할 상황에 스택을 쓴것이다.
컴퓨터 프로그램의 서브 루틴에 대한 정보를 저장하는 자료구조나 함수 호출에서 널리 활용됨
스택은 흔히 크기를 고정하여서 사용하기 때문에 이를 다 사용하면 넘치게 됨(스택 오버플로)
입력: 푸쉬Push
출력: 팝Pop
C++에서 스택 사용하기
std::stack
활용사례:
단어 뒤집기: 문장이 주어졌을때 단어를 모두 뒤집는 문제
스택은 후입선출이므로, 단어의 캐릭터들을 스택에 넣고, 차례대로 POP을 수행하면 단어가 뒤집혀 나오게 된다.
괄호문제: 괄호 문자열이 주어졌을때 올바른 괄호 문자열인지 아닌지 알아보는 문제
괄호 문자열: ( 와 ) 로만 이루어진 문자열
올바른 괄호 문자열: 괄호의 쌍이 올바른 문제
올바른 괄호 문자열의 예:
()
(())
((()))
올바른 괄호 문자열이 아닌 예
(()(
(())()))
(()
문제 힌트: 괄호의 쌍은 가장 가까운 여는 괄호와 닫는 괄호가 쌍을 이룬다.
괄호들을 쭉 탐색하면서 여는 괄호가 검출되면 스택에 넣고,
닫는 괄호가 검출되면 스택의 Top 여는괄호(가장 나중에 있는 == 닫는 괄호와 가장 가까운)괄호와 매칭시킨다.
끝까지 수행했을때 모든 괄호의 짝이 맞으면 올바른 괄호 문자열이다.
또는 닫는 괄호가 검출되고, 매칭을 하려고 했을떄, 스택에 내용물이 없으면 잘못된 괄호 문자열이다.
스택 수열
1부터 N까지의 수를 스택에 넣었다가 뽑아 놓음으로 하나의 수열을 만들 수 있다.
Push하는 순서는 오름차순이다.
임의의 수열 A가 있을때 스택을 이용해 이 수열을 만들수 있는지 없는지 구하는 문제
A = [4,3,6,8,7,5,2,1]이라면
큐
한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
선입선출
push 큐에 자료를 넣는 연산
pop 큐에서 자료를 빼는 연산
front 큐의 가장 앞에 있는 자료를 보는 연산(pop의 값을 출력하는것)
back 큐의 가장 뒤에 있는 자료를 보는 연산
empty 큐가 비어있는지 아닌지 알아보는 연산
size 큐에 저장되어 있는 자료의 개수를 알아보는 연산
선언법
#include
queue Q;
사용예)
조세피스 문제
https://www.acmicpc.net/problem/1158
우선순위 큐
큐는 먼저 들어온 값이 먼저 나가는 자료구조이지만, 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
일반적으로 힙을 이용하여 구현한다.
우선순위 큐의 속성
- 모든 항목에는 우선순위가 있다
- 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 queue에서 제외된다.
- 두 요소의 우선순위가 같으면 queue의 순서에 따라 제공된다.
우선순위 큐가 지원하는 기능
enqueue(): queue에 새 요소를 삽입
dequeue(): queue에 최대 우선 순위 요소를 삭제하고 그 값을 반환
peek(): queue에서 최대 우선 순위 요소를 반환
덱Deque
양쪽 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조
Double-Ended Queue의 약자
스택과 큐를 덱으로 대체할 수 있기 때문에 중요한 자료구조이다.
덱을 사용해야만 풀 수 있는 문제는 거의 없긴 하다.
벡터
자동으로 메모리가 할당되는 배열느낌의 컨테이너
선언
vector<자료형> 이름; 비어있는 벡터를 생성
vector<자료형> 이름(5); 기본값 0으로 초기화된 5개의 원소를 가지는 벡터 생성
vector<자료형> 이름(5,2); 2로 초기화된 5개의 원소를 가지는 벡터 생성
vector<자료형> 이름(v2); 다른 벡터를 복사하여 새로운 벡터 생성
벡터가 두개 있을떄 == != < > <= >=로 대소비교가 가능함
==,!=은 모든 요소가 동일한지 검사하고,
<,>등은 각 벡터의 요소를 1:1로 검사하다가 다름을 감지했을때의 대소를 비교한다.
v.front() : 벡터의 맨 첫번째 값
v.back() : 벡터의 맨 마지막 값
v.push_back()
v.pop_back()
v.size() : 벡터에 원소가 채워진 갯수
v.capacity: 벡터에 할당된 공간. 즉 size와 capacity는 다를 수 있음
v.swap(v2): 다른 벡터와 모든 원소의 값을 swap해줌
v.resize(n): 벡터의 크기를 n으로 변경한다. 크기가 더 커진다면 0으로 초기화된다.
v.resize(n, m): 벡터의 크기를 n으로 변경한다. 크기가 더 커진다면 m으로 초기화된다.
