퀵 정렬
오늘 살펴볼 알고리즘은 정렬 알고리즘 중 빠르다고 알려진 퀵 정렬 이다. 처음엔 다소 헷갈리는 개념일 수 있지만 pivot이라는 개념만 잘 파악한다면 금방 이해할 수 있는 알고리즘이다. 퀵 정렬은 분할 정복을 통해 구현된다. 분할 정복이란 큰 단위에서 작은 단위로 문제를 쪼개며 해결해 나가는 것을 말한다. 이를 위해 재귀적으로 코드가 작성된다. 정렬을 하는 방식은 이러하다. 하나의 기준(pivot)을 설정하고 해당 기준보다 작은 값을 갖는 것은 왼쪽에, 큰 값을 갖는 것은 오른쪽에 위치시키는 방식으로 swap 해가며 정렬을 진행한다. 해당 과정을 쪼개가면서 적용시키면 최종적으로 정렬이 완료되는 효과를 갖게 된다. 예시를 확인해보자. 1. [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] + ^ 2...
2021. 4. 14.
버블 / 선택 / 삽입 정렬
오늘 살펴볼 알고리즘은 정렬 알고리즘의 가장 대표적인 예시들인 버블 / 선택 / 삽입 정렬 알고리즘이다. 알고리즘 자체는 크게 어렵지 않지만 정보처리기사 시험에서도 가끔 출제되고 비슷하게 동작하여 개념들이 약간 헷갈리기 때문에 잘 기억해두면 좋을 듯하다. 글에서 설명하는 정렬은 모두 오름차순을 기준으로 정렬하는 것을 말한다. 버블정렬 우선 버블 정렬이다. 거품이 터지는 모양이 생각난다하여 이름 지어졌다 한다. 간단하게 말해서 큰 수를 먼저 뒤로 보내는 방식으로 정렬하는 것을 말한다. 이를 위해 앞뒤로 값을 비교하여 자리를 바꿔주는 작업을 수행해야 한다. 실제 과정을 살펴보자. 1. [1, 5, 3, 4, 2] ^ ^ 2. [1, 5, 3, 4, 2] ^ ^ swap 3. [1, 3, 5, 4, 2] ^ ..
2021. 3. 24.