알고리즘

[Algorithm] 이진 탐색(Binary Search) 알고리즘

Binary Search Idea 이진 탐색은 정렬된 배열이 주어질 때, 리스트의 중간값과 비교하면서 반씩 제외하며 원하는 값을 찾아가는 과정입니다. 주의할 점은, 이진 탐색 알고리즘은 정렬된 배열에만 적용 가능하다는 점입니다. 따라서 정렬되어있지 않다면 성능이 우수한 퀵 정렬을 통해 약 O(nlogn)의 시간을 들여 정렬을 한 뒤 이진 탐색 알고리즘을 적용해야 합니다. 이진 탐색의 과정을 살펴보면 아래와 같습니다. 중간 인덱스(middle)를 구한다. (첫번째 인덱스 + 마지막 인덱스) / 2 찾을 값(target)이 middle보다 작은 경우, middle과 그 이후 인덱스들을 검색 범위에서 제외한다. target이 middle보다 큰 경우, middler과 그 이전 인덱스들을 검색 범위에서 제외한다..

[Algorithm] 위상 정렬(Topological sort) 알고리즘

Topological sort 위상 정렬이란, 사이클이 없는 방향 그래프(DAG)를 방향성에 거스르지 않도록 순서대로 나열하는 것입니다. 대표적인 예시로, 선수 과목을 고려해서 학습 순서를 설정하는 것이 있습니다. 일반화학, 유기화학1, 유기화학2 라는 3과목이 있을 때, 아래의 학습 순서들 중 적절한 순서는 (2)가 될 것입니다. (1) 일반화학 -> 유기화학2 -> 유기화학1 (2) 일반화학 -> 유기화학1 -> 유기화학2 우선, 비순환 방향 그래프(DAG)에 대해 정리하겠습니다. 비순환 방향 그래프 (Directed Acyclic Graph) 위와 같이 방향 그래프이면서 사이클이 없는 그래프를 DAG라고 한다. DAG와 Topological sort 위상 정렬은 이러한 비순환 방향 그래프에서 정점들..

[Algorithm] 힙 정렬(Heap sort) 알고리즘

Heap sort Idea 우선 heap의 개념부터 정리하겠습니다. Heap 완전 이진트리 형태이며, 최대 힙과 최소 힙으로 나뉜다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리이고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리이다. 이러한 힙의 형태를 유지하면서 삽입과 삭제 연산이 가능하도록 해야하며, 이러한 연산을 heapify이라 한다. 힙과 이진 탐색 트리는 명확한 차이점을 가진다. 두 자료구조 모두 이진트리라는 점은 같지만, 노드 값이 다르게 구성된다. 이진 탐색 트리의 경우 가장 왼쪽의 리프노드가 가장 작고, 가장 오른쪽의 리프노드가 가장 큰 값을 가진다. 하지만 힙의 경우 부모와 자식 간의 값의 순서만 지키면 되기 때문에 차이점이 있다. Heap 표현..

[Algorithm] 계수 정렬(Counting sort) 알고리즘

Counting sort Idea 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 리스트를 생성 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력 간단히 정리하면, 주어진 리스트들의 수들이 몇 번 나왔는지 기록한 후, 앞에서부터 차례대로 나온 횟수만큼 출력하는 것입니다. When we use 계수 정렬은 다음의 제약 사항을 갖습니다. 데이터가 양수여야 한다. 값의 범위가 적당해야 한다. (메모리 issue) 이러한 제약 사항을 위반하지 않을 때, 값의 범위가 작은 경우 계수 정렬은 뛰어난 성능을 보입니다. 여타 다른 정렬 알고리즘을 살펴보면, 항상 비교 연산이 포함됩니다. 이러한 비교 연산은..

[Algorithm] 합병 정렬(merge sort) 알고리즘

Merge sort Idea 합병 정렬은 하나의 리스트를 크기가 균등한 리스트 두 개로 분할하고, 각 부분 리스트를 정렬(정복)한 후 다시 합병하는 방식입니다. 구체적으로 단계를 나누면 다음과 같습니다. 분할(Divide): 주어진 리스트를 같은 크기의 부분 리스트 2개로 분할한다. 정복(Conquer): 더 이상 분할이 불가능할 경우, 주어진 부분 리스트를 정렬한다. 결합(Combine): 정렬이 완료된 부분 리스트들을 다시 하나의 완전한 리스트로 합친다. Example 위에서 살펴본 3단계 중, 1단계인 분할의 경우 주어진 리스트를 같은 크기로 2개 나누는 일이므로 특별한 연산이 필요하지 않습니다. 하지만, 2,3 단계의 경우 특별한 연산이 들어가고 사실상 하나의 단계로써 구현됩니다. 즉, 합병 정렬..

[Algorithm] 퀵 정렬(Quick sort) 알고리즘

Quick sort Idea 퀵 정렬은 기본적으로 분할 정복 (Devide and Conquer) 기법과 재귀를 이용한 정렬 알고리즘입니다. Pivot이라는 것을 사용하여 정렬의 기준을 정하게 됩니다. 그리고 그 pivot을 기준으로 “작은 group”, “큰 group”을 나누고, 분할 정복 기법을 이용하여 각각을 해결하는 방식입니다. 6 1 5 11 16 [7] 10 13 위와 같은 숫자 배열을 정렬하고자 할 때, 아무 값이나 pivot으로 선정합니다. 저는 7을 선정하였습니다. pivot을 선정하면, 해당 pivot을 기준으로 작은 값들과 큰 값들을 분류하여 각각 왼쪽, 오른쪽에 위치시킵니다. 6 1 5 [7] 11 16 10 13 그럼, [6,1,5]는 작은 group, [11,16,10,13]은..

[Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘

선택 정렬 Idea 선택 정렬은 주어진 값들 중 최소값을 맨 앞으로 땡겨와서 정렬하는 방법입니다. 170cm, 180cm, 150cm, 160cm 예를 들어 4명의 사람을 키 순서로 정렬하고자 할 때, 선택 정렬의 방식을 따른다면, 우선 150cm을 맨 앞에 세우고 나머지 3명의 키를 비교합니다. 150cm[정렬 완료] || 170cm, 180cm, 160cm 3명 중에서는 160cm가 가장 작으므로 앞쪽으로 땡겨오고, 먼저 앞으로 간 150cm 뒤에 위치하도록 합니다. 150cm, 160cm[정렬 완료] || 170cm, 180cm 이를 반복하면 최종적으로 키 순서대로 사람들이 정렬될 것입니다. Code 이를 코드로 구현하면 다음과 같습니다. def selection_sort(people): lengt..