문제풀이/백준
-
[백준 11568번] 민균이의 계략 Java 풀이문제풀이/백준 2021. 10. 6. 21:42
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어보았습니다. 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열과 문제는 동일 합니다. 그러나 일전의 문제의 경우 DP[N]을 구하기 위하여 1부터 N-1까지 반복하여 정답을 구하는 방식으로 구현하였습니다. 이 방법은 최종 길이인N을 구하기 위해서는 worst-case인 N * (N-1)번 반복을 수행하므로 시간 복잡도가 O(N2)이 됩니다. 만약 이번 문제 또한 일전의 방식으로 풀이 시 시간초과가 되게 됩니다. 하여 Lower Bound를 이용하여 시간복잡도가 O(nlogn)인..
-
[백준 11053번] 가장 긴 증가하는 부분 수열 Java 풀이문제풀이/백준 2021. 10. 5. 00:19
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어보았습니다. 입력받은 수열의 길이가 1이라면 어떤 수여도 가장 긴 증가하는 부분 수열의 길이는 1이 될 것입니다. 그럼 입력받은 수열의 길이가 2개인 경우를 살펴보도록 하겠습니다. 아래 표와 같이 입력을 받은 경우 DP[0]은 어떤 수가 와도 1이므로 1이 되고 DP[1]의 경우 현재 수(20)의 이전 수인 10의 DP값에 1을 더한 값인 2가 됩니다. 10 20 이번에는 입력이 아래 표와 같은 경우 DP[0]은 1이 되고 DP[1]은 현재 수(10) 이전의 수인 20의 경우 현재 수..
-
[백준 11048번] 이동하기 Java 풀이문제풀이/백준 2021. 10. 1. 00:49
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어 보았습니다. 준규는 오른쪽과 아래쪽 그리고 오른쪽 아래 대각선으로만 움직일 수 있습니다. 준규가 (2, 3)으로 이동한다면 이전 위치는 (2, 2), (1, 2), (1, 3) 3가지 위치에서 (2, 3)으로 이동이 가능합니다. DP[2][1]의 값은 (1, 2)에서 가지고 있을 수 있는 사탕의 최대 개수이며 DP[2][2]의 값은 (2, 2)에서 가지고 있을 수 있는 사탕의 최대 개수이며 DP[3][1]의 값은 (1, 3)에서 가지고 있을 수 있는 사탕의 최대 개수가 됩니다. 그렇..
-
[백준 11722번] 가장 긴 감소하는 부분 수열 Java 풀이문제풀이/백준 2021. 9. 28. 12:13
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 문제를 풀었습니다. 이번 문제의 목적인 가장 긴 감소하는 부분 수열을 구하는 것이므로 부분 수열의 최대 길이를 DP에 메모라이즈 하여 문제를 풀 수 있습니다. 만약 입력으로 N = 1, 입력 수로 10이 주어 지면 DP[0] = 1이고 정답 또한 1이 될 것입니다. 이번에는 N = 2, 입력 수로 10, 30이면 어떻게 될까요? 먼저 N이 어떤 수가 입력으로 주어지더라도 DP[0]은 무조건 1일 될 것입니다. 최초의 수는 시작하는 수이므로 길이가 1이 되기 때문입니다. 그럼 DP[1]은 ..
-
[백준 16496번] 큰 수 만들기 Java 풀이문제풀이/백준 2021. 9. 24. 01:31
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 입력받은 숫자들의 우선순위를 찾아 정렬하여 풀어보았습니다. 먼저 입력받은 숫자 3, 30, 34는 어느 것이 우선순위가 높은 숫자가 되는지 알아야 합니다. 3과 30 둘 중 어느 숫자가 더 높은 우선순위를 가질까요? 3이 먼저 오면 330 3이 늦게 오면 303이 되어 3이 30보다 우선순위가 높습니다. 그럼 3과 34는 어떤 수가 우선순위가 높을까요? 이번에는 34가 우선순위가 높습니다. 343이 334보다 큰 수이기 때문입니다. 이번에는 3과 같은 우선순위에 있는 수들은 무엇일까요? 333, 3333..
-
[백준 9465번] 스티커 Java 풀이문제풀이/백준 2021. 9. 21. 00:02
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀어보았습니다. N이 1인 경우를 생각해 보도록 하겠습니다. N이 1인 경우 선택한 스티커의 값이 최댓값이 됩니다. 위쪽을 선택한 경우 아래쪽 스티커를 사용하지 못하고 아래쪽 스티커를 사용한 경우 위쪽 스티커를 사용하지 못하기 때문입니다. 아래 표 처럼 스티커 점수가 있다면 DP[0][1] = 50이 되며 DP[1][1] = 30이 됩니다. 추후 계산을 위해 Index는 1부터 시작하도록 하겠습니다. 50 30 그럼 N이 2인 경우를 생각해 보겠습니다. N이 2인 경우는 첫번째 선택의 대..
-
[백준 1890번] 점프 Java 풀이문제풀이/백준 2021. 9. 19. 23:59
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 문제에서 주어진 내용을 보면 게임의 점프 진행은 언제나 왼쪽에서 오른쪽 위쪽에서 아래쪽으로 진행됩니다. 하여 DP의 진행 또한 왼쪽에서 오른쪽으로 위쪽에서 아래쪽으로 진행을 하면 문제를 풀 수 있습니다. DP의 각각의 위치에는 말이 시작점에서 점프되어 온 경우의 수를 가지고 있습니다. 예제를 통해 문제를 풀면 맨 처음 움직일 수 있는 (1, 1)(가장 왼쪽의 가장 위쪽)은 어떤 게임이 되어도 1이 되어야 합니다. 해당 부분은 시작점이므로 무조건 해당 부분에서 이동이 일어나기 때문입니다. 아래 표처럼 DP가 준비됩니다..
-
[백준 2670번] 연속부분최대곱 Java 풀이문제풀이/백준 2021. 9. 16. 23:47
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제는 DP를 이용하여 풀이가 가능합니다. 문제 풀이에 앞서 입력으로 주어지는 N이 10,000 이하의 자연수 이므로 N은 10,000이 최대 값으로 입력될 수 있습니다. 또한 실수의 경우 소수점 첫째 자리까지 주어지므로 소수점 이하 10,000자리 까지 나올 수 있다는 것을 의미합니다. java의 double형 타입은 소수 부분 15자리까지 오차 없이 표현할 수 있습니다. 하여 이번 문제에서는 기본형인 float이나 double이 아닌 BigDecimal이라는 Class를 이용하여 계산을 하고자 합니다. Bi..