Queue의 정의 기본적인 자료 구조의 한가지로, 마지막에 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 처음으로 Push한 값이 Pop해서 나오는 자료 구조이다. Queue 용어 Pop : Queue에 들어있는 가장 처음으로 넣어진 값을 없앤다. Push : Queue에 가장 마지막에 값을 넣는다. 백준 Queue
비정확 할 수 있음. 영어의 Stack Stack의 영어 정의는 쌓다, 쌓아 올린 더미를 뜻한다. 프로그램에서의 Stack 기본적인 자료 구조의 한가지로, 마지막에 집어 넣은 데이터가 먼저 나오는 LIFO(Last In First Out)구조로 저장하는 형식을 말한다. 마지막으로 Push한 값이 Pop해서 나오는 자료 구조이다. Stack을 구현해 보기 Queue는 Vector를 제한 한 것 이라고도 할 수 있다. 그렇기에 Vector를 제한한 class를 만들어보자. #include using namespace std; template class Stack { public: vector vec; void push(T v) { vec.push_back(v); } T top() { return vec[ve..
Union Find란? 여러 node들을 묶어 그룹을 만들어내 공통된 조상을 찾는 알고리즘. 작동 방식 초기화 각 node마다 조상의 번호가 부여되어있다. const int MAX_IDX = 1005; int root[MAX_IDX]; for(int i = 0;i < MAX_IDX;i++) { root[i] = i; } node조상 구하기 재귀적으로 조상을 찾는 함수를 호출하여 찾는다. find를 하면서 가장 위 조상을 호출된 node의 조상으로 변경하면 최적화를 할 수 있다. int union_find(int x) { if (root[x] == x) return x; return root[x] = union_find(root[x]); } node 합치기 조상의 번호를 따라가며 가장 마지막으로 발견되는 ..