알고리즘

삽입 정렬

삽입 정렬은 구현이 간단하지만 성능이 아쉬운 정렬 알고리즘입니다.

배열을 두 영역으로 나누어, 정렬되지 않은 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다.

이때, 정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 마지막 원소부터 역순으로 비교하여 자리를 찾습니다.

시간 복잡도는 최악의 경우 O(n²)입니다.

병합 정렬

병합 정렬은 비교적 복잡한 정렬 알고리즘으로, 분할 정복 기법을 사용합니다.

배열을 부분집합으로 나눈 후, 각 부분을 재귀적으로 정렬하고 합병하여 전체 배열을 정렬합니다.

병합 과정에서 n개의 데이터를 n번 비교하므로 시간 복잡도는 O(n log n)입니다.

성능 면에서 매우 뛰어나지만, 구현이 어려울 수 있다는 단점이 있습니다.

퀵 정렬

퀵 정렬도 병합 정렬처럼 분할 정복 알고리즘에 속하며, 재귀적으로 배열을 정렬합니다.

배열에서 하나의 숫자를 '피벗'으로 선택한 뒤, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 다시 같은 방식을 적용해 정렬합니다.

평균적인 성능은 O(n log n)이지만, 피벗 선택이 좋지 않을 경우 최악의 시간 복잡도는 O(n²)입니다.

그러나 퀵 정렬은 실제로는 병합 정렬보다 더 적은 메모리와 비교 횟수를 사용하여 더 효율적인 경우가 많습니다.

동적 프로그래밍 - 메모제이션

재귀 함수는 중복된 계산을 여러 번 수행하여 성능에 악영향을 미칠 수 있습니다.

이를 해결하기 위해 메모제이션을 사용하여, 이미 계산된 값을 저장하고 필요할 때 이를 다시 사용하여 성능을 개선할 수 있습니다.

메모제이션은 주로 해시 테이블을 사용하여 빠르게 결과를 조회하고 저장하는 방식으로 동작합니다.

다만, 메모리 사용량이 늘어난다는 단점이 있습니다.

동적 프로그래밍 - 타뷸레이션

타뷸레이션은 상향식 접근 방식으로, 필요한 값들을 미리 테이블에 계산하여 저장해두고 사용합니다.

메모리 사용량이 적으면서도 재귀를 사용하지 않기 때문에 메모제이션보다 더 빠를 수 있습니다.

재귀가 직관적인 경우에는 메모제이션을 사용하는 것이 좋지만, 그렇지 않은 경우에는 타뷸레이션을 통해 더 효율적으로 문제를 해결할 수 있습니다.