![]()
문제https://www.acmicpc.net/problem/1517 1517번: 버블 소트첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.www.acmicpc.net 접근법원래 세그먼트 트리 연습을 하려고 세그먼트 트리 문제를 고른거였는데 세그먼트 트리로 푸는 것보다 분할 정복으로 푸는게 훨씬 쉽다.. 세그먼트 트리는 다른 문제로 연습을 하는 것이 좋은 것 같다. 따라서 이번 글에서는 합병 정렬(분할 정복의 대표적인 예)을 사용해 푸는 것을 설명해보겠다. 과정{9, 1, 7, 4} 데이터 셋이 있을 때, 합병 정렬 과정은 아래와 같다.분..
분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법 대표적인 예: Quick Sort, Merge Sort 재귀함수를 사용해 구현 분할 정복의 단점 재귀함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게된다. Merge Sort 정렬해야 할 리스트가 주어지면 해당 리스트를 최대한 작게 쪼갠 후, 인접한 원소들끼리 비교하며 정렬해 합치는 방법이다. 위 gif는 merge sort 과정에서 업데이트 되는 정렬 리스트를 보여주는 것이기 때문에 정렬 과정을 이해하기엔 어려우니 아래 그림을 통해 이해해보자. 이해가 쉽도록 리스트 원소의 개수를 8개로 하였다. 더이상 쪼갤 수 없을 때까지 쪼갠 후..
