IT's me

[자료구조] 우선순위 큐의 구현(1) - 배열을 기반으로 한 힙의 구현

힙은 배열을 기반으로 구현하는 대표적인 이진트리이다.

-> 연결 리스트 기반은 마지막 위치에 새로운 트리를 추가하는 것이 쉽지 않다.

-> 배열을 기반으로 구현하는 이유는 힙의 마지막 위치에 추가하는 것이 쉽기 때문이다.

(우선순위 큐를 위한) 힙의 구현

1. 구현의 편의를 위해 배열의 인덱스 0은 비워둔다.

2. 왼쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2

3. 오른쪽 자식의 노드의 인덱스 값 --> 부모 노드의 인덱스 값 x2 +1

4. 부모 노드의 인덱스 값 --> 자식 노드의 인덱스 값 /2 --> 정수형 나눗셈

꼭 알아야 할 점

1. 힙은 완전 이진 트리이다.

2. 배열 기반 (인덱스 0은 비워두기)

3. 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

4. 노드의 고유 번호가 저장되는 배열의 인덱스 값이 된다.

5. 우선순위를 나타내는 정수값이 적을수록 높은 우선순위를 나타낸다고 가정!

--> 힙에 저장된 노드의 개수와 마지막 노드의 고유 번호가 일치하기 때문에

마지막 노드의 인덱스 값을 쉽게 얻을 수 있다. 

(우선순위 큐를 위한) 힙의 헤더파일

오늘은 우선순위 큐의 구현을 위한 (우선순위 큐에 치우쳐진) 힙 구현에 대해 간단하게 알아보았다.

계속 해서 우선순위 큐의 구현에 대해 다룰 것이며, 위의 헤더파일에 다뤄진 함수들을 차근차근 구현해 나가도록 하겠다.

[자료구조] 우선순위 큐의 이해(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와 동적 계획법을

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

DFS 알고리즘 - 점프 문제 (백준)

DFS , BFS 알고리즘 항목에 있길래

DFS 알고리즘으로 풀어 보았다..

답이 맞는지 안맞는지는 모르겠지만

일단은 예제는 맞고.. 10분 컷 했으나 시간초과..

예전에 DFS 알고리즘 문제를 풀다가

시간 초과가 계속 떠서 몇 시간을 씨름하다

나중에 검색해보니 DP 문제였던 기억이 있어서

이번에도 뭔가 느낌이 싸해서 바로 검색을 해보니

아니나 다를까 DP문제...

사실 문제를 풀 때, 쓸데없는 동작들이 있어서

(이미 DFS를 수행한 곳을 또 다시 들렸을 경우, 똑같은 작업을 반복)

사실 DP문제가 아닌가 생각도 했지만, 일단은 DFS로 풀어보았다.

DFS 알고리즘 문제 - 점프 (백준)

DFS에 DP 배열을 넣어서 풀어보면 어떻까 하고 풀었지만

DP 배열을 넣는 순간 코드가 DP로 서서히 바뀌어 나가더라..

DP로 다시 풀어서 올려야 겠다고 생각해서 일단 오답 코드를 올려본다.

음.. DFS 알고리즘으로 한번 풀어 보았으니

DP로 풀어서 다시 올리도록 하겠다.

[자료구조] 이진 트리의 순회(Traversal) (2)

오늘은 아진트리의 순회 방법에 있어서

좀 더 유연한 동작방식을 적용하기 위해서

함수 포인터를 이용해 보도록 하겠다.

저번 포스팅이 재귀의 개념이 핵심이었다면

이번 포스팅은 함수 포인터가 핵심이 된다.

가장 첫 줄을 보면 함수 포인터가 선언이 되어있다.

반환형은 void 그리고 매개 변수는 BTData타입이다.

이 함수 포인터를 순회 함수의 두 번째 매개변수로 넣어준다.

그리고 데이터를 다루는 부분을 이 함수 포인터로 대체한다.

이제는 인자로 들어온 함수에 따라 데이터를 다루는 방식이 달라진다.

ShowIntData(int Data) 함수를 인자로 전달해주고 실행

이로써 이진 트리의 순회가 좀 더 유연성을 가지게 되었다.

데이터를 다루는 방식이 달라지더라도 함수를 재 선언할 필요가 없고

함수를 하나 선언해서 넘겨주기만 하면 되는 것이다.

이는 STL의 알고리즘에 쓰이는 콜백 메커니즘의 기본이다.

이러한 동작 원리를 잘 이해해서 좀 더 유연한 프로그래밍을 할 수 있도록하자.

[자료구조] 이진 트리의 순회 (Traversal) (1)

앞서 이진 트리를 만드는 도구에 대해 알아보고,

간단하게 이진 트리를 만들어보기까지 했다.

그렇다면 만들어진 이진 트리의 정보를

가져오기 위해 어떠한 방법을 써야할까?

이진 트리의 순회를 이용하여 트리의

루트부터 단말노드까지 모든 데이터를

순회하며 정보를 가져올 수 있다.

이진 트리의 순회를 하기 위해서는 재귀의 개념이 필요하다.

들어가기에 앞서 순회의 세가지 방법에 대해 알아보도록 하자.

위 그림 처럼 노드가 세개밖에 없는 경우는 매우 간단하다.

하지만 트리의 깊이가 깊은 경우에는 상당히 복잡할 수도 있다.

만약 중위순회 방법으로 순회를 구현했다면

트리의 깊이가 얼마가 되었든간에 순차적으로

중위 순회를 하며 모든 데이터를 가져올 수 있어야 한다.

ex) 중위 순회의 구현

여기서 재귀의 개념이 사용되는데,

처음 루트노드의 주소값이 전달이되고

함수가 시작이 되면

1. 종료 조건을 체크한다.

현재의 노드가 아무런 데이터를 가지고 있지 않으면 리턴하여 함수를 종료한다.

2. 데이터를 가진 노드라면 (공집합 노드가 아니라면)

자신의 왼쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

3. 자신의 왼쪽 트리의 순회가 끝나고 (2에서 실행했던 함수가 끝나면)

자신이 가진 데이터를 출력한다.

3. 데이터를 출력한 후 (중위 순회이기 때문에 왼쪽에서 오른쪽)

자신의 오른쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

4. 함수 종료

ex) 중위 순회

이진 트리의 중위 순회 결과

위의 중위 순회 동작 순서

오늘은 이진 트리의 순회에 대해 알아보았다.

재귀의 개념이 들어가다 보니까 살짝 어렵게 느껴지기도 한다.

다음에는 함수포인터를 이용하여 이진 트리의 순회를

좀 더 세련되게 표현해보도록 하겠다.

다이나믹(동적 계획법) 알고리즘 기초 문제 : 계단 오르기 (백준)

이번 문제를 풀면서 느낀 점은

다이나믹(동적 계획법) 알고리즘을 풀 때에는

답을 저장하는 DP배열이 꼭 필요하다는 것이다.

답을 담을 변수를 하나만 선언해서 이리저리 굴려보다가 결국 제시간에 풀지 못했다.

동적 계획법은

첫 째, 그 전에 구해놓은 답을 사용하여 현재의 답을 찾는 것!

둘 째, 구한 답을 저장할 DP배열을 사용할 것!

셋 째, 문제를 잘 읽고 규칙을 찾아 내는 것!

지금까지 다이나믹(동적 계획법) 알고리즘을 풀면서 중요하다고 느낀 부분이다.

익숙해질 때까지 반복적으로 문제를 풀어보는 것이 중요할 듯 하다.

계단 오르기 (백준)

문제를 처음 딱 접했는 때에는

DFS 알고리즘으로도 풀 수 있겠다 생각했지만,

동적 계획법으로 푸니 정말 간단하게 답이 나왔다.

짧은 코드로 많은 것을 해내는 코드는 그 만큼 어렵다고 했다.

위의 코드는 매우 간단해보이지만, 이 문제를 DFS 알고리즘으로

푼다고 생각했을 때는, 이렇게 간단한 코드로 끝나지 않을 것이다.

(물론 DFS도 그리 긴 코드는 나오지 않을 것이다.)

다이나믹 (동적 계획법) 알고리즘 기초 문제 : 숫자 삼각형 (백준)

첫 문제를 풀고나서 푸니까 확실히 시간이 단축된다.

원리에 좀 더 익숙해진다면 점점 더 단축되리라 믿는다.

다이나믹(동적 계획법) 알고리즘 기초 : 숫자 삼각형

RGB 거리라는 비슷한 문제를 풀고

바로 풀어서 그런지 시간이 15분 밖에 안걸렸다.

RGB와 같은 원리지만 위에서 아래로 향했던 것과 달리

이 문제는 아래에서 위로 계산하며 올라가야 한다.

다시한번 말하지만 다이나믹(동적 계획법) 알고리즘의 핵심은

구해놓은 답을 활용하여 현재의 답을 차근차근 찾아 나가는 것!!

꼭 기억하고 문제를 푼다면 더욱 이해하기 쉬울 것이다.

가장 밑의 바로 위층 부터 시작해서

(가장 밑 층의 데이터를 이용하여 밑의 바로 위층을 갱신하기 때문에 여기부터 시작한다.)

최대 값만을 골라 그 위치에 더하면서 갱신한다.

그렇다면 현재층의 모든 숫자는 아래층으로부터 올라온 최대값을 골라서 더하게 되며,

결국 꼭대기에서는 가장 최대값만을 골라서 더한 값이 저장되게 된다.

다이나믹(동적 계획법) 알고리즘은 코드의 크기는

DFS, BFS보다 훨씬 간결하다. 하지만 두 알고리즘 보다

훨씬 많은 고민을 해야하는 것은 분명한 사실인듯 하다.

다이나믹 (동적 계획법)알고리즘 기초 문제 : RGB 거리 (백준)

다이나믹 (동적 계획법) 알고리즘의 기초 문제를 풀어 보았다.

핵심은!! 그 전에 저장되었던 답을 끌어다가 현재의 답을 도출한다는 점!!

딱 저거 하나만 알면되는데.. 그 과정을 생각하기가 정말 쉽지 않다.

동적 계획법 기초 문제 : RGB 거리

몇줄 안되는 코드이지만 푸는 데 시간이 꽤 걸렸다..

잊지 말자!

처음 부터 차근차근 답을 구해서

구한 답을 바탕으로 계속해서 답을 찾아 나가는 것!

이번 문제는 기준을 잡는 것이 중요해 보였다.

처음에 집을 어떤 색으로 칠할 것이냐?

빨강, 초록, 파랑으로 모두 칠하면서 답을 찾아가봄

다이나믹 (동적 계획법) 알고리즘은

항상 풀 때마다 많은 고민을 하게 하는 것 같다.

꾸준히 풀어나가야 겠다는 생각이 든다.