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 분석 N(1 ≤ N ≤ 500,000)이므로 nlogn 병합정렬로 풀이 시간복잡도, 시간제한, 빅오(Big-O) 표기법 1초 제한 n으로 구성된 O( )를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다고 한다. 예를 들어 N의 최대값이 10만이라고 문제에서 주어진다면 1. O(N) 의 시간복잡도일 경우에 값이 10만 karla.tistory.com 풀이 """ 1517 N개의 수로 이루어진 수열 A[1], A[2], …, A[..

1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 분석 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제 버블정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다 == 이미 모든 데이터가 정렬됐다 N은 500,000보다 작거나 같은 자연수 : n^2불가 안쪽 루프는 1에서 n-j까지 swap 수행, 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이므로 데이터의 정렬 전 인덱스와 정렬 수 인덱스를 비교..