목록알고리즘 (1)

Trey

[분할 정복 알고리즘 1] 병합 정렬(Merge Sort)

백준 Z문제(www.acmicpc.net/problem/1074)를 풀다가 분할 정복 개념을 다시 공부해야겠다고 느껴서 공부도 할 겸, 정리도 한번 할겸 이 글을 써봅니다! 1. 분할 정복(Divide and Conquer) 알고리즘이란? 2. 병합 정렬이란? 3. 병합 정렬 시간 복잡도 1. 분할 정복(Divide and Conquer) 알고리즘이란? 어떤 문제를 재귀적으로 분할, 정복, 그리고 결합하는 3단계의 방법으로 해결하는 기법입니다. 1) 분할 (divide) : 원래 문제를 더 작은 단위로 나눈다. - 예시) 병합 정렬에서 길이가 8인 원소를 길이가 4인 두개의 리스트로 나누는 단계 2) 정복 (conquer) : 문제의 단위가 해결하기에 충분히 작아졌다면, 종료 조건을 가지고 문제를 해결한..
알고리즘 2021. 3. 18. 23:23
이전 Prev 1 Next 다음