설명 - 피벗을 기준으로 좌측에 피벗 보다 작은 값, 우측에 피벗보다 큰 값을 위치 시킴 - partition(파티션)을 나눠 행위를 반복한다 - partition을 최소 까지 나눴을 때는 이미 정렬이 완료된 상태이다. 파티션을 나누기 전에 pivot 기준으로 임의 정렬을 하고 partition을 나눠 행위 반복하면 더이상 나눌 수 없을 때 이미 정렬이 완료된다. 반대로 merge sort의 경우 제일 작은 크기 까지 파티션을 먼저 나눈 후 병합을 하면서 정렬 수행한다. *과정 (1) pivot 을 정함 (2) 양쪽 끝에 L, R 포인터를 두고 다음 수행 2-1) L < pivot 경우 포인터 증가 L += 1 (pivot 기준 좌변은 항상 작아야 하므로, 큰 값이 나올 때까지 포인터 이동) 2-2) p..

설명 1) 리스트의 길이가 1이 될 때 까지 나눈다(mergeSort()) 2) 왼쪽과 오른쪽 리스트를 대소 비교 하여 정렬된 결과(merge()) 반환 - 재귀 함수 호출하여 작은 문제로 나눈 후 큰 문제의 정답을 구한다 - 재귀 호출로 인해 스택 오버플로우 발생가능(단점) - Java의 경우 인스턴스 메서드 *.subList(int from, int to) 사용하여 쉽게 리스트 분할 가능하다 시간 복잡도 : O(NlogN) - 파티션을 나누는데 logN 만큼 걸리고, 다시 병합할 경우 N 만큼의 소요 공간 복잡도 : O(N) 영상 참고 https://www.youtube.com/watch?v=3j0SWDX4AtU 작은 문제로 나눠서 큰 문제의 해답을 구한다 코드 - 오름차순 정렬 기준으로 작성 - 내..

문제 링크 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 - 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 - 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택) - 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2