다이나믹 프로그래밍27 [자바] 백준 14728 - 벼락치기 (java) 목차 문제 : boj14728 필요 알고리즘 DP, 냅색 (배낭 문제) DP로 해결 가능한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 dp[x]를 x시간을 사용해 얻을 수 있는 최대 점수라고 해보자. 그렇다면 현재 단원에 대한 K와 S가 주어졌을 때, x시간을 사용해 얻을 수 있는 최대 점수는, '현재까지 파악한 x시간을 사용해 얻을 수 있는 최대 점수', 'x-K 시간까지 얻을 수 있는 최대 점수에 이번 단원.. 2024. 4. 8. [자바] 백준 1309 - 동물원 (java) 목차 문제 : boj1309 필요 알고리즘 DP (동적계획법, 다이나믹 프로그래밍) 기본적인 형태의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 Nx2 칸으로 동물원이 구성된다. N칸의 세로는 우선 생각하지 말고, 2칸인 가로칸의 존재 가능한 상태를 생각해보자. 다음과 같이 4가지 종류로 존재 가능하다. 다만 이 중 (d)는 가로로 붙어 있게 배치할 수 없다고 하였으므로 불가하여 (a)~(c)의 3가지만 이.. 2024. 2. 21. [자바] 백준 11066 - 파일 합치기 (java) 목차 문제 : boj11066 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법), 누적합 분할정복 느낌으로 생각해보면 풀이법을 찾을 수 있다. 그리고 구현을 위해 DP와 누적합을 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선, 이 문제의 경우 연속된 파일끼리만 합칠 수 있다는 점을 주의해야 한다. 만약 아무 파일이나 합칠 수 있었다면 그리디로 매번 합쳐진 파일들 중 가장 가중치가 낮은 2개를 합치.. 2023. 8. 10. [자바] 백준 17365 - 별다줄 (java) 목차 문제 : boj17365 필요 알고리즘 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static.. 2023. 7. 10. [자바] 백준 3174 - 나누기 (java) 목차 문제 : boj3174 필요 알고리즘 동적 계획법(다이나믹 프로그래밍, DP), 트라이(Trie) DP를 기본으로 깔고, DP 진행을 효율적으로 하기 위해 트라이를 사용하면 좋은 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 우선 경우의 수를 어떻게 구할 수 있는지부터 생각해보자. 예제 입력 1을 보자. abcd 4 a b cd ab abcd 라는 문자열에서 우선 첫 번째 문자인 a부터 시작해보자. a부.. 2023. 6. 28. [자바] 백준 28017 - 게임을 클리어하자 (java) 목차 문제 : boj28017 필요 알고리즘 다이나믹 프로그래밍 (DP, 동적 계획법) DP로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 개인적으로 국어문제였다.. '바로 이전 회차의 무기는 사용하지 않기로' 라고 써있는걸 대충 읽고 넘어가서, '이전에 사용한 무기는 사용 않기로'로 해석했다 ㅋㅋ. 덕분에 "와.. 비트 dp도 안되는데 이걸 어떻게 한거지? 최소 3~4 차원 dp는 필요할 것 같은데.. 2023. 5. 12. [자바] 백준 1048 - 유니콘 (java) 문제 : boj1048 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 대부분의 경우의 수 문제는 DP로 풀 수 있다. 이 문제도 DP로 풀 수 있다. 누적합 유니콘의 이동 범위 내의 누적합을 구하기 위해 2차원 누적합을 사용하면 빠르다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제 설명이 약간 부족한데, 시작은 어느지점에서 해도 된다! 이것때매 좀 헷갈렸다. 우선 DP를 어떤식으로 진행하는지는 알아야.. 2023. 3. 2. [자바] 백준 13699 - 점화식 (java) 문제 : boj13699 필요 알고리즘 개념 다이나믹 프로그래밍 (동적 계획법, DP) DP 문제이긴한데, 그냥 memoization 문제라고 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 t(n)을 계산하기 위해서는 t(0)부터 t(n-1) 까지의 계산 결과가 모두 필요한데, 이걸 매번 점화식대로 구해주면 당연히 시간초과가 될 것이다. 그러니 매번 x = 1부터 35까지 t(x)를 순서대로 계산해주고, t(x).. 2023. 1. 14. [자바] 백준 16395 - 파스칼의 삼각형 (java) 문제 : boj16395 필요 알고리즘 개념 다이나믹 프로그래밍 (DP, 동적계획법) 파스칼의 삼각형을 한쪽으로 전부 밀어보면 규칙이 보인다. DP로 미리 값을 구한 후, n과 k에 따라 해당하는 값을 출력해주면 된다. DP 문제긴한데 DP라기보다는 그냥 규칙찾는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 파스칼 삼각형을 코드로 어떻게 표현할지 생각해보자. 파스칼 삼각형을 좌측으로 쭉 밀어서 2.. 2022. 10. 25. [자바] 백준 8394 - 악수 (java) 문제 : boj8394 필요 알고리즘 개념 동적계획법 (다이나믹 프로그래밍, DP, dynamic programming) 동적계획법을 안다면 어렵지 않게 풀 수 있다. 동적계획법을 몇 개 풀어봤었다면 풀이를 몇초만에 떠올릴 수 있는 정도로 응용없이 기본적인 형태의 문제이다. 참고로 방법의 수, 경우의 수를 구하는 문제들은 높은 확률로 동적계획법을 사용해 풀리는 경우가 많다. 나머지 연산 (모듈러, modular) 수가 매우 커지므로, 자바의 BigInteger(큰 수 표현 가능. 대신 느림)를 쓰거나, 나머지 연산을 사용해줘야 한다(안해보긴 했는데 BigInteger 사용하면 메모리초과날 것 같긴하다). '%'를 사용하는 나머지 연산을 알고 있어야 더 쉽게 통과 가능하다. ※ 제 코드에서 왜 main 함.. 2022. 8. 6. 이전 1 2 3 다음
