문제 링크 : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 일단 이 문제를 풀기 위해서는 버블정렬을 알아야했다. 그래서 버블정렬에 대해 먼저 정리해 보았다. https://infinitt.tistory.com/228 버블 정렬 (bubble sort) * 버블정렬의 개념 두 인접한 원소를 검사하여 정렬하는 방법을 말한다. 시간 복잡도는 느리지만, 코드는 단순하다. 교환정렬의 일부에 속한다. 원소가 이동하는 모습이 거품..

* 버블정렬의 개념 두 인접한 원소를 검사하여 정렬하는 방법을 말한다. 시간 복잡도는 느리지만, 코드는 단순하다. 교환정렬의 일부에 속한다. 원소가 이동하는 모습이 거품이 수면위로 올라오는 듯한 모습과 같다고해서 붙여진 이름이라고 한다. * 정렬의 과정 버블정렬로 정렬을 할때는, 원소의 갯수만큼의 순회를 하게된다. 1회차때는 가장 큰수가, 2회차때는 두번째로 큰수..... 이런식으로 가장 큰수부터 자기자리를 찾아가게 된다. 따라서, 회차를 거듭할수록 1회씩 정렬의 횟수가 적어지게된다. (자기자리를 찾은 부분은 정렬할 필요가 없으므로) array = [7,4,6,1] 이라는 배열을 버블정렬을 이용하여 작은수가 앞에 오도록 정렬한다면 * 1회차 : 가장 큰수(7)가 정렬된다. 정렬횟수 : 3회 * 2회차 :..