Devjo의 코딩

그리디 알고리즘 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보다 작..

ATM 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 51353 33659 27575 66.398% 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게..

동전 0 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 63302 33632 26262 52.513% 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 풀이 현재 K원에서 만들 수 있는 동전 중 ..

평범한 배낭 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 512 MB 46452 17466 11410 35.908% 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알..

연속합 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 (추가 시간 없음) 128 MB 90176 29770 20571 31.853% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. ..

동적 계획법 Dynamic Programming 또는 DP라고 부른다 1940년대 리차드 벨만이 사용하던 용어이다. 어떤 문제가 주어질 때 본래의 문제를 분석하고 반복되는 연산을 찾아낸다 연산을 기준으로 문제를 작은 문제들로 나눈 다음 각 문제들의 결과값을 기록하며 본래의 문제의 해답을 구하는 방법이다 단계를 구체화하면 다음과 같다 문제 ➡ 점화식 발견 ➡ 작은 문제들로 나누기 ➡ 각 문제의 해답을 기록 ➡ 해답 피보나치 수열 피보나치 수열을 통해 동적계획법을 이해한다 점화식 발견, 연산한 값을 기록하는 것이 dp의 핵심이라 볼 수 있다 피보나치 수열의 0항과 1항은 1이고 n항은 다음과 같이 표현된다 f(n) = f(n-1) + f(n-2) dp를 사용하지 않고 피보나치 특정항을 구해보자 40항을 구하..

1로 만들기 시간 제한메모리 제한제출정답맞은 사람정답 비율 0.15 초 (하단 참고) 128 MB 169868 54512 34481 31.922% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 숫자가 매우 크고(10의 6승) 주어진 시간이 매우 짧았다(0.15초). 먼저 DP를 어떻게 기록할 것인지 알아내야 했..