자료구조
: 컴퓨터과학에서 데이터를 구조적으로 표현하는 방식
- 선형 자료구조 : 하나의 자료 뒤에 하나의 자료가 배치되는 구조 ex) stack, queue, list, 배열
- 비선형 자료구조 : 하나의 자료 뒤에 여러 자료가 올 수 있는 구조 ex) 트리, 그래프
Stack
- LIFO (Last in FIrst out)
- STL
#include <stack>- push() : 스택에 원소 추가
- pop() : 스택에서 원소 삭제
- top() : 스택 최상단 원소 확인
- size() : 스택의 사이즈 확인
- empty() : 스택이 비어있는지 확인
- 문제 풀이 예시 : 백준 10828 스택 (https://www.acmicpc.net/problem/10828)
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, x;
string order = "";
stack<int> s;
cin >> n;
for (int i=0; i<n; i++)
{
cin >> order;
if (!order.compare("push"))
{
cin >> x;
s.push(x);
}
else if (!order.compare("pop"))
{
if (s.size())
{
cout << s.top() << "\n";
s.pop();
}
else cout << "-1" << "\n";
}
else if (!order.compare("size")) cout << s.size() << "\n";
else if (!order.compare("empty")) cout << s.empty() << "\n";
else
{
if (s.size()) cout << s.top() << "\n";
else cout << "-1" << "\n";
}
}
return 0;
}Queue
- FIFO (First in FIrst out)
- STL
#include <queue>- push() : 큐에 원소 추가
- pop() : 큐에서 원소 삭제
- front() : 큐에서 가장 앞에 있는 원소 출력
- back() : 큐에서 가장 뒤에 있는 원소 출력
- size() : 큐의 사이즈 확인
- empty() : 큐가 비어있는지 확인
- Circular Queue : 선형 큐로 인해 발생하는 메모리 낭비 해결 가능
- 문제 풀이 예시 : 백준 10845 큐 (https://www.acmicpc.net/problem/10845)
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
queue<int> q;
int n, x;
string s;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
if (!s.compare("push"))
{
cin >> x;
q.push(x);
}
else if (!s.compare("pop"))
{
if (q.size())
{
cout << q.front() << "\n";
q.pop();
}
else cout << "-1\n";
}
else if (!s.compare("size")) cout << q.size() << "\n";
else if (!s.compare("empty")) cout << q.empty() << "\n";
else if (!s.compare("front"))
{
if (q.size()) cout << q.front() << "\n";
else cout << "-1\n";
}
else
{
if (q.size()) cout << q.back() << "\n";
else cout << "-1\n";
}
}
return 0;
}List
- 동일한 자료형으로 된 원소들의 모임
- 선형 리스트 (Linear List)
- 배열로 구현
- 인덱스를 통해 접근
- 선언 이후 배열의 크기 변경 불가
- 연결 리스트 (Linked List)
- 링크를 통해 서로 연결되어 있음.
- 실행 중에 원소가 동적으로 생성,삭제되므로 크기 변경이 자유로움
- STL : 양방향 연결리스트(Double Linked List) 제공
#include <list>- begin() : beginning iterator 반환
- end() : end iterator 반환
- push_front(element) : 리스트 가장 앞에 원소 추가
- push-back(element) : 리스트 가장 뒤에 원소 추가
- insert(iterator, element) : iterator가 가리키는 부분의 앞에 원소 추가
- pop_front() : 리스트 가장 앞의 원소 삭제
- pop_back() : 리스트 가장 뒤의 원소 삭제
- erase(iterator) : iterator가 가리키는 부분의 원소 삭제
- front() : 첫번째 원소 반환
- back() : 마지막 원소 반환
- empty() : 리스트가 비어있는지 확인
- size() : 리스트의 사이즈 확인
- *iterator : iterator가 가리키는 원소에 접근
ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 주차는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 표기된 모든 출처를 옮겨 작성합니다.
<출처>
'학회&동아리 > ALGOS' 카테고리의 다른 글
| [ALGOS STUDY] 2023-SUMMER DAY1 Bruteforcing, Backtracking (3) | 2023.09.01 |
|---|---|
| [ALGOS STUDY] 2023-1-WEEK5 정수론 (0) | 2023.09.01 |
| [ALGOS STUDY] 2023-1-WEEK4 그리디 (0) | 2023.09.01 |
| [ALGOS STUDY] 2023-1-WEEK3 Priority Queue, Map, Set (0) | 2023.09.01 |
| [ALGOS STUDY] 2023-1-WEEK1 C/C++ 입출력, STL 라이브러리, 복잡도 (0) | 2023.09.01 |