Programming/Algorithm
-
[Java] 백준 1003 피보나치 함수Programming/Algorithm 2021. 3. 24. 21:30
문제 0이상 40이하의 정수가 주어질 때, 해당 숫자를 가지고 피보나치 함수를 호출한다. 이 때 n이 0과 1에 다다르는 횟수를 출력하는 문제이다. 문제에서 요구하는 바를 재귀로 구현하게 되면 40 level의 트리가 만들어지게 되고 O(40!)이라는 시간 복잡도가 나오게된다. (0.25초 안에 당연히 통과 불가) 따라서 만들어질 수 있는 수들의 규칙을 찾아서 점화식을 만들어야 한다. N = 0 1 0 N = 1 0 1 N = 2 1 1 N = 3 2 1 위의 숫자를 토대로 0의 개수, 1의 개수를 각각 담는 DP 배열을 만들 수 있다. N 0 1 2 3 4 [0의 개수] 1 0 1 1 2 [1의 개수] 0 1 1 2 3 코드 import java.io.BufferedReader; import java...
-
[Java] 백준 1931 회의실 배정Programming/Algorithm 2021. 3. 24. 01:47
문제 회의의 시작시간, 종료시간이 주어질 때 사용할 수 있는 회의의 최대개수를 출력하는 문제. 풀이 - 처음엔 문제를 잘못 이해했다. - 시작시간이 2 종료시간이 2라고 할 때 시작과 동시에 끝나므로 해당 경우도 갯수에 더해줘야 한다. - 또한 (1 2) (2 2) 인 경우나 (2 2) (2 5) 인 경우 2 회의 모두 결과값에 포함될 수 있다. - 첫번째로 푼 풀이는 다이나믹 프로그래밍이었다. - 현재 인덱스에 대해서 이전의 인덱스를 모두 확인하여 최댓값을 구하게끔 했다. - 이 경우 O(n^2)이라는 시간 복잡도가 나와 N이 10만인 경우 100억의 연산이 필요하다는 문제가 있었다. 당연히 시간초과가 났다. - 두번째로 푼 풀이는 그리디였다. - 사실 회의를 최대한으로 하는 횟수는 매우 간단하게 구할..
-
[Java] 백준 12852 1로 만들기 2Programming/Algorithm 2021. 3. 24. 01:37
문제 숫자 N이 주어지고, 가능한 연산은 3가지가 주어진다. 3으로 나누어 떨어진다면 3으로 나누기, 2로 나누어 떨어진다면 2로 나누기, 1을 빼기. 이 때 최소의 연산 횟수로 1을 만든다고 할 때 최소 연산 횟수와 해당 경우에 사용되는 숫자를 출력하는 문제. 풀이 기존의 '1로 만들기' 문제에서 사용되는 숫자를 출력하는 로직만 넣어주면된다고 생각했다. 처음엔 MAP 자료구조를 이용해서 DP의 인덱스 값을 KEY로 해당 인덱스를 만들어주기 위한 숫자들을 VALUE로(ArrayList)로 저장하게끔 했다. 통과는 했다. 하지만 다른 분들의 답안을 보고 int 배열을 둔 뒤 재귀 호출로 출력하는 방식이 있다는 것을 발견했다. 처음에 푼 풀이보다 시간이 10분의 1로 줄어들었다. 코드 import java...
-
[Java] 백준 11726 2 x n 타일링Programming/Algorithm 2021. 3. 19. 11:12
문제 2 x n 크기의 직사각형을 채우는 경우의 수를 출력한다 사용할 수 있는 타일의 크기 - 1 x 2 - 2 x 1 풀이 - dp[i]는 2가지 타일을 사용해서 2 x i 직사각형을 채울 수 있는 방법의 수이다. - 2 x i를 만들 수 있는 경우의 수는 다음의 두 경우를 더한 값이다. - 2 x (i - 1)까지 만든 타일 + [2x1타일] - 2 x (i - 2)까지 만든 타일 + [1x2타일+1x2타일] - 이것을 점화식으로 나타내면, dp[i] = dp[i-1] + dp[i-2] 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class b11726__2 { ..
-
[Java] 백준 11399 ATMProgramming/Algorithm 2021. 3. 19. 11:09
문제 사람의 수와 각 사람이 돈을 인출하는 데 걸리는 시간이 주어진다. 이 때 모든 사람이 돈을 인출하기 위해 대기하는 총 시간의 최솟값을 출력하는 문제이다. 풀이 인출시간이 빠른 사람이 앞에 오도록해서 사람들의 대기시간을 최소로 만든 뒤에 대기시간의 합을 구하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class b11399 { public static void main(String[] args) throws IOException { BufferedR..
-
[Java] 백준 1149 RGB 거리Programming/Algorithm 2021. 3. 16. 00:11
문제 집 N개가 있다. 각각의 집은 빨강, 초록, 파랑으로 칠할 수 있다. 각각의 집에 각각의 색깔을 칠하는 가격은 다르다. 또한 인접한 집의 색깔은 같아선 안된다. 위의 규칙을 모두 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해라 풀이 N번째 집을 칠해야 하는 상황이라고 생각해보자. 1) N번째 집을 빨간색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 초록색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 2) N번째 집을 초록색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 ..
-
[Java] 백준 10610 30Programming/Algorithm 2021. 3. 15. 23:58
문제 숫자 N이 주어진다. 해당 숫자를 이루고 있는 수들을 이용해서 만들 수 있는 가장 큰 30의 배수를 출력하는 문제이다. 풀이 처음에는 받아온 N이라는 숫자를 char[]로 쪼개어서, 만들 수 있는 모든 조합을 만들다가 가장 큰 30의 배수가 나오면 출력하게끔 짰다. 근데 NumberFormat Exception이 발생했다. 다시 문제를 자세히 살펴보니, 주어진 N이라는 수의 자릿수가 최대 10^5라는 조건이 있었다. 최댓값이 10^5(100_000)라는 것으로 착각했던것.. 이 조건을 생각하면 long타입으로도 조합을 만들 수가 없다. 다른 분들의 코드를 참고해서 풀었다. 풀이의 핵심은 다음과 같다. - 30의 배수는 10의 배수이므로 끝자리가 0이다. => N에 0이 포함되어 있지 않다면 30의 ..
-
[Java] 백준 9095 1,2,3 더하기Programming/Algorithm 2021. 3. 13. 00:26
문제 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구해라. 풀이 1) 1을 1,2,3의 합으로 나타내는 방법 [1 단독으로 사용가능] - 1가지 : (1) - 1 단독 2) 2을 1,2,3의 합으로 나타내는 방법 [2 단독으로 사용가능] - 2가지 : (1,1) / (2) - [1]을 만드는 경우에 1을 합한 경우 / 2 단독 3) 3을 1,2,3의 합으로 나타내는 방법 [3 단독으로 사용가능] - 4가지 : (1,2)/ (1,1,1) (2,1) / (3) - [1]을 만드는 경우에 2를 합한 경우 / [2]를 만드는 경우에 1을 합한 경우 / 3 단독 4) 4를 1,2,3의 합으로 나타내는 방법 [단독으로 사용가능한 숫자없음] - 7가지 : (1,3) / (1,1,2) (2,..