그리디 알고리즘(Greedy Algorithm)이란? 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다. 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다. 주요 속성 1. 탐욕 선택 속성(Greedy Choice Property) 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결..
문법
힙 정렬이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 - 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 과정 설명 - 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다. - 내림차순을 기준으로 정렬 - 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. - 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다. 특징 장점 - 시간 복잡도가 좋은편 - 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때..
병합 정렬이란? 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다. - 분할 정복(divide and conquer) 방법 - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. - 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 다음의 단계들로 이루어진다. - 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. - 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으..
셸 정렬이란? 삽입정렬을 보완한 알고리즘이다. - 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안 - 삽입 정렬의 최대 문제점: 요소들이 삽입될 때, 이웃한 위치로만 이동 - 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. - 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 ‘간격(gap)’ 이라고 한다. - 간격의 초깃값: (정렬할 값의 수)/2 - 생성된 부분 리스트의 개수는 gap과 같다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 ..
퀵 정렬이란? 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다. - 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 - 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. - 분할 정복(divide and conquer) 방법 - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. - 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 퀵 정..
선택 정렬이란? 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 - 손안의 카드를 정렬하는 방법과 유사하다. - 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. - 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. - 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, ..
