Devjo의 코딩

소트인사이드 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 43447 26601 22398 61.682% 문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 풀이 숫자 크기에 명백한 제한이 있을 때 카운팅 정렬을 생각하게 된다. 각 자리수의 경우 0~9까지 수의 범위는 제한적이다. 10크기의 카운팅 배열을 만들고 숫자에 해당하는 index에 값을 추가해 9부터 0까지 출력한다 Arrays.sort 등을 사용해 코드 길이를 줄일 수 있지만 이번에는 System.in.read..

수 정렬하기 3 시간 제한메모리 제한제출정답맞은 사람정답 비율 5 초 (하단 참고) 8 MB (하단 참고) 129846 29380 21612 23.384% 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이1 이전 단계 문제에서 사용한 Arrays.sort를 이용해도 풀이가 되는 것을 확인할 수 있다 import java.io.*; import java.util.Arrays; public class Main { sta..

안정 정렬 Stable sort, 정렬 전의 순서를 유지하고 정렬된다 삽입(Insertion) 정렬, 버블(Bubble) 정렬, 병합(Merge) 정렬이 있다 삽입 정렬 두번째 자료부터 시작해 자신보다 앞 자료들과 크기를 비교해 알맞은 자리에 끼워넣는다 버블 정렬 서로 인접한 자료들을 계속해서 정렬해준다. 1번 회전이 될 때 가장 큰 수가 맨 오른쪽에 위치한다 병합 정렬 현재 배열을 두 개로 나눈 뒤 각각 정렬을 수행한다. 정렬된 두 배열의 처음 값들을 비교해 작은 값을 먼저 원래 배열에 넣어준다 위의 예시는 원리를 설명하기 위한 병합정렬의 맨 마지막 과정이다. 자세히 보면 크기가 4인 배열들이 이미 정렬되어 있다. 크기가 4인 배열을 정렬하기 위해 크기가 2인 배열로 나누고 다시 크기가 1인 배열로 나..

수 정렬하기 2 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 256 MB 147950 39870 27221 29.965% 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 2750 풀이 수 정렬은 Arrays.sort를 이용하면 곧바로 해결된다 import java.util.Arrays; import java.util.Scanner; public class Main { stati..

주유소 서브태스크 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 512 MB 21992 8272 6547 37.056% 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 ..

잃어버린 괄호 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 35632 16846 13602 47.219% 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫..

그리디 알고리즘 greedy(욕심많은, 욕심쟁이의) 알고리즘 뜻 그대로 선택의 이후를 고려하지 않고 순간 순간마다의 최적의 해를 찾는 방식이다 그리디 알고리즘의 이해 그리디 알고리즘은 동적 계획법을 보완하는 개념이다 브루트 포스, 동적 계획법 그리고 그리디 알고리즘을 비교한다 위 그림을 참고해 서울 → 부산을 가는 최소 경로를 구해보자 브루트 포스, 동적 계획법, 그리고 그리드 알고리즘을 토대로 구해볼 것이다 브루트 포스 서울에서 부산으로 갈 수 있는 모든 해를 구한다(왼쪽부터) 250km + 100km / 80km / 120km 200km + 100km / 80km / 120km 300km + 100km / 80km / 120km 위 9개의 값 중 최소값인 280km를 결과로 반환한다 동적 계획법 1항..

1차원 배열 정렬 java.util 안에 있는 Arrays 클래스를 가져온다 1차원 배열 오름차순 1차원 배열 내림차순 import java.util.Arrays; import java.util.Arrays; import java.util.Collections; Arrays.sort( 배열 ); Arrays.sort( 배열 , Collections.reverseOrder() ); int 배열 사용 가능 Wrapper Class 사용(Integer 등) *내림차순에서는 int가 아닌 Integer을 사용함에 유의한다 import java.util.Arrays; public class Main { public static void main(String[] args){ Integer[] arr = {3,5,2..

보호되어 있는 글입니다.

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작..