15171 [백준 1517번] 버블 소트 난이도: 플래티넘 V 문제 링크: 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 분할-정복 (divide & conquer) 문제입니다. n은 최대 50만이므로, 모든 원소에 대해 모든 다른 원소와 비교해 보는 식으로 하면 시간 초과가 납니다 (O(N^2)). 재귀 방식으로 배열을 구간별로 나누어 접근하도록 합니다. 나눈 구간에 대해 정렬하기 전 swap 횟수를 세고, 정렬되는 값을 별도의 배열에 기록한 후 (arr2).. 2021. 9. 17. 이전 1 다음
