본문 바로가기

분류 전체보기352

[백준] 자바 2751 수 정렬하기 2 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 테스트 케이스 접근 당연하게 arrays.sort(arr)를 이용하여 문제를 풀려하였지만, 시간 초과가 떴습니다. 함정이 있는 듯합니다. 구글링 해본 결과 arrays.sort()의 경우 퀵 소트를 사용하여 최악의 경우 O(N^2) 시간이 걸리게 된다고 합니다. 이를 해결하기 위해 Collections.sort()를 이용하면 문제가 해결.. 2021. 2. 15.
[백준] 자바 5585 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져 있고, 타로가 지불할 돈(1 이상 1000 미만의 정수) 1개가 쓰여있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 테스트 케이스 접근 거스름으로 줄 수 있는 돈의 종류가 500,100,50,10,5,1엔이 있으므로 입력받은 값이.. 2021. 2. 14.
[백주] 자바 2217 로프 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수.. 2021. 2. 14.
[알고리즘] 그리디 알고리즘 1.그리디 알고리즘 이란? 목적을 도달하기 위한 선택의 순간에 최고의 선택만 하는게 그리디 알고리즘 입니다. 탐욕법이라고도 합니다. 그림으로 나타내면 다음과 같습니다. A시작 D목표 일때 최단 경로는 A->C->D 입니다. 하지만 그리디 알고리즘은 매 선택의 순간에 최고의 선택을 하기때문에 A->C로 가지않고 A->B로 가게됩니다. 이것이 그리디 알고리즘 입니다. 따라서 항상 최적의해를 찾게되는 알고리즘은 아닙니다. 2021. 2. 12.
[백준] 자바 1932 정수 삼각형 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 테스트 케이스 접근 dp문제이므로 최대한 쪼개서 생각해보려 노력.. 2021. 2. 11.
[백준] 자바 1463 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 접근 아래 과정을 f(x)라고 생각하면 값을 넣었을 때 f(x)를 몇 번써야 1이 되는지 출력하는 문제입니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. dp문제이므로 문제를 잘게 쪼개어 다음 문제를 풀 수 있게끔 .. 2021. 2. 11.
반응형

티스토리툴바