IT's me

[자료구조] 우선순위 큐의 완성

힙을 사용하여 삽입, 삭제 등 우선순위 큐와 근접하게 완성해 보았다.

하지만 지금까지 구현한 우선순위 큐에는 한가지 문제점이 있는데

데이터와 함께 우선순위에 대한 정보를 사용자가 직접 지정해주어야 한다는 것에 있다.

주어진 데이터를 기반으로 우선순위가 정해지며 우선순위가 정해지는 기준을 사용자가 지정해주는 것이 좋은 자료 구조이다.

자 그럼 우선순위를 정하는 기준의 정보를 담은 함수를 정의하여 함수 포인터로 넘겨주는 식의 구현을 해보자.

1. 구조체 재정의

우선 기존의 힙 구조체를 지우고 함수 포인터를 멤버로 갖는 새로운 힙 구조체를 생성하자.

이 함수 포인터로 전달된 정보를 통해 우선순위를 정할 것이고, 정의 기준은 사용자의 필요에 따라 정한다.

위의 코드를 보면 함수 포인터의 선언과 멤버 선언이 각각 2개로 나누어져 있는데,

typedef로 함수 포인터를 선언하는 두 가지 방법이 있음을 보여주기 위한 것이다.

02. 초기화 함수

초기화 함수에 우선 순위를 정하는 기준에 대한 정보를 담은 함수를 적용시키고 있다.

02. 우선순위가 높은 트리 찾기 함수

원래는 사용자가 정해준 우선숭위에 대한 정보를 통해 처리되었다면

지금은 자용자가 정해준 함수를 통해 우선순위에 대한 처리가 이루어지고 있다.

03. 삽입

삽입 또한 사용자가 지정한 우선순위에 의해 처리되던 기존 방식과는 달리

사용자가 지정한 함수에 의해 우선순위가 가려지며, 새 노드의 위치가 결정되고 있다.

매개변수로 원래는 pr이라는 우선순위 정보가 전달되었지만 지금은 없어졌다.

04. 삭제

삭제 또한 삽입과 마찬가지로 진행된다.

05. 메인

초기화를 할 때 우선순위 기준 정보를 담은 함수를 적용시켜주고 있다.

지금까지 우선순위 큐의 이해와 구현과정에 대해 알아보았다.

다음 부터는 이진 탐색트리에 대해 공부해보도록 하겠다.

BFS 알고리즘 문제 : 미로 탐색 (백준)

약 2주전 이 문제를 DFS 알고리즘으로 풀어본 적이 있다.

하지만 시간초과가 떠서 상당히 난감한 적이 있었는데

이를 BFS 알고리즘으로 풀어보니 상당히 쉽게 풀렸다.

해가 없는 경로로도 쭉쭉 들어가서 수행시간을 폭발 시키는 DFS 알고리즘의 단점을 실감할 수 있었고,

DFS 알고리즘에 비해 BFS 알고리즘은 공간 복잡도는 상당하지만 항상 최단 경로를 보장한다는 장점을 체험할 수 있었다.

미로 탐색이라는 알고리즘은 DFS, BFS 알고리즘으로 풀어봄으로써

약간씩 헷갈렸던 두 알고리즘의 장단점을 명확하게 할 수 있었다.

미로 탐색 (백준)

1. 필요한 변수 선언

2. 초기화

3. 인큐, 디큐, 비었는지 확인, 가능한 경로인지 확인

4. BFS 알고리즘

5. 메인

6. 참고

DFS 알고리즘과 BFS 알고리즘의 장단점을 잘 정리해놓은 것 같아 링크를 가져왔다.

http://blog.naver.com/jjuncoder/220797012420

[자료구조] 우선순위 큐의 구현(3) - Delete , Insert

오늘은 우선순위 큐의 삽입, 삭제 과정에 대해 알아보도록 하겠다.

저번 시간에 두 자식 노드 중 우선순위가 높은 놈을 찾고, 자식이 없다면 0을 리턴하는 함수를 정의했다.

그 함수를 적극 활용하여 Delete 과정을 이해해 보도록 하자.

Delete 과정을 잘 이해한다면 Insert 과정 또한 쉽게 이해할 수 있을 것이다.

1. 우선순위 큐의 Delete 구현

2. 우선순위 큐 삭제의 과정

1. 가장 마지막 노드를 추출한다.

2. 인덱스 1번에 위치한 노드가 삭제되기 때문에 그 밑의 자식노드들과 마지막 노드의 우선순위를 비교한다.

3. 자식노드의 우선순위를 비교할 때, 저번 포스팅에서 정의한 GetHiPriChildIDX() 함수를 사용한다.

4. 현재의 노드가 마지막 노드보다 우선순위가 높다면 한칸 위로 이동한다. (1번이 빠졌기 때문에 공간을 메운다.)

5. 마지막 노드보다 우선순위가 낮거나, 자식노드가 더이상 없을 때, 마지막 노드의 자리가 결정된다.

3. 그림으로 이해(..?)

우선순위 큐의 Delete 구현 소스 우측에 적혀있는 번호와 위 그림의 번호의 동작과 일치한다. (그림이 쪼금 애매하다.)

쉽게 말해서, 힙의 마지막 데이터를 빼서, 가장 위쪽에서부터 차례로 비교를 해오면서 내려온다.

그리고 마지막 노드보다 우선순위가 높다면 한칸씩 위로 이동하게 해주는 것이다.

4. 우선순위 큐의 Insert 구현

5. 우선순위 큐의 삽입 과정

1. 힙의 마지막 자리에 새로운 노드를 배정 (실제로 넣지는 않고 가정만 한다.)

2. 그의 부모노드와 우선순위를 비교하여 위치 변경

3. 삭제의 과정이 위에서 밑으로 였다면, 삽입의 과정은 밑에서 위로

오늘은 우선순위 큐의 Delete와 Insert 과정에 대해 알아보았다.

다음 포스팅에서는 좀 더 유연성있게 우선순위를 정하는 힙에 대해 알아보도록 하겠다.