시간복잡도 (4) 썸네일형 리스트형 알고리즘 | 병합 정렬 ✔ 학습목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 병합 정렬 병합 정렬(merge sort)은 원소가 한 개가 될 때까지 계속해서 나누다가 다시 합쳐가며 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 이는 분할 정복(divide and ) 알고리즘의 하나이다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아 원래의 문제를 해결하는 전략이다. 병합 정렬의 단계 병합 정렬은 세 단계로 이루어진다. 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다. 3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열로.. 알고리즘 | 정렬 알고리즘의 실행시간 ✔ 학습목표 1. 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Bio O와 Big Ω로 정의할 수 있다. 2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다. 알고리즘의 실행 시간 이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자. 상한은 다음과 같다. O(1) O(log n) O(n) O(n log n) O(n^2) Linear search o Binary search o Bubble sort o Selection sort o 하한은 다음과 같다. Ω(1) Ω(log n) Ω(n) Ω(n log n) Ω(n^2) L.. 알고리즘 | 선택 정렬 ✔ 학습목표 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다. 선택 정렬 선태 정렬(selection sort)은 버블 정렬과 마찬가지로 정렬을 위한 알고리즘 중 하나이다. 선택 정렬에서는 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환한다. 넣을 위치는 이미 정해져있고, 어떤 수를 넣을지 선택한다는 게 특징이다. 선택 정렬은 아래와 같은 의사 코드로 나타낼 수 있다. For i from 0 to n–1 Find smallest item between i'th item and last item Swap smallest item with i'th item 이해를 위해 간단한 GIF를 보자. 선택 정렬은 버블 정렬과 달리 교환 횟수가 .. 알고리즘 | 알고리즘 표기법 ✔ 학습목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 알고리즘의 효율성 프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다. Big O Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다. 앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 .. 이전 1 다음
