본문 바로가기

프로그래밍/알고리즘

 (45)
힙 정렬에 대해(2) 보호되어 있는 글입니다.
힙 정렬에 대해(1) 힙 정렬 (Heap Sort) Heap Sort- 최악의 경우 시간복잡도 O(n logn)- Sort in place -> 추가 배열이 필요하지 않다.- 이진 힙(binary heap) 자료구조를 사용하여 정렬을 수행한다. Heap의 정의- 조건1) complete binary tree이여야 한다.2) heap property를 만족해야 한다.- property는 아래 두 조건 중 하나를 만족해야 한다.1) Max heap property부모는 자식보다 크거나 같다2) Min heap property부모는 자식보다 작거나 같다. Full binary trees와 Complete binary trees- full binary trees모든 레벨에 노드들이 전부 차있는 상태의 트리이다.- complete b..
정렬 알고리즘 - 퀵 정렬 퀵 정렬 (Quick Sort) 분할 정복법- 분할 : 배열을 아래의 조건이 되도록 두 부분으로 나눈다. (Pivot을 이용한다.)lower part elements ≤ upper part elements- 정복 : 각 부분을 순환적으로 정렬한다.- 합병 : 수행하지 않는다. 퀵 정렬 수행 과정- 정렬할 배열이 주어진다. 이 때 마지막 수를 기준 (pivot)으로 삼아둔다.31 8 48 73 11 3 20 29 65 15(pivot)- 기준보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치 (분할)한다.8 11 3 15 31 48 20 29 65 73- 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다. 퀵 정렬 슈도 코드quickSort (A[], p, r) {if (p < r) {q..
정렬 알고리즘 - 합병 정렬 합병 정렬 (Merge Sort) 분할 정복법- 분할정복법은 본질적으로 순환 함수를 사용하여 문제를 해결하려 한다.- 분할 : 해결하려하는 문제를 작은 크기의 동일한 문제들로 분할한다.- 정복 : 각각의 작은 문제를 순환적(Recursion)으로 해결한다.- 합병 : 작은 문제의 해를 합하여(Merge) 원래 문제애 대한 해를 구한다. 합병 정렬- 데이터가 저장된 배열을 절반 나눈다.- 각각을 순환(Recursion)방식으로 정렬한다.- 정렬된 두 개의 배열을 합쳐 전체를 정렬한다.- 합병 정렬의 진행 과정 - 분리된 두 배열을 병합- 이미 i배열과 j배열은 정렬이 되어있는 상태이고 k배열에 두 배열을 합치기 위해서는 작은 순서대로 넣어주어야 한다.- i와 j배열의 가장 작은 원소들끼리 비교하여 더 작은..
기초 정렬 알고리즘 기본 정렬 알고리즘 종류 예시- Bubble sort ┒- Insertion sort ├ simple, slow- Selection sort ┘- Quick sort ┒- Merge sort ├ fast- Heap sort ┘- Radix sort = O(N) Selection Sort- 각 루프마다1) 최대 원소를 찾는다.2) 최대 원소와 맨 오른쪽 원소를 교환한다.3) 맨 오른쪽 원소를 제외한다.- 하나의 원소만 남을 때까지 위 루프를 반복한다.- 선택 정렬의 진행 과정 - 슈도 코드selectionSort (A[], n) {for last = 1; i--) { save = 0; bw.write(Arrays.toString(array) + "\n"); bw.flush(); for (int j = 0; j
Recursion 응용(4) 멱집합 (powerset) 의미- 어떤 집합의 모든 부분집합들의 집합이다. - data = {a, b, c, d}의 모든 부분집합을 출력한다면(멱집합)∅, a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd가 있다.이는 $2^4$개로서 총 16개라 할 수 있다. 멱집합을 구하는 방법- {a, b, c, d, e, f}의 모든 부분집합을 나열하고자 한다.1) a를 제외한 {b, c, d, e, f}의 모든 부분집합들을 나열한다.2) {b, c, d, e, f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.-이는 곧 a를 포함하지 않은 부분집합의 수인 $2^5$와 포함한 부분집합의 수인 $2^5$가 합해져 총 $2^6$개가 된다. - {b, c..
Recursion 응용(3) N Queens Problem 문제- N X N배열의 체스판에 N개의 말을 서로 동일한 행이나 열에 놓이지 않도록 배치하는 문제- 문제를 체계적으로 해결하기 위해서는 back tracking기법을 이용하는 것이 좋다. 상태 공간 트리- 찾는 해를 포함하는 트리이다.- 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당하고, 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다.- 찾고자 하는 해를 위해 반드시 모든 노드를 탐색해야할 필요는 없다. 이는 가능성이 없는 노드는 생략하고 (non-promising, infeasible)탐색을 진행해 효율성을 높일 수 있다는 것을 의미한다. Back Tracking (되추적 기법)- 자신이 행했던 경로를 다시 되돌아간다는 것으로 가장 최근에 결정..
Recursion 응용(2) Counting cells in a Blob 문제 조건- Binary 이미지- 각 픽셀은 background pixel이거나 image pixel이다.- 서로 연결된 image pixel의 집합을 blob이라 칭한다.- 상하좌우뿐 아리라 대각으로 연결된것도 같은 집합이라 간주한다.- 인접한 8개 픽셀에 대해서 북, 북동, 동,... 순서의 시계방향으로 탐색한다.- 입력N * N크기의 2차원 그리드하나의 좌표 (x, y)- 출력픽셀 (x, y)가 포함된 blob의 크기(x, y)가 어떤 blob에도 속하지 않을 경우에는 0 순환적으로 생각해보기- 현재 픽셀이 속한 blob의 크기를 카운트하려면현재 픽셀이 image color가 아니라면0을 반환한다.현재 픽셀이 image color라면현재 픽셀을 우선 카운..

티스토리툴바