문제 설명 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보다 값이 큰 모든 원소들이 오도록 ..
버블 소트란? 버블 소트는 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 위에서와 같이 인접한 원소와 하나하나 비교하며 정렬을 수행한다. 배열의 끝까지 정렬을 완료하면 다시 처음으로 돌아가 같은 작업을 반복하여 수행한다. 다음은 JAVA로 작성된 버블 소트의 코드이다. public class bubbleSort { public static void main(String[] args) { int arr[] = {1,3,6,2,8,2,5,9}; //정렬중 임시 저장 int temp; //출력(정렬전) System.out.print("정렬전..
병합 정렬이란? 재귀를 이용한 정렬방법으로 원래의 배열을 분할한 뒤 정렬하며 병합하는 방식으로 정렬을 수행하는 방법을 말한다. 분할 정복의 개념을 도입한 방법이며, 부분 배열 array [a.... b]를 다음과 같이 정렬한다. 1. 만일 a=b이면 아무것도 하지 않는다. 부분 배열이 원소 한 개로 이루어져 있으며, 이는 이미 정렬되어 있기 때문이다. 2. 가운데 원소의 위치를 k = (a+b)/2 ※이때, a+b가 2로 나누어 떨어지지 않는다면 (a+b)/2보다 크지 않은 정수중 가장 큰 수가 k가 된다. 3. 재귀적으로 부분 배열 array [a.... k]를 정렬한다. 4. 재귀적으로 부분 배열 arrat [k+1..... b]를 정렬한다. 5. 정렬된 부분 배열 array [a... k]와 arr..
