본문 바로가기
반응형

전체 글340

[알고리즘] Sort - Heap의 응용, 우선 순위 큐(Priority queue) Sort - Heap의 응용, 우선 순위 큐(Priority queue) 큐는 여러개의 데이터를 넣을수 있는 컨테이너이다.데이터가 들어오고 나갈때는 First In First Out(FIFO) 구조를 가진다. 우선 순위 큐는 이러한 큐의 한종류로써최대 우선 순위 큐와 최소 우선 순위 큐로 나뉜다.우리는 최대 우선 순위 큐를 중심으로 알아보도록 하겠다. 최대 우선순위큐는 다음의 두가지 연산을 지원하는 자료구조이다.1) INSERT(x) : 새로운 원소 x 를 삽입2) EXTRACT_MAX : 최대값을 삭제하고 반환 반대로 최소 우선 순위큐는 EXTRACT_MAX대신 EXTRACT_MIN을 지원한다.MAX HEAP을 이용해서 최대 우선 순위 큐를 구현할 수있다. 먼저 INSERT에 대해서 알아보도록 하자위의.. 2017. 4. 19.
[알고리즘] Sort - 힙정렬(heap sort) - 2 Sort - 힙정렬(heap sort) - 2 이번 시간에는 heap과 heapify연산을 이용해서어떻게 heap 정렬을 할것인지 알아 볼것이다. 그 전에 정렬을 하기 위해서는 heap을 만들어야한다.정렬할 1차원 배열을 complete binary tree로 해석한다tree로 만든다는 것이 아니라 개념적으로 받아들인다는 뜻이다. complete binary tree는 heap property를 만족하지 않기때문에heap은 아니다.그러므로 부모가 자식보다 크다 라는 조건이 자동으로 성립되지 않는다. 따라서, 정렬의 첫번째 조건은 complete binary tree을 heap으로 만드는 것이다.leaf가 아닌 그 다음 레벨의 노드에서부터 heapify 연산을 통해서 heap으로 만들어준다. 1234BUI.. 2017. 4. 19.
[알고리즘] Sort - 힙정렬(heap sort) - 1 Sort - 힙정렬(heap sort) - 1 어원인지 모르겠지만 쌓아놓은 더미가 heap의 사전적 의미이다. 이번시간에는 힙 정렬에 대해서 알아보자힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는정렬 알고리즘이다.(여기서 힙은, 메모리 영역인 힙과는 다른 말이다) 힙 정렬의 특징은 다음과 같다.1)최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.2 )힙 정렬은 알고리즘을 구현하는데 추가 배열이 필요하지 않다.3) 힙 이라는 자료구조를 이용해서 정렬을 한다. 따라서 알고리즘을 구현하기 앞서, 힙 이라는 자료구조에 대해알아보도록 하자 힙(Heap)은 1) complete binary tree 이면서2) heap property를 만족해야 한다. complete binar.. 2017. 4. 19.
[알고리즘] Sort - 퀵정렬(Quick sort) Sort - 퀵정렬(Quick sort) 퀵 정렬은 합병 정렬과 동일하게 분할정복법을 사용하나방법에서 차이를 보인다. 퀵 정렬에서는 정렬할 데이터가 주어지면하나의 값을 기준값(pivot)으로 사용하여 정렬을 실행한다.어떤 값을 기준값으로 잡는냐가 퀵정렬 성능의 관건이다. 1) 분할하나의 값을 피봇으로 선정 한 후, 데이터들을 피봇보다 큰 값과 작은값으로 분류한다.그렇기 때문에 합병정렬과 같이 반으로 갈라지는 것을 보장하지 않는다.그렇기 때문에 기준값에 따라 최악/최선의 상황이 나뉜다. 2) 정복분할한 양쪽을 각각 재귀로 퀵 정렬한다. 3)합병할일이 없다.이미 분할과 정복 과정에서 정렬이 완료되었기 때문이다. 위의 과정들을 표현한 그림이다.파티션 후에는 재귀적으로 정렬해주면 되기때문에결국 퀵 정렬에서 중요.. 2017. 4. 19.
[알고리즘] Sort - 합병정렬(Merge sort) Sort - 합병정렬(Merge sort)​ 앞서 비교적 간단하지만 효율적이지 않은 정렬 방법을 살펴보았다그 다음으로 합병 정렬과 퀵, 힙 정렬에 대해 알아보자 그 중에 합병과 퀵 정렬은 분할정복법이라는 동일한 정렬을 사용하는 알고리즘이다 분할정복법이라는것은예를들어, 한 나라가 다른 나라를 정복할때 한꺼번에 침략하지않고조금씩 영토를 쪼개어 각각을 하나씩 정복 하는것과 비슷한 것이다.영어로는 divide and conquer라고 한다. 좀 더 간단하게 말하자면 주어진 문제를 3단계에 걸쳐서 해결하는것이다그 순서는 다음과 같다. 1단계(분할)해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할한다. 2단계(정복)각각의 작은 문제를 해결한다 3단계(합병)작은 문제의 해를 합하여(merge) 원래 문제에 대한.. 2017. 4. 19.
[알고리즘] Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) 컴퓨터 알고리즘의 가장 기본이 되는 것이 정렬 알고리즘이다.그 종류는 여러가지가 있는데 위와 같은 특징이 있다. 이 중에서 3개의 기본적인 정렬 알고리즘을 살펴 보자 선택 정렬 먼저 선택정렬이다이중에서 가장 큰 값을 찾는다그 후에 가장 큰 값과 맨 마지막 값의 자리를 바꾼다.그럼 결과적으로 가장 큰값이 맨 끝자리로 오게 된다. 그렇다면 마지막 값에 대해서는 더이상 신경쓰지 않아도 된다.이후에 남아있는 4개의 데이터에 대해서다시 가장 큰 값을 찾아 4번째 위치에 있는 값과 자리를 바꿔 준다. 이와 같은 알고리즘을 마지막 1개의 값이 남을 때까지 반복해준다면결론적으로 오름차순, 작은값을 맨 끝자리로 보내면 내림차순의 순서로정렬이 가능하다. 12345678.. 2017. 4. 19.
[알고리즘] Recursion의 응용 - 멱집합(power set) Recursion의 응용 - 멱집합(power set) 어떤집합의 모든 부분 집합의 집합을 멱집합이라고 한다. 멱집합을 계산하기에 앞서 기본적으로, 집합의 부분집합을 살펴보자원소의 개수가 n개인 모든 가능한 부분집합의 개수는 2^n개이다.각각의 원소에 대해서 그 원소를 포함하던가, 포함하지 않던가라는 2개의 경우의수를 적용한다면 2x2x...xN 이므로 결국 2^n이 된다. 그렇다면 크기가 N인 모든 부분집합의 집합을 어떤식으로 구하는 것일까 Recursion을 이용한다면 다음과 같은 조건을 세운다{a,b,c,d,e,f} 의 모든 부분집합을 나열한다고 했을 때 1) a를 제외한 {b,c,d,e,f}의 모든 부분집합을 나열하고2) {b,c,d,e,f}의 모든 부분 집합에 {a}를 추가한 집합을 나열한다. .. 2017. 4. 19.
[알고리즘] Recursion의 응용 - n queens Recursion의 응용 - n queens 가로세로 크기가 N인 2차원 배열(체스판)이 주어진다이 체스판에 N개의 말을 놓는데, 그중에 어떤 2개의 말도 동일한 행이나 열, 대각선에 오지 않게 배치하는것이 n queens 문제이다. 가장 기본적으로 생각 되는것은동일한 행, 열에 배치가 되지 않으므로 한 행, 열당 1개의 말을 배치할수 있다는 것이다 행을 기준으로 생각해 봤을때1개의 행에 놓일수 있는 경우의 수는 4 가지이다. 따라서, 1개의 행에 하나씩 놓으며 그것이 해가 아닐경우 체스말을 치우고바로 전의 행으로 돌아와 다른 경우의 수를 살핀다.이와 같은 방법을 backtracking이라고 한다. backtracking은 자신이 지나온 궤적을 되돌아온다는 것이다즉, 어떠한 결정을 내리다가 안된다는 것이.. 2017. 4. 19.
[알고리즘] Recursion의 응용 - Counting Cells in a Blob Recursion의 응용 - Counting Cells in a Blob Counting Cells in a Blob(인접한 셀의 개수 찾기)의 조건 1) 입력으로 하나의 바이너리 이미지가 주어진다(흑백 이미지라고 생각)2) 각 픽셀은 background pixel(흰색) 이거나 image pixel(파란색)이다3) 서로 연결된 image pixel들의 집합을 blob이라고 한다.4. 상하좌우, 대각선 방향도 연결된 것으로 간주 입력- NxN의 2차원 배열 그리드- 하나의 좌표(x,y) 출력- 픽셀(x,y)가 포함된 blob의 크기- (x,y)가 어떤 좌표에도 속하지 않을 경우에는 0을 리턴 123456789현재 픽셀이 속한 blob의 크기를 카운트 하려면 현재 픽셀이 image color가 아니라면 0.. 2017. 4. 18.
반응형

티스토리툴바