굥뷰를 햡시댜
문제 풀이에 앞선 자주 쓰이는 STL 컨테이너, 자료구조 설명 본문
하루 공부한 것 리마인드겸 티스토리를 시작하게 되었습니다.
저는 알고리즘 문제 풀이용 언어로 C/C++을 선택했습니다.
컴퓨터 공학을 전공하면서 가장 처음 접했던 프로그래밍 언어이기도 하고 가장 자신있으며 친숙하다고 생각했기 때문입니다.
(다른 언어들도 다룰 수 있지만 그것들은 추후에 따로 시간이 된다면 다시 공부하고 올리도록 하겠습니다...)
또, C++에는 STL이라는 아주 잘 만들어진 라이브러리가 있어서 초보자도 조금만 공부한다면 문제 풀이에 유용하게 사용할 수 있습니다.
처음 알고리즘 문제 풀이에 어떤 언어를 선택해야할지 고민이신 분들은 저처럼 자신이 익숙하거나, 아니면 혼자 스터디할 때 자료가 많은 C++을 사용하시는 것을 추천합니다!
알고리즘 문제 풀이에 대한 글을 포스트 하기전에 앞서, 간단하게 STL에 대해 소개하려고 합니다.
1. STL(Standard Template Library)
앞서 말했듯이 C++에서는 아주 잘 만들어진 라이브러리를 제공합니다. 뭐 1979년도에 Alexander Stepanov라는 분이 만든 것이 시초라고 하는데 아직까지 쓰이는걸 보면 이분은 엄청난 천재인것 같습니다..
잡소리는 그냥 무시하시구요..
STL은 크게 컨테이너, 반복자, 알고리즘의 3가지로 구성되어 있습니다.
일단, 가장 자주 쓰이는 것들 위주로 간단하게 정리하자면
vector, stack, queue, pair 정도가 있습니다.
2. Vector
vector는 여러가지 자료형을 담을 수 있는 컨테이너 입니다.
문제 풀이에 아주 많이 사용되는 컨테이너로 C++로 문제를 푸신다면 꼭 숙지하고 가셔야 합니다.
1) 사용법
- vector는 vector라는 헤더에 포함되어 있습니다. vector를 사용하시려면 <vector> 헤더를 포함시켜주셔야 합니다.
이런식으로 헤더를 추가해주시고 담고 싶은 자료형에 따라 vector를 선언해주시면 됩니다.
또, vector에는 다양한 멤버 함수가 있습니다.
함수명 |
기능 |
v.push_back(value) |
v를 선언할 때 썼던 자료형과 동일한 value를 vector 컨테이너에 추가 |
v.pop_back() |
v의 마지막 원소를 삭제 |
v.size() |
v의 크기를 반환(v가 담고 있는 원소의 갯수 반환) |
v.resize(i) |
v를 i만큼의 크기로 사이즈 변경 |
v.begin() |
v의 맨 앞 원소를 가리킴 |
v.end() |
v의 마지막 원소를 가리킴 |
v.front() |
v의 0번째 원소 반환 |
v.back() |
v의 마지막 원소 반환 |
v.clear() |
v의 모든 원소를 비워줌(삭제) |
v.empty() |
v가 비어있는지 조사 -> 비어있으면 1, 아니면 0 반환 |
3. Pair
pair는 쉽게 말해서 두 개의 변수를 저장할 수 있는 컨테이너 입니다.
1) 사용법
- pair는 <utility>라는 헤더를 추가하시면 사용할 수 있습니다.
이런식으로 헤더를 추가해주시고 담고 싶은 자료형에 따라 pair를 선언해주시면 됩니다.
또, pair는 pair 안에 pair를 담을 수 있습니다. 위 사진처럼 pair<int, pair<int, int> >이런 식으로 선언해주시면 됩니다.
여기서 주의하셔야 할 점은, pair안에 pair를 선언해주실때 pair<int, pair<int, int> > 이렇게 뒤에 '>' 꺽쇠 모양을 한 칸 띄고 선언해 주셔야 합니다.
이유는 제가 지금 사용하고 있는 visual studio 2015에서는 에러가 나지 않지만, 어떤 개발환경에서는 '>>' 이 부분을 시프트 연산자로 인식해서 에러가 난다고 합니다.
또, pair의 각 원소에 대해 접근할 수 있는 방법이 있습니다.
pair<int, int> p1;과 같이 선언한 p1에서
p1.first; -> pair의 첫번째 원소를 반환해줍니다.
p1.second -> pair의 두번째 원소를 반환해 줍니다.
즉, pair<first, second> 이런 식으로 원소가 담겨 있다고 생각하시면 됩니다.
pair의 원소를 생성하실 때는 p1.first = 10; 이런식으로 초기화해주는 것이 아니라 make_pair(first, second)라는 함수를 통해 초기화 할 수 있습니다.
사용법은 간단합니다.
p1.make_pair(10, 20);
이런 식으로 선언해 주면 p1.first는 10, p1.second는 20의 값을 담게 됩니다.
4. stack
stack은 대학교 컴퓨터 공학이나 관련 전공을 이수하셨다면 자료구조 수업 시간때 한번쯤은 구현해보셨을 겁니다.
stack은 LIFO(Last In First Out) 즉, 나중에 들어온 것이 먼저 나갈 수 있는 후입선출의 자료구조 입니다.
1) 사용법
- stack은 <stack>이라는 헤더를 추가하시면 사용할 수 있습니다.
이런식으로 헤더를 추가해주시고 담고 싶은 자료형에 따라 stack을 선언해주시면 됩니다.
그럼 stack을 언제 사용하냐?
-> stack은 위 그림 처럼 어떤 일의 실행순서를 기록해두었다가 나중 일의 순서부터 출력하고 싶은 경우 사용한다고 생각하시면 됩니다.
또, stack에는 다양한 멤버 함수가 있습니다.
함수명 |
기능 |
s.top() |
s의 가장 상위 원소(가장 나중에 들어간 원소를 반환) |
s.push(value) |
s의 맨 위에 value 추가 |
s.pop() |
s의 맨 위 원소 삭제(가장 나중에 들어간 원소를 삭제) |
s.empty() |
s가 비어있는지 조사 -> 비어있으면 1, 아니면 0 반환 |
s.size() |
s의 크기(s가 담고 있는 원소의 갯수) 반환 |
이런 식으로 s에 값 1, 2, 3을 push하고 가장 나중에 들어간 원소 3을 pop할 수 있습니다.
5. queue
queue도 stack과 마찬가지로 자주 쓰이는 자료구조중 하나입니다.
하지만 stack과 달리, queue는 FIFO(First In First Out) 즉, 먼저 들어온 것이 먼저 나가는 선입선출의 자료구조입니다.
1) 사용법
- queue는 stack과 마찬가지로 <queue>라는 헤더를 추가하시면 queue에 관한 라이브러리를 사용하실 수 있습니다.
이런식으로 헤더를 추가해주시고 담고 싶은 자료형에 따라 queue를 선언해주시면 됩니다.
queue는 나중에 BFS(Breadth First Search)를 구현할 때 사용되는 자료구조이기 때문에 꼭 알아두셔야 합니다!
또, queue에는 다양한 멤버 함수가 있습니다.
함수명 | 기능 |
q.fron() | q의 가장 먼저 들어간 원소 반환 |
q.back() | q의 가장 나중에 들어간 원소 반환 |
q.push(value) | q의 맨 뒤에 value 추가 |
q.pop() | q의 맨 앞 원소 삭제(가장 먼저 들어간 원소) |
q.empty() | q가 비어있는지 조사 -> 비어있으면 1, 아니면 0 반환 |
q.size() | q의 크기(q가 담고 있는 원소의 갯수) 반환 |
이런 식으로 q에 값 1, 2, 3을 push하고 가장 먼저 들어간 원소 1을 pop할 수 있습니다.
잘못된 정보 or 추가할 사항 피드백 댓글로 남겨주시면 즉각 반영하도록 노력하겠습니다!