알고리즘/정렬

문제 설명R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다.하지만 나보다 의자에 가까이 있는 사람이 보이면, 그 사람이 먼저 앉는다는 것을 알기 때문에 양보할 수밖에 없다.만약, 나보다 의자에 가까이 있는 사람은 없지만, 같은 거리에 있는 사람이 있으면 서로 자리를 차지하려고 할 것이므로, 그 자리는 전쟁터가 될 것이다. (심지어 모든 사람들은 싸움에 자신있기 때문에, 이러한 전쟁터를 거부하지 않는다(!) )여러분들은 이 전차의 정보가 주어질 때, 전쟁터가 될 자리의 수를 세어주면 된다.A행 B열에서 C행 D열과의 떨어진 거리 Dist는 다음과 같은 유클리드 거리로 계산된다.Dist² = (A-..

문제 설명선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.배열의 요소 하나를 선택합니다.배열에서 해당 요소를 삭제합니다.해당 요소를 배열의 맨 뒤에 삽입합니다.선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.https://www.acmicpc.net/problem/13884      제한 사항      풀이문제를 요약하면, 배열이 주어졌을 때 하나의 숫자를 택해 제일 뒤로 보..

문제 설명상근이는 친구들과 함께 라인제로 스키장에 왔다. 오전, 오후에는 열심히 스키를 타고, 저녁 때는 근처 바로 가서 술을 마시며 친구들과 놀려고 한다.라인제로 스키장은 모든 시설이 세계 최고를 자랑하지만, 한 가지 단점이 있다. 바로, 스키 리프트이다. 리프트는 너무 작아서 5초에 한 명씩 태울 수 있다.보통 친구와 동시에 스키장의 정상에서 내려온다고 해도, 리프트가 있는 곳에는 동시에 도착하지 않는다. 따라서, 리프트를 타기 전에 친구가 내려오기를 기다려야 하고, 리프트에서 내린 이후에도 친구가 내리기를 기다려야 한다.상근이는 친구가 아직 리프트에 도착하지 않았다면, 줄을 뒤에 있는 사람에게 양보하려고 한다. 상근이의 입장에서 이 상황을 살펴 보면, 상근이가 아낄 수 있는 시간은 없고, 기다리는 ..

문제 설명아래의 그림과 같이 배열된 장애물들 사이로, 구슬을 굴린다.장애물들은 n개의 행에 걸쳐 배치되어 있으며, 구슬은 맨 위의 행부터 맨 아래의 행을 향해 구른다. 각 행의 장애물들을 지나면서, 구슬은 왼쪽 또는 오른쪽으로 굴러갈 수 있다. 각 행의 번호는 0부터 n-1까지로 주어지며, 그 행의 장애물 사이의 공간은 왼쪽부터 차례로 0으로 주어진다.(0, 0)의 위치에서부터 아래로 구슬을 굴려갈 때, n-1번 행까지 구슬을 굴리는 경우의 수를 구하는 프로그램을 작성하시오. 단, 구슬은 주어진 m개의 공간을 모두 지나야 한다.https://www.acmicpc.net/problem/23317      제한 사항      풀이문제를 요약하면, 주어진 좌표에 해당하는 빈칸을 모두 통과하여 바닥까지 떨어지는..

문제 설명 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다. 전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 ..

문제 설명 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 정렬..

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. https://school.programmers.co.kr/learn/courses/30/lessons/42746# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 ..

우선적으로 y를 기준으로 정렬하고 같다면 x를 기준으로 정렬하는 문제이다. 좌표를 저장할 때, 이차원 배열에 저장할까, x배열, y배열을 이용하여 index로 관리할까 고민해 봤지만, Pair라는 class를 정의해 문제를 풀면 간단할 거라고 생각이 들었다. Pair라는 클래스를 정의하는데 Comparable interface를 구현하게 만들어 우선순위 큐를 이용하여 출력한다면, 한번에 문제를 풀 수 있다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import java.util.Scanner; public class Coordinate { public static void main(String[] args) { //Pair class 정의 class P..

자연수 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보다 값이 큰 모든 원소들이 오도록 ..