재귀(Recursion)
- 재귀: 자신을 정의할 때, 자기 자신을 참조하는 것
- 재귀 함수: 함수 내부에서 자기 자신을 호출하는 함수
재귀 함수를 사용하는 이유
변수의 사용을 줄여, 프로그램을 더 간결하고 이해하기 쉽게 만들 수 있음
재귀 함수는 복잡한 문제를 간단한 기본 단계 (base case)로 나누고, 이러한 기본 단계에서 해결하는 방식을 통해 문제를 해결할 수 있게 함
재귀 함수를 작성할 때 주의할 점
- 무한 루프에 빠지지 않도록 종료 조건을 잘 설정
(종료 조건을 기저 사례 (base case) 라고도 함) - 함수의 파라미터 및 인자 설정에 유의
* 재귀는 이후 DFS / BFS 등에 자주 사용되는 개념이기 때문에 꼭 이해하고 넘어가야함
정렬
정렬이 필요한 이유?
오름차순 및 내림차순으로 정렬되어 있다면 특정 원소를 좀 더 효율적으로 찾을 수 있음
특정 정렬이 빠르다고 항상 좋은 것은 아님
데이터의 특성, 크기에 따라 적절한 정렬 방법을 사용해야 함
삽입 정렬 (Insertion Sort)
- 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성
- 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점 존재
버블 정렬 (Bubble Sort)
- 배열의 인접한 두 수를 선택하여, 정렬되지 않았다면 두 수를 바꿈 (swap)
- 이를 배열의 처음부터 끝까지 반복하고, 배열에 아무 변화가 없을 때까지 함
- 구현이 간단하지만, 느림
합병(병합) 정렬 (Merge Sort)
- 재귀의 개념이 사용됨
- 정렬되지 않은 리스트를 하나의 원소만 포함할 때까지 n개의 부분 리스트로 분할
(원소의 개수가 하나인 리스트는 이미 정렬된 것으로 봄) - 부분 리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분 리스트를 생성
- 마지막 남은 부분 리스트가 정렬된 리스트
퀵 정렬 (Quick Sort)
- Pivot (기준점) 개념이 사용됨 + 재귀 사용
- 배열의 요소들 중에서 피벗(Pivot)을 정하여, 피벗의 앞에는 피벗보다 작은 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값이 오도록 배열을 둘로 나눔
- Pivot은 중앙값/처음값/마지막값 등 다양하게 설정할 수 있음
- pivot(기준), left, right -> left, right 자리 바꿈
- 분할된 두 개의 배열의 크기가 0이나 1이 될 때까지, 분할된 두 배열에 대해 재귀적으로 이 과정을 반복
- 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소가 최종적인 위치에 있게 되므로, 종료됨이 보장
힙 정렬 (Heap Sort)
- 최대 힙 구성
최대 힙이란 부모 노드가 자신 노드보다 큰 트리를 의미 - 현재 힙에서 가장 큰 값(루트의 값)을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄이고 최대 힙 구성
- 힙의 사이즈가 1이 될 때까지 위 과정을 반복
언어들의 라이브러리 내장 sort 함수 구현
- C++은 sort 함수 내부에 일반적으로 인트로 정렬로 구현되어 있음
(인트로 정렬(Intro Sort): 퀵 정렬 + 힙 정렬 + 삽입 정렬)
- Python은 팀 정렬 (Tim Sort)
(팀 정렬: 합병 정렬 + 삽입 정렬)
- Java는 Java7 이전에는 병합 정렬, 이후에는 팀 정렬
코딩테스트에서는 특별한 경우가 아니면 내장 sort함수를 많이 사용하기 때문에 모든 정렬 방법에 대해서 자세히 알 필요는 없음
다만, 각 정렬의 동작 방식에 대해서 간단하게 설명할 수 있을 정도로는 숙지하는 것을 권장함
