정렬 썸네일형 리스트형 백준 1071번 소트 http://icpc.me/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 간단한 그리디 문제입니다. 사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다. 앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다. 1) $i$번째로 출력한 수 + 1 == 최솟값일 때 2) 출력하지 않은 수에서.. 더보기 백준 1422번 숫자의 신 http://icpc.me/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 풀이 뒤에서 설명할 비교 연산을 편하게 하기 위해 n개의 수를 문자열 자료형으로 받습니다. k개의 수 중 가장 길이가 길고 큰 수를 최대한 많이 반복하는 것이 이득입니다. 따라서 길이순(길이가 같다면 크기순)으로 정렬하여 n - k번 반복할 수를 먼저 선택하고, 정답을 나타낼 벡터에 선택한 수를 n - k번 넣고 k개의 수를 모두 하나씩 넣습니다. 이후 선택한 n개의 수로 가장 큰 수를 만들 수 있도.. 더보기 Codeforces Round #672 (Div. 2) A~C1번 풀이 얼마 전 Codeforces Round #672 (Div. 2)에 참가했습니다. 처음으로 문제를 3개나 풀어서 행복했습니다. 그래서 대회 중 풀었던 A번, B번, C1번의 풀이를 써 보려 합니다. A번 - Cubes Sorting 문제 Problem - A - Codeforces codeforces.com 문제 설명 $N$개의 정육면체가 한 줄로 놓여 있을 때, 부피가 큰 순으로 정렬한다고 합니다. 단, 두 인접한 정육면체를 교환하는 작업만 할 수 있습니다. 각 정육면체의 부피가 주어질 때, 정렬을 위해 필요한 최소 교환 횟수가 $\frac{N\times (N-1)}{2}$회 미만이라면 YES, 아니면 NO를 출력하는 문제입니다. 풀이 두 인접한 원소만 교환하여 정렬하는 알고리즘으로는 버블 정렬이 있습니.. 더보기 이전 1 다음
