Dynamic Programming9 [쇼미더코드 3회] 백준 27212 - 미팅 (자바 java) 문제 : boj27212 필요 알고리즘 개념 DP (동적 계획법) 약간 생각이 필요한 DP 문제였다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 쇼미더코드 3회 당시 1, 2번 15분만에 풀어놓고 이것만 1시간정도 걸렸다. 생긴게 이분 그래프 형태라 그래프쪽으로 자꾸 생각해보다가 오래걸렸다. 확실히 난 DP에 약한 것 같다 ㅠ. DP로 풀면 되겠는데?! 라고 깨닿기까지 너무 오래걸렸다 ㅋㅋ 입력이 아래와 같다고 해보자. .. 2023. 1. 15. [자바] 백준 9465 - 스티커 (java) 문제 : boj9465 필요 알고리즘 개념 동적 계획법 (Dynamic Programming, DP) DP로 풀 수 있는 문제이다. DP는 알고리즘이라기 보단 문제 푸는 방식? 같은 거라 생각한다. 어쨌든 어떤건진 미리 알고 풀어야 생각해낼 수 있을 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 스티커 위치가 아래와 같다고 해보자. A C E B D F 이 때, 각 스티커의 가치 중 음수인 것은 없으므로 결국 우측.. 2022. 12. 21. [자바] 백준 8394 - 악수 (java) 문제 : boj8394 필요 알고리즘 개념 동적계획법 (다이나믹 프로그래밍, DP, dynamic programming) 동적계획법을 안다면 어렵지 않게 풀 수 있다. 동적계획법을 몇 개 풀어봤었다면 풀이를 몇초만에 떠올릴 수 있는 정도로 응용없이 기본적인 형태의 문제이다. 참고로 방법의 수, 경우의 수를 구하는 문제들은 높은 확률로 동적계획법을 사용해 풀리는 경우가 많다. 나머지 연산 (모듈러, modular) 수가 매우 커지므로, 자바의 BigInteger(큰 수 표현 가능. 대신 느림)를 쓰거나, 나머지 연산을 사용해줘야 한다(안해보긴 했는데 BigInteger 사용하면 메모리초과날 것 같긴하다). '%'를 사용하는 나머지 연산을 알고 있어야 더 쉽게 통과 가능하다. ※ 제 코드에서 왜 main 함.. 2022. 8. 6. [코틀린, 자바] 백준 14651 - 걷다보니 신천역 삼 (Large) (boj kotlin java) 문제 : boj14651 우선 3의 배수를 판정하는 방법부터 알아보자. 이 경우 수 A의 모든 자리의 숫자의 합이 3의 배수라면 A도 3의배수이다(정수론). 그럼 이 문제는 N자리 숫자에 대해, N번의 선택을 거친 결과 모든 자리 수의 합이 3의 배수인 경우의 수를 찾는 문제인 셈이다. 물론 단순하게 brute force로 찾아보려 한다면 O(3^33333)이 필요하므로 불가능하다. DP로 생각해보자. dp[a][b]를 a번째 자리수까지 더했을 때의 합을 3으로 나눈 나머지가 b인 경우의 수로 정해보자. 그럼 a가 5일때까지만 살펴보자. (N=5) 1. 우선 a=1 일 경우 다음과 같이 될 것이다. 또 이렇게 두면 '0으로 시작하는 수는 만들 수 없는 수 이삼' 부분을 별도로 처리하지 않아도 되기 때문에.. 2022. 7. 10. [코틀린, 자바] BOJ 15645 - 내려가기 2 (boj kotlin java) 문제 : boj15645 ps. 코틀린의 경우 대강 인터넷 검색해서 문법을 익혔으므로 아직 늅늅이 상태여서 많이 어색하게 짰다. 이 문제의 경우 dp로 풀면 쉽게 풀린다. 알아야 하는 정보는 바로 직전 3칸의 합계 뿐이다(시작할때는 당연히 셋 다 0이라고 치면 된다.). N개의 줄을 입력받으면서, 매번 해당 칸으로 올 수 있는 값 중 최대와 최소값을 갱신 후에 현재 줄에서 입력받은 값을 더해주면 된다. dp[a][b]가 a라인까지 입력받았을 때 b번째(0,1,2로 3개) 칸까지의 최대합계라고 해보자. 그렇다면 dp[x][0] = max(dp[x-1][0], dp[x-1][1]) + 입력받은 0번째 값 dp[x][1] = max(dp[x-1][0], dp[x-1][1], dp[x-1][2]) + 입력받은 .. 2022. 7. 9. [자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26. [자바] 백준 17271 - 리그 오브 레전설 (Small) (boj java) 문제 : boj17271 다음의 dp식을 사용하면 구할 수 있다. dp[0] = 1로 시작하고, i를 1부터 n까지 증가시키면서 dp[1]부터 dp[n]까지 위의 식을 적용해 계산해주면 된다. dp[i]는 i시간이 있을 때의 경우의 수이다. dp[i-1]은 이전의 경우의 수에 A 기술을 쓰는 경우, dp[i-b]는 이전의 경우의 수에 B 기술을 쓰는 경우를 의미한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final int MOD = 1000000007; private void solu.. 2022. 5. 22. [자바] 백준 17212 - 달나라 토끼를 위한 구매대금 지불 도우미 (boj java) 문제 : boj17212 N을 1,2,5,7원들을 최소한으로 사용한 합으로 나타내야 하는 문제이다. dp로 쉽게 풀 수 있다. 점화식은 다음과 같다. dp[i]는 i원을 표현하기 위해 필요한 1,2,5,7원 동전의 최소 개수이다. dp[0] = 0을 base condition으로 둔다면 위의 점화식을 통해 N이하의 모든 값에 대해 최소 개수를 구할 수 있다. 답은 dp[n]이 될 것이다. 말로 표현하자면 "i원(dp[i])을 표현하기 위한 최소개수는 i-1원의 최소개수, i-2원의 최소개수, i-5원의 최소개수, i-7원의 최소개수 중 가장 작은 회수에다가 현재의 동전 1개를 추가한(+1) 개수이다." 코드 : github import java.io.BufferedReader; import java.io.. 2022. 5. 20. 백준 2602 자바 - 돌다리 건너기 (BOJ 2602 JAVA) 문제 : boj2602 이게 돌다리 2개를 번갈아 건너는 부분을 어떻게 처리할지 감이 잘 안올 수 있어서 그렇지, 그 부분 때고 생각하면 생각보다 어렵지 않다. 1. 그러니 우선 돌다리가 한 줄만 있다고 치고 생각해보자. 이 경우에도 모든 경우를 보기에는 당연히 무리가 있다. 대강 100! (팩토리얼) 정도 나올테니 다 볼순 없다. 브루트포스로 하진 못하겠고, 그럼 돌다리 한 줄만 우선 본다고 했으니 "RRGGSR"에서 "RGS"를 건너면서 지나가는 경우를 생각해보자. 이런건 DP를 사용해 구하면 효율 좋게 구할 수 있다. dp[a][b]를 "RGS"에서 a 인덱스 까지를 표현하는 가지수, b는 "RRGGSR"의 인덱스 라고 정의해보자. 이 경우 다음과 같이 그려볼 수 있다. 최종적으로 가장 우측 아래에.. 2022. 3. 18. 이전 1 다음
