IT's me

[자료구조] 우선순위 큐의 이해(2)

1. 우선순위 큐를 구현하기 위해 힙(heap)을 사용한다.

2. 우선순위 큐는 꼭 만족해야 하는 조건이 있다.

(1) 완전 이진 트리

(2) 자식노드의 우선순위 <= 부모노드의 우선순위

3. 힙(heap)의 삽입 과정 (출처 : 윤성우의 열혈 자료구조)

4. 힙(heap)의 삭제 과정 (출처 : 윤성우의 열혈 자료구조)

--> 루트의 우선순위가 가장 높기 때문에 (만족 조건2) 루트를 빼준다.

--> 마지막 노드가 루트 노드로 위치한 뒤, 자기자리를 찾아가는 과정에서 두 서브트리 중 우선순위가 높은 쪽과 교환하게 된다.

5. 삽입과 삭제 과정에서 보이는 성능 평가

(1) 배열 기반 우선순위 큐                                 삽입 : O(n)            --> 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(1)

(2) 연결 리스트 기반 우선순위 큐                     삽입 : O(n)             -- 저장된 데이터 수 만큼 비교가 일어난 뒤에 자리를 찾게 된다.

  삭제 : O(n)

(3) 힙(heap) 기반 우선순위 큐                         삽입 : O(log2n)

  삭제 : O(log2n)

--> 4층 높이의 힙이 있다고 치면, 이는 각각의 우선순위에 따라 위치가 정해져 있을 것이다.

--> 삽입을 하기 위해서 루트 노드부터 우선순위를 비교를 해나간다.

--> 한 층에 한번씩만 비교연산을 하게 되면 자리를 찾게된다. (트리는 내려가면서 자리가 결정되는 구조이다.)

[자료구조] 우선순위 큐의 이해(1)

1. 큐 (queue)

큐는 대표적인 자료구조 중 하나이고 선입 선출(FIFO)의 동작을 한다.

즉, 들어간 순서대로 하나씩 빠져나오는 동작 구조이다.

때문에 큐는 선형 구조로 이루어져 있다.

2. 우선순위 큐 (priority queue)

이름이 똑같다고 해서 큐의 연장선에 있다고 생각할 수 없다.

우선순위 큐는 들어가는 순서와 나오는 순서가 상관이 없다.

들어가는 순서에 상관없이 우선순위가 가장 높은 놈이 가장 먼저 나오게 되어있다.

때문에 우선순위 큐는 비선형 자료구조로 이루어져있으며, 큐가 아닌 트리의 연장선상에 있다고 생각해야 한다.

3. 큐의 두 가지 연산

enqueue : 큐에 데이터를 삽입한다.

dequque : 큐에서 데이터를 꺼낸다.

4. 우선순위 큐의 두 가지 연산

enqueue : 우선순위 큐에 데이터를 삽입한다.

dequeue : 우선순위 큐에서 데이터를 꺼낸다. (우선순위를 근거로 deququq 연산이 진행된다.)

어떤 근거로?? --> 프로그래머가 결정할 수 있어야 한다.

5. 우선순위 큐의 구현 방법

1. 배열 기반                --> 구현이 간편하다. 데이터가 많아질 수록 이동과 비교에 대한 부담이 커진다.

2. 연결 리스트 기반    --> 구현이 간편하다. 이동에 대한 부담은 없으나 비교에 대한 부담은 여전하다.

3. 힙(heap) 기반        --> 이동과 비교에 대한 부담이 없다.

6. 그렇다면 힙(heap)이란?

완전 이진 트리이다.

--> 위에서 아래로 왼쪽에서 오른쪽으로 차곡차곡 저장해나가는 이진 트리..

(1) 최대 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

(2) 최소 힙 - 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 작거나 같아야 한다.

오로지 루트 노드와 자식 노드간의 값만 비교해서 저장해주면 된다.

같은 레벨의 노드에는 어떠한 정렬 기준이 없다.

우선순위 큐가 무엇인지 간단하게 알아보는 시간을 가졌다.

다음 포스팅에는 우선순위 큐를 직접 구현해보도록 하겠다.

DFS 알고리즘, 다이나믹(동적 계획법) 알고리즘 문제 - 점프 (백준)

DFS와 동적 계획법을 동시에 써서 풀어야 했다.

문제가 쉬워서 금방 금방 푸나 싶었는데..

정말 함정이 많은 문제였다..

첫 번째 함정.. 0이 종착점 말고도 존재할 수 있다는 것..

두 번째 함정.. 경로의 수가 겁나 크게 나올 수 있기 때문에

int로는 답을 담을 수가 없어 long long로 선언해야 한다는 것..

문제를 꼼꼼히 읽지 않아서 정말 고생할 뻔 했다..

DFS 알고리즘, 다이나믹(동적 계획법) 알고리즘 문제 - 점프 (백준)

DFS와 동적 계획법의 개념이 동시에 들어가 있다.

이번 문제는 알고리즘이 어려웠다기 보다

문제를 꼼꼼히 읽지 않아서 소요된 시간이 더 많았다.

문제를 꼼꼼히 읽는 습관을 들여야겠다.

아무튼 문제는 DFS와 동적 계획법을

연습하기에는 정말 좋은 문제인 것 같다.