알고리즘 요약

시간이 지나면 알고리즘도 잊게 됩니다.
빠르게 복습할 수 있도록 알고리즘 요약과 프로그래밍 구현 예를 제공합니다.
아래 알고리즘 목록에서 원하는 항목을 선택하면 자세한 내용을 보실 수 있습니다.
알고리즘간략설명시간복잡도
정렬
버블정렬
(bubble sort)
앞쪽 부터 인접한 두 값을 비교하면서 정렬 하는 것을 반복해서 정렬. O(n²)
선택정렬
(selection sort)
가장 작은 항목을 찾아서 맨앞부터 차례로 배치를 반복한다. O(n²)
삽입정렬
(insertion sort)
배열의 앞쪽 부터 차례로 정렬되지 않은 값들을 앞쪽 정렬된 값과 비교해서 정렬한다. O(n²)
카운트정렬
(count sort)
숫자의 발생횟수를 계산하는 누적 카운트 사용. 누적 카운트를 갱신해 순서대로 숫자를 직접배치 O(n+k)
병합정렬
(merge sort)
리스트를 반으로 나누고, 각 리스트가 크기가 1이 될 때까지 반으로 나누면서 정렬 후 병합
안정적이고 대규모 데이터에서도 속도 빠름.
O(n log n)
퀵정렬
(quick sort)
피벗(리스트에서 기준이 되는 요소를 고르는 것)값의 선택이 성능에 큰 영향.
피벗값을 중심으로 작은값 리스트와, 큰값 리스트로 나눈다.
O(n log n)
탐색
순차탐색
(sequential search)
첫째 항목부터 차례로 비교한다.
배열이 정렬되어 있지 않을 경우 사용.
O(n/2)
이진탐색
(binary search)
정렬된 배열내에서 지정된 값의 위치를 찾는 과정을 반복한다.
중간요소 값보다 작으면 좌측에서 다시 찾고, 크면 우측에서 다시 찾고.
배열이 정렬되어 있는 경우 효과적
O(log n)
© 코드솔 - CodeSol. All Rights Reserved.