Algorithms, Part 1/2주차

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..

Sorting problem key를 기준으로 오름차순 정렬한 예시입니다. Sample sort client 1, 2 숫자, 문자(알파벳)를 기준으로 정렬한 예시입니다. Sample sort client 3 directory를 기준으로 정렬한 예시입니다. Callbacks 데이터 타입에 대한 정보가 주어져있지 않은 상황에서도 정렬을 수행하기 위해 callback 메커니즘이 사용됩니다. comparetTo( ) 메서드를 통해 두 아이템의 타입을 비교할 수 있습니다. Java에서는 인터페이스라는 특정 메서드를 사용합니다. Callbacks: roadmap 객체 형식을 지닌 배열이 인자로 전달됩니다. Java의 comparable interface 같은 것을 generic이라고 합니다. compareTo( )..