빅 오는 알고리즘을 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해 주는 좋은 도구이지만, 유일한 도구는 아니다. 1. 선택 정렬 선택 정렬의 시퀀스 배열의 각 셀을 왼쪽에서 오른쪽으로 확인하면서 어떤 값이 최솟값인지 판단하고 가장 작은 값을 기록한다. 최솟값과 pass through를 시작했을 때의 값을 교환한다. pass through를 반복한다. 2. 선택 정렬 실제로 해보기 & 3. 선택 정렬 구현 (Kotlin) fun main() { selectionSort(arrayOf(10, 9, 4, 6, 7, 8, 3, 2, 11, 1)).forEach { print("$it ") } } fun selectionSort(arr: Array): Array { for (i in arr.indices)..
1. 버블 정렬 정렬 알고리즘: 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까? 2 1 3 5 위와 같은 배열이 있을 때, 포인터 1은 2를, 포인터 2는 1을 가리킨다. 포인터 1 > 포인터 2 일 때, 두 항목을 교환한다. 포인터들은 한 칸씩 이동하며 두 항목을 비교하고 필요시 두 항목을 교환한다. 이렇게 한 번 배열 전체를 pass through하고 나면, 다시 맨 왼쪽으로 포인터를 옮겨 교환이 일어나지 않을 때까지 반복한다. 2. 버블 정렬의 구현 생략 파이썬 코드 예쁘다 3. 버블 정렬의 효율성 버블 정렬 알고리즘에서 중요한 단계는 비교와 교환이다. 비교: 배열 크기가 N이라고 했을 때, 비교는 N - 1 + N - 2 + N - 3 + … + 1번 실행된다. 교환: ..
알고리즘의 효율성을 결정하는 주 요인은 알고리즘 수행에 필요한 단계 수 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하면…? 빅 오 표기법 1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까? O(N) “빅 오 엔”이라고 발음한다. 보통 “빅”을 생략하고 “오 엔”이라고 부름. 알고리즘에 N단계가 필요하다는 뜻 O(1) 1장에서 배열 읽기에 필요한 단계 수는 “배열의 크기와 상관없이” 딱 한 단계. 이때의 표기를 O(1)이라고 한다. 즉 배열에 원소가 몇 개든 한 단계만 필요할 때. O(1)의 시간 복잡도를 갖는 알고리즘을 가장 빠른 알고리즘 유형으로 분류한다. 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다. 2. 빅 오의 본질 빅 오가 진정으로 의미하는 것:..
