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