본문 바로가기

동적계획법6

[자바] 백준 2418 - 단어 격자 (java) 목차 문제 : boj2418 필요 알고리즘 DP (동적 계획법) BFS 같은걸론 시간초과가 나게된다. 동적 계획법으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '각 칸은 중복되게 사용해도 된다.' 부분이 문제인데, 이 부분때문에 BFS나 DFS로 진행 시 중복체크를 못하므로 시간복잡도가 저 멀리 가버리게 된다. 게다가 경우의 수의 경우 최대 10^18 이라고 했으므로, 따로 시간복잡도를 계산해보지.. 2023. 12. 8.
[자바] 백준 16395 - 파스칼의 삼각형 (java) 문제 : boj16395 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 파스칼의 삼각형을 한쪽으로 전부 밀어보면 규칙이 보인다. DP로 미리 값을 구한 후, n과 k에 따라 해당하는 값을 출력해주면 된다. DP 문제긴한데 DP라기보다는 그냥 규칙찾는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 파스칼 삼각형을 코드로 어떻게 표현할지 생각해보자. 파스칼 삼각형을 좌측으로 쭉 밀어서 2.. 2022. 10. 25.
[자바] 백준 15489 - 파스칼 삼각형 (java) 문제 : boj15489 필요 알고리즘 개념 동적계획법(DP) 사실 딱히 DP 개념은 필요없다. 풀고보니 파스칼 삼각형 데이터 마련하는게 DP 느낌인거지, 그냥 구현문제다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최근에 어떤분의 질문으로 3차원 파스칼 삼각형에 대한 설명이 이해안된다고 해서 그려서 설명해줬었는데, 마침 백준에 파스칼 삼각형이 보이길래(이 문제는 2차원이긴 하다) 한번 풀어봤다. 아래 이미지는 설명해준다.. 2022. 9. 7.
[자바] 백준 25418 - 정수 a를 k로 만들기 (java) 문제 : boj25418 필요 알고리즘 개념 동적계획법(DP), 너비 우선 탐색(BFS), 탐욕법(greedy) DP, BFS, 그리디 정도가 풀이로 생각나는 문제이다. 셋 다 알아야 하는건 아니고, 셋 중 하나만 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - DP 풀이 dp[x]를 x를 만들기 위한 최소 횟수로 정의하자. 그리고 dp[x]를 모두 무한대로(이 문제의 경우 나올 수 있는 최대수치가 .. 2022. 9. 4.
[자바] 프로그래머스 - 도둑질 (코딩테스트 연습 Lv4) 문제 : Programmers-도둑질 레벨 4라 보기엔 프로그래머스의 다른 레벨4 문제에 비해 너무 쉽다. DP가 개인적으로 내 최대 약점이라 생각하는데도 금방 점화식이 생각날 정도니 2~3정도가 적당할 것 같다. 레벨4 스킬 체크 딸 때 이거 나왔으면 더 꿀이었을 것 같다. 일단 점화식은 간단하다. dp[i]를 i번 집을 털 때 얻을 수 있는 최대 돈이라 하면 아래와 같이 세울 수 있다. 즉, 현재 i번 집을 털 때 얻을 수 있는 최대 돈은, 이전집을 털고 현재집을 털지 않는것과 이전으로 2번째 집을 털고 이번 집도 터는 것 중 max값을 선택하면 된다. 이렇게 하면 '100 1 1 100' 처럼 중간에 두 집을 건너띄고 털어야 하는 것 까지 한번에 해결된다(세 집을 건너띄는 경우는 없다. 그 경우라면.. 2022. 4. 21.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA) https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀.. 2021. 10. 7.