[알고리즘] 쉘 정렬
쉘 정렬은 하나의 배열을 여러 개로 쪼개 각각 정렬하는 과정을 반복한 후, 마지막으로 한 번에 정렬하는 기법이다. 이 때, 특정 간격으로 떨어진 요소들을 모아 정렬하는 것이 특징이다. 다음 그림에서는 4칸씩 떨어진 2개의 요소들을 정렬하는 경우를 보여준다. 즉, (8, 7), (1, 6), (4, 3), (2, 5)를 각각 정렬한다. 그 후 2칸씩 떨어진 요소 4개씩, 즉 (7, 3, 8, 4), (1, 2, 6, 5)를 묶어 각각 정렬한다. 그러면 전체 배열은 최종적으로 (3, 4, 7, 8, 1, 2, 5, 6)이 되며, 최종적으로 이를 단순 삽입 정렬하면 된다. 세 번의 정렬 과정에서, 기준 간격은 4 -> 2 -> 1로 변한다. 그런데 이와 같이 간격들이 서로 배수가 되면, 이미 정렬한 원소들을 ..
[알고리즘] 단순 선택 정렬
단순 선택 정렬은 가장 작은 원소를 골라 인덱스 0에, 두 번째로 작은 원소를 골라 인덱스 1에, ... 배치하는 방법이다. 이 알고리즘은 안정적이지 않으며, 시간 복잡도는 O(N^2)이다. (교재 p239 참고) # 단순 선택 정렬 알고리즘 구현하기 from typing import MutableSequence def selection_sort(a: MutableSequence) -> None: """단순 선택 정렬""" n = len(a) for i in range(n - 1): print(f'i = {i}') min = i # i = 0, 1, 2, 3, 4, 5 for j in range(i + 1, n): # j = [1, 2, 3, 4, 5, 6], ... , [5, 6], [6] if a[j..
[알고리즘] {재귀} 하노이 탑
* 참고 : Do It! 자료구조와 함께 배우는 알고리즘 파이썬 편 p200 ~ p203 하노이 탑에는 3개의 기둥(A, B, C)가 있고, 기둥 A에는 위에서부터 차례대로 '원반 1, 원반 2, ... , 원반 n - 1, 원반 n'이 있다. 이 n개의 원반들을 모두 C기둥으로 옮겨야 하며, 최적의 방식은 다음과 같다. 1) 기둥 A의 원반 1, ... , 원반 n - 1들을 기둥 B로 옮긴다. 2) 기둥 A의 원반 n을 기둥 C로 옮긴다. 3) 기둥 B의 원반 1, ... , 원반 n - 1들을 기둥 C로 옮긴다. 그런데 과정 1 & 3 또한 여러 개의 원반들을 다른 기둥으로 옮기는 행위이기 때문에, 다시 재귀적으로 과정 1, 2, 3을 사용할 수 있다. 단지 시작 기둥, 중간 기둥, 목표 기둥이 달..
