🔷 스택과 큐
✔️ 스택
삽입과 삭제 연산이 후입선출(LIFO : Last In First Out)로 이뤄지는 자료구조
- 나중에 들어온 데이터가 먼저 나가는 구조
- 삽입, 삭제가 한 쪽에서만!
- 새 값이 스택에 들어가면 → top이 새 값 가리키게 됨!
스택 용어
top: 삽입/삭제가 일어나는 위치
연산
push: top에 새로운 데이터 삽입pop: top에 현재 데이터 삭제 → 확인top: top 위치 데이터 단순 확인
→ 깊이 우선 탐색 (DFS), 백트래킹 종류의 코테에 효과적 (후입선출 : 재귀 함수 알고리즘 원리와 일맥상통)
❓ Stack과 재귀함수가 LIFO 후입선출로 같은가?
먼저 재귀함수란, 자기 자신을 호출하는 것.
무한으로 호출 → 반드시 탈출 조건을 써야만 한다.
재귀함수 예시는 다음과 같다
void countNum(int num)
{
if (num == 1)
{
cout << "Num : " << num << endl;
return;
}
else
{
cout << "Num : " << num << endl;
countNum(num - 1);
}
}
재귀함수는 먼저들어온 함수의 명령을 실행 → 맨 앞번호부터 수직탐색 한다.
1→2→3→4
1→6→7
…
과 같이..
가장 겉에 있는 A라는 함수를 부르면 A가 시작됨
그 안에서 또, A를 부르니까 또 겉의 A가 시작됨. 이런 식으로 조건을 만족할 때까지 A를 호출함
재귀함수가 끝날 조건을 만족했을 때, 가장 마지막으로 실행한 함수부터 끝나게 됨!!!!!
✔️ 큐
삽입, 삭제 연산이 선입선출(FIFO : First In First Out)로 이뤄지는 자료구조
- 먼저 들어온 데이터가 먼저 나감
- 삽입, 삭제가 양방향에서 이뤄짐
큐 용어
back: 큐에서 가장 끝 데이터를 가리키는 영역front: 큐에서 가장 앞의 데이터를 가리키는 영역
연산
push: back 부분에 새로운 데이터 삽입pop: front 부분의 데이터 삭제, 확인
→ 너비 우선 탐색(BFS)에서 자주 사용
💭 우선순위 큐란 무엇인가?
먼저 들어오는 데이터가 아닌(들어간 순서에 상관없이!!), 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조!
힙(Heap)을 이용하여 구현함- 왜 우선순위 큐는
배열이나연결리스트로 구현하지 않나?배열로 구현한다면, 우선순위 높은 순서대로 배열 앞부분으로 넣는다면, 우선순위 높은 데이터를 반환하는 건 어렵지 않을텐데?!?!?! → 응 아니야 우선순위가 중간인 것이 들어가는 건 ..? → 뒤의 데이터까지 인덱스를 다 밀어야 하고, 최악의 경우 → 삽입 위치를 찾기 위해 모든 인덱스를 탐색해야 함..-
시간 복잡도가
O(n)이 됨!!(자료가 n 개라는 가정) -
배열 → 삭제는 O(1) 삽입은 O(n)
연결리스트로 구현한다면, 배열이랑 마찬가지로 우선순위가 높은 데이터 반환은 쉬움근데.. 배열이랑 마찬가지로 위치 찾는 문제가 생김..
최악의 경우 → 맨 끝까지 가야 찾을 수 있게 됨 →
O(n)의 시간복잡도 -
연결리스트 → 삭제는 O(1) 삽입은 O(n)
-
이런 저런 이유로, 힙으로 구현한다면?
→ 삽입이나 삭제 과정에서 모두 부모/자식간의 비교만 이루어짐.
- 이진 트리의 높이가 하나 증가할 때마다, 저장 가능한 자료 갯수가 2배 증가
- 비교 연산 횟수 1회 증가
즉, 삽입&삭제 모두 최악의 경우 : O(log2n)의 시간 복잡도를 가진다!
힙 : 삭제 O(log2n) 삽입 O(log2n)
🤨 그래서, 힙이 뭔데..?
- 완전 이진 트리
- 모든 노드에 저장된 값(우선순위)들이 자식 노드들의 것보다 우선순위가 크거나 같다!
- 즉, 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조!
→ 아하! 그래서 우선순위 큐를 구현하기에 적합하
최대 힙(Max Heap) : 완전 이진트리면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조
우선순위는, 값이 큰 순서대로 매겨진다~
최소 힙(Min Heap) : 완전 이진트리면서, 루트 노드로 올라갈수록 값이 작아지는 구조
우선순위는, 값이 작은 순서대로 매겨진다~
최대 힙이던 최소 힙이던
루트 노드에는우선순위가 높은 것이 자리잡게 됨!!
🤔 힙에 데이터를 어떻게 저장하는 건데?
일단, 최소 힙에 저장할 경우부터 살펴보자.
위와 같은 최소 힙에 3이라는 노드 하나가 들어오게 된다면?
→ 일단 들어오는 새로운 노드를 우선순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장한다.
(7의 left child)
이런 과정을 거쳐 3이 자리바꿈이 완료됨.
그래서, 이걸 코드로 어떻게 작성하냐?
→ 배열로 구현하라!
(엥? 근데 배열 말고 힙으로 구현하라며..)
힙을 배열로 구현하라고~ !!
주의
→ 힙을 배열로 구현할 때는, 인덱스 1부터 시작하라. 직관적이고, 다루기 용이하니까!
(우선순위 1~2~ 이런 식~)
#include<stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int heap[MAX_SIZE];
void push(int item,int*n)
{
int i= 0;
i=++(*n);
/* 개념은 부모-자식 간 비교하면서 즉시 서로 자리를 바꾸는 것이지만 */
/* 실제 코드 구현상에서는 들어올 자식보다 작았던 부모는 먼저 그 자리로 바꾼 뒤 */
/* while문 빠져나올 때 새로 들어올 자식을 최종적으로 넣으면 됨. */
while ((i!= 1)&& item< heap[i/2]) {
heap[i]= heap[i/ 2];// 원래 자식 들어갈 자리에 부모의 값 저장
i= i/ 2;// 새로 들어올 자식이 기존 부모자리에 들어갈 것을 대비해 i를 반 줄임
}
heap[i]= item;
}
int main(void)
{
int input;
int n= 0, count= 0;
printf("Min Heap 구현 - 숫자를 입력하세요.\n");
printf("*****숫자 입력(-1을 입력하면 입력 종료)*****\n");
while (1)
{
scanf("%d",&input);
if (input==-1)
break;
push(input,&n);
count++;
}
printf("Level Order Traversal : ");
for (int i= 1; i<= count; i++) {
printf("%d ", heap[i]);
}
}Min Heap 구현 - 숫자를 입력하세요.
*****숫자 입력(-1을 입력하면 입력 종료)*****
1
2
3
4
5
-1
>> Level Order Traversal : 1 2 3 4 5🤔 힙에서의 데이터 삭제는?
우선순위 큐에서의 pop : 가장 우선순위가 높은 데이터를 빼낸다는 의미!
- 힙의 루트 노드를 반환하는 것과 같다~
- 힙의 구조를 유지해야하는 게 관건!!! (heapify)
int delete(int *n){
int first, temp, parent, child;
first = heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while (child <= *n) {
if ((child < *n) && (heap[child] > heap[child + 1]))
child++;
if (temp <= heap[child])
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return first;
}////main 함수 뒤에 이어서...
printf("\n\n최상위 노드 삭제(반환)값 : %d", delete(count));
printf("\n삭제 후 힙의 Level Order Traversal : ");
for (int i = 1; i <= count; i++) {
printf("%d ", heap[i]);
}Min Heap 구현 - 숫자를 입력하세요.
*****숫자 입력(-1을 입력하면 입력 종료)*****
1
2
3
4
5
-1
>> Level Order Traversal : 1 2 3 4 5
>> 최상위 노드 삭제(반환)값 : 1
>>> 삭제 후 힙의 Level Order Traversal : 2 4 3 5참고 자료
자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)
재귀함수와 스택 (자료구조)의 작동원리
인프런 - Do it! 알고리즘 코딩테스트 with C++
