문제 설명크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.https://www.acmicpc.net/problem/1083 제한 사항 풀이문제를 요약하면, 내림차순으로 정렬할 때 S번만 이동시켰을 때의 결과를 구해야 한다. 문제를 읽어보면 버블 소트와 유사하다는 것을 알 수 있다.버블 소트는 숫자 N개를 읽어 위치가 정해지지 않은 가장 큰 수의 위치를 정해가는 것이다.하지만 해당 문제에서는 S번이라는 제약이 있기 때문에 가장 큰 수를 올바른 위치로 이동시키지 못할 경우가 생긴다.그렇다면 이때 다음 큰 ..
자연수 N을 입력받아 자연수 안에서 각 자릿수를 내림차순으로 정렬하는 문제이다. 우선 각 자리수로 수를 나누어 크기 순으로 정렬한 뒤 다시 합치면 된다. 다음은 Java로 작성한 코드이다. import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class SortInside { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //역전된 우선 순위 큐 PriorityQueue solution = new PriorityQueue(Collections.rev..
퀵 소트란? 퀵 소트는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 퀵 소트는 정렬 알고리즘 중 가장 빠르다고 하여 붙여진 이름이다. pivot을 선택하여 비교하며 정렬을 수행하는데 pivot으로 선택한 수가 가장 작거나 가장 크다면 최악의 경우로 정렬 수행 시간이 가장 오래 걸린다. 하지만 가장 오래 걸리더라도 O(n^2)의 시간 복잡도를 가지며 이 최악의 경우만 제외한다면 평균적으로 O(nlogn)의 시간 복잡도를 가진다. 퀵 소트은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 1. 리스트에서 임의의 수를 pivot으로 정한다. 2. pivot앞에는 pivot보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 ..
