Algorithms, Part 1

Two classic sorting algorithms 지금까지 배웠던 정렬들과 달리, 앞으로 배울 두 정렬인 '병합 정렬'과 '퀵 정렬'은 엄청나게 효율적이고 지금까지도 널리 쓰이는 공신력 있는 알고리즘입니다. Mergesort 병합 정렬의 기본 아이디어는, 배열을 반으로 쪼개고 그 결과를 합치는 작업을 재귀적으로 반복하는 것입니다. Abstract in-place merge demo 캡쳐본이라 영상이 아니지만, 방법은 이렇습니다. 우선 맨 처음의 배열을 복사한 aux 배열을 생성합니다. 그리고 이를 반으로 쪼개어 왼쪽의 첫 번째, 오른쪽의 첫 번째 원소에 인덱스 i, j 를 부여합니다. 그리고 오리지날 배열의 첫 번째 인덱스는 k가 됩니다. i, j 를 비교하여 더 작은 것을 k 자리에 넣고 k는 1..

Convex hull 평면 내의 모든 점을 포함하는 최소한의 다각형을 구하는 문제입니다 여기에도 정렬 알고리즘이 사용됩니다. 시계 반대방향으로 도는 과정을 반복합니다. Convext hull: mechanical algorithm 비유이긴한데.. 잘 와닿지는 않네요.. Convex hull applicatoin: motion planning 로봇의 이동 알고리즘을 설계할 때 장애물을 피해갈 수 있는 최적의 경로를 선정하는데 활용될 수 있습니다. Convex hull application: farthest pair Convex hull: geometric properties Grahan scan: implementation challenges 시작은 y 좌표값이 가장 작은 것을 p로 정하는 것입니다. 이로..

How to shuffle an array Shuffle sort 랜덤하게 생성한 실수를 부여하고 이를 정렬하는 방식으로 shuffle을 할 수 있습니다. Knuth shuffle 하지만 선형 시간을 소요하면서 빠르게 shuffle할 수 있는 방법이 있습니다. 배열을 순서대로 탐색하면서, i 번째 이전의 정수값들을 랜덤하게 하나 골라서 i 번째 원소와 교환하는 것입니다. import random n = len(a) for i in range(n): r = random.randint(0,i-1) a[i],a[r] = a[r],a[i] 파이썬 코드로 구현하면 위와 같습니다. War story (online poker) 간단해 보이는 shuffle 함수에도 네 개나 되는 버그가 존재한다고 하네요. 52개의 카..

Shellsort overview 정렬을 공부하면서 여러 종류들을 접해봤는데 이건 또 신선하네요.. i 번째 이전의 모든 원소를 살피는 삽입 정렬과 달리 일정 간격(h)만큼과 비교하는 정렬입니다. 그래서 h 간격에 따라 부분 정렬되어 있습니다. 물론 간격이 1인 경우는 모든 원소가 오름차순으로 정렬되어 있다는 것을 의미하게 됩니다. h-soring 당연한 얘기지만 간격이 크면 부분 정렬된 배열의 크기 자체는 작습니다. 반대로 간격이 작으면 작을수록 배열 전체가 정렬된 상태에 가까워집니다. Shellsort example: increments 7, 3, 1 Shellsort: intuition 그렇다면 이 논리가 어떻게 적용 가능한 것일까요? 바로 작은 간격으로 h 정렬을 수행했을 때도 큰 간격의 h 정렬..

Insertion sort demo 모든 값을 왼쪽에서부터 오른쪽으로 살펴보던 선택정렬과 달리, 삽입 정렬은 i의 값은 왼쪽에서 오른쪽으로 이동하지만, j의 값은 오른쪽에서 왼쪽으로 이동합니다. j는 0부터 i-1까지의 값이 되는데, 리스트에서 i 번째 값보다 큰 값이 있다면 교환하는 작업을 반복적으로 수행합니다. Insertion sort inner loop n = len(a) for i in range(n): for j in range(i-1,0,-1): if a[j] < a[j-1]: a[j],a[j-1] = a[j-1],a[j] else: break 삽입 정렬을 파이썬으로 구현한 것은 위와 같습니다. 중간에 더 작은 값을 만나게 되어 정렬이 보장되는 경우 break를 통해 반복문을 탈출합니다. I..

Selection sort demo entry 중에서 가장 작은 것을 찾아 맨 앞의 원소와 swap하는 작업을 반복합니다. 아주 간단한 정렬 중 하나인 '선택 정렬'입니다. 결과적으로 왼쪽의 원소가 오른쪽보다 반드시 작은, 오름차순 정렬이 수행됩니다. Selection sort inner loop n = len(a) for i in range(n): minimum = i for j in range(i+1, n): if a[j] < a[minimum]: minimum = j a[i],a[minimum] = a[minimum],a[i] 파이썬으로 선택 정렬을 구현하면 위와 같습니다. 이중 for문 내에서 가장 작은 값의 인덱스를 minimum에 저장하고, 마지막에 이를 맨 앞의 값과 교환하는 방식입니다. S..