https://leetcode.com/problems/knight-probability-in-chessboard/ Knight Probability in Chessboard - LeetCode Can you solve this real interview question? Knight Probability in Chessboard - On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and t leetcode.com 오늘 문제는 dp를 이용한 문제이다...
https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net dfs와 dp를 활용한 문제이다. 핵심 어떠한 발판을 밟는 순간 이후의 동작은 동일해진다. 즉 이후에 탈출을 한다면 그 발판을 밟기 전에도 탈출을 한다는 의미이다. 이러한 사실을 이용해 dp를 적용할 수 있다. 또한 방문했던 곳을 다시 방문한다면 이것은 탈출을 할 수 없다는 의미이다. 이를 활용하여 풀어보자. 정답 코드 import java.util.Scanner; public c..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 핵심 이 문제는 DP를 사용하여 쉽게 풀 수 있다. 테이블 정의 - DP [i] = 카드가 i개일 때 지불해야 하는 최대 금액 점화식 찾기 카드가 1개 들어있는 카드팩을 구매하고 카드 i-1개를 구입한다. 카드가 2개 들어있는 카드팩을 구매하고 카드 i-2개를 구입한다. 카드가 3개 들어있는 카드팩을 구매하고 카드 i-3개를 구입한다. 정답 코드 import java.util.Scanner; class ..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 핵심 백트래킹을 사용하여 풀면 시간초과가 뜨게 된다. 따라서 이 문제는 DP를 사용해야 한다. 우선 물건 1개를 넣을 때 각 무게당 최대 가치는 어떻게 구할 수 있을까? 당연하게도 위와 같다. 1~5에는 6의 무게를 넣을 수 없기 때문이다. 저 자리에 0이 들어가는 것이 맞을까? 당연하게도 6이 들어가는 게 맞다. 3의 가치를 넣을..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 핵심 이 문제는 DFS로 풀면 시간초과가 나게 된다. 따라서 DP를 함께 사용한다. 이미 탐색한 부분은 다시 탐색하지 않는 방법을 이용한다. 정답 코드 import java.util.Scanner; public class Main { static int M; static int N; static int[][] map; static int[] dy = {1, 0, -1, 0}; static int[] d..
동적 계획법(Dynamic Proframming)이란? 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것 작은 나를 해결함으로써 더 큰 나를 해결함 동적 계획법의 문제 풀이 순서 1. 부분 문제를 정의한다. - 무슨 값을 구할지를 정의한다. 2. 점화식을 구한다. - 그 값을 어떻게 구할지에 대한 식을 세운다. ( 부분은 풀려있다고 가정) 3. 문제를 해결한다. - 값을 직접 구하는 코드를 작성한다. 동적 계획법을 활용한 대표적인 예시 피보나치 수 구하기가 있다. 점화식을 활용하기 위해 index 0,1에 해당하는 값을 미리 채워주어야 한다. 반복문을 통해 이전의 값을 활용하여 채워주면서 나아가면 된다. 동적 계획법 활용 문제 개인적으로 동적 계획법 자체는 쉽지만 부분 문제를 정의하는 것이 어..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2579번 계단 오르기 문제 링크입니다. 핵심 계단을 1칸, 2칸 이동 가능하다. 마지막 계단은 반드시 밟아야 한다. 3개 연속으로 계단은 올라갈 수 없다. 가장 중요한 것이 3개의 계단을 연속으로 올라갈 수 없다는 것이다. 정답 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner ..
