안녕하세요.
오늘은 알고리즘 중간고사 준비를 위해 학교 수업에서 배운 합병 정렬을 복습할 겸, 제 방식대로 한번 정리해보고 코드도 작성해보려고 합니다.
1. 합병 정렬(Merge Sort)
- 제목에 써져있는 대로 '분할(Divide)'하고 '정복(Conquer)'하여 정렬을 수행하는 알고리즘.
- 아무리 복잡하고 큰 문제라도 잘게 쪼개서 해결한 뒤, 다시 합치면 원래의 큰 문제를 해결할 수 있다는 아이디어에서 출발했다고 합니다.
2. 기본 동작 방식
1) 1단계: 분할 (Divide)
- 말 그대로 정렬할 리스트를 더 이상 나눌 수 없을 때까지(원소가 1개가 남을 때까지) 계속해서 반으로 쪼갭니다
IF) [8, 4, 3, 1, 6, 5, 7, 2] 있다면,
0번째 : 반으로 쪼갠다. [8,4,3,1] 과 [6,5,7,2]
1번째 : 반으로 쪼갠다. [8,4] 과 [3,1], [6,5] 과 [7,2]
2번째 : 반으로 쪼갠다. [8], [4], [3], [1], [6], [5], [7], [2]
2) 2단계 : 병합 및 정복 (Merge & Conquer)
- 이제 쪼개진 조각들을 다시 합칠 차례입니다. 이때 그냥 합치는 것이 아니라, 두 개의 작은 리스트를 정렬하면서 하나의 큰 리스트로 합칩니다
IF) 0번째 : [4,8], [1, 3], [5,6], [2, 7]
1번째 : [1,3,4,8], [2,5,6,7]
2번째 : [1,2,3,4,5,6,7,8]
=> 병합 단계에서는 두 리스트의 첫 번째 원소끼리 비교해 더 작은 값을 새로운 리스트에 추가하는 방식을 사용합니다. 이 과정에서 정렬이 일어나는 것.
3. 성능(시간복잡도, 공간 복잡도)
1) 시간 복잡도
- 데이터의 상태와 무관하게 최악, 최선의 시간 복잡도 같음(=끝까지 수행하는 신뢰성의 알고리즘이라고도 함)
- 분할단계) 데이터가 8개 일때, 분할 단계에서 3번 을 실행했다. 반으로 나누는 것이라서, 8 = 2^3이 성립하므로, 3(지수)로 끌어내면 3 = log₂(8)이다. 따라서, 일반화하여 데이터의 개수가 n개 라면, log n의 시간복잡도를 가진다.
- 병합단계) 병합단계에서는 모든 요소에 대해서 병합을 시도해야 함으로, n만큼의 연산이 필요하다.
그래서, 합병 정렬의 알고리즘은 O(n log n)이다.
2) 공간 복잡도
- 공간 복잡도는 결국, 메모리에 대한 복잡도 인데, 메모리는 병합 및 정복 과정에서 새로운 배열을 계속 생성한다. (두 리스트를 합칠 때 정렬된 결과를 담아둘 임시 배열이 필요)
- 8개 중에서 처음에는 4개짜리 배열이 필요했고, 그 다음에는 8개 짜리 배열이 필요함. 결국 필요한 메모리는 계속 증가하여, n개짜리 배열이 결국 필요하게 됨으로, O(n)이 된다.
4. 특징
| 장점 | 단점 |
| 1. 안정적인 성능 : 어떤 데이터가 들어와도 O(n log n) 성능을 보장함 |
1. 최선의 경우에도 O(n log n): 이미 정렬된 리스트에 대해서도 분할/병합 과정을 모두 거치므로 O(n log n)보다 더 좋은 성능을 내는 건 불가능 2. 추가 메모리 필요: 정렬을 위한 임시 배열(O(n))이 필요함 |
5. 내가 이해한대로 문제 풀어보기
[백준: 2750] 합병 정렬 연습하기 by min-99 · Pull Request #15 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/2750 카테고리 (예: 구현, 탐색, DP) : 정렬(합병정렬) ✏️ 풀이 방법 결과 (성공/실패) : 성공 풀이 시간 : 20m 풀이 방법 : 참고한 글 링크 : ⭐ 비고
github.com
[코드 설계 의도]
우선 개념에서 설명한대로 1단계 분할과 2단계 병합을 나누어서 코드를 작성하였습니다.
- 1단계 분할 함수 : divide(): number[]을 left와 right 배열로 나누어줍니다.
- 2단계 병합 함수 : merge(): 정렬 + left와 right 배열을 병합하여 리턴합니다.
- 합병 정렬 함수 : mergeSort() : 분할 함수를 실행합니다.
[코드 실행순서 및 실행예시]
IF) input에 [3, 1, 4, 2]로 값이 들어왔다고 가정합니다.
1. console.log(mergeSort([3, 1, 4, 2])) 실행 -> MergeSort 함수 실행
2. divide([3,1,4,2]) 실행 : left: [3,1], right: [4,2] -> return merge(divide([3,1]), divide([4,2]))
3. divide([3,1])부터 실행: left: [3], right: [1] => merge([3], [1])을 실행
4. merge([3], [1]) => return [1, 3]을 리턴(divide([3,1])의 결과)
5. divide([4,2]) 실행 : left: [4], right: [2] => merge([4], [2])을 실행
6. merge([4], [2]) => return [2, 4]를 리턴(divide[4,2]의 결과)
7. merge([1,3], [2,4]) 실행 => [1, 2, 3, 4]를 리턴
결과)
6. 개선해보기
- 문제의 조건중에 '수는 중복되지 않는다.' 라는 조건이 있다.
- 이 부분에 대해서 원래는 merge함수쪽에 같은 경우, 값을 추가하고 leftIndex와 rightIndex를 둘다 증가하도록 해주었다
// 같은 값일때
result.push(right[rightIndex]);
leftIndex++;
rightIndex++;
하지만, 변수가 있었다. 남은 요소들을 추가하는 경우가 고려되지 않았다.
그래서 result에 push하기 전에 아래의 조건을 추가해주었다.
result[result.length - 1] != left[leftIndex]
이번에는, result에 아무값도 추가되지 않은 경우(result.length가 0일때)가 고려되지 않았다..
아래와 같이 조건을 또 추가하여 작성하였다.
result.length === 0 || result[result.length - 1] != left[leftIndex]
결과는 성공이었지만,
Typescript(javascript)에는 Set이라는 중복을 허용하지 않는 자료구조형이 존재한다. 그래서 내가 생각한 Best안은 mergeSort에서 매개변수로 받은 value를 Set 자료구조형으로 생성하고, 다시 배열로 반환하는 구조이다. 이렇게 되면, merge에서 중복을 고려할 필요가 없어서 코드가 훨씬 간단해진다.
하지만, 이슈가 하나 있는데..
백준에서 Set 자료형을 지원하지 않는것 같다.. 내가 가지고 있는 테스트 코드는 통과 하였지만, 백준에서는 '컴파일 에러'가 발생했다..ㅎ
(10/11, 추가 작업)
moonlight-duck님의 댓글로 다시 생각해보게 되었다. Set은 javascript에 기본 내장 되어 있는 함수라서 안될리가 없는데 안된다는 점이 이상했다.
그래서 몇번 시도를 해봤는데 아마 ...(스프레드 연산자) 때문에 컴파일 에러가 발생한 것 같다.
// ❌ 컴파일 에러 발생
const unique = [...new Set(arr)];
// ✅ 정상 작동
const uniqueSet = new Set(arr);
const unique = Array.from(uniqueSet);
아마 생각해보면 백준에서 typescript를 javascsript로 변환할때 ES6 문법보다는 낮은 버전으로 진행을 하는 것 같다.
조금더 찾아봤는데, 더 정확하게는 ES5에는 iterator가 없어서 이를 변환할 때 downlevelIteration: true 옵션이 필요하다고 한다.
'알고리즘' 카테고리의 다른 글
| 분할 정복 주의할점 (0) | 2025.10.16 |
|---|---|
| 최근접점찾기(Closest Pair) - 분할정복 (0) | 2025.10.16 |
| 백준 큐 문제 - 메모리 초과, 시간 초과 해결과정(2164번) (1) | 2025.10.01 |
| 백준 연결리스트 문제 - 시간초과 해결과정(23309번) (0) | 2025.09.29 |
| 백준 연결리스트 문제풀이 접근 (1406번) (0) | 2025.09.28 |