💻 Coding Problems Solving/Dynamic Programming 검색 결과

14 개의 검색 결과가 있습니다.

💻 Coding Problems Solving/Dynamic Programming

[BOJ 1103] 게임

[BOJ 1103] 게임 1. 문제 : https://www.acmicpc.net/problem/1103 2. 풀이 dfs + dp 문제 3. 코드 package baekjoon; import java.util.*; public class Main { static int N, M; static int[][] map; static boolean[][] visit; static int[][] dp; static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); map = ne..

2023. 8. 7. 21:11

💻 Coding Problems Solving/Dynamic Programming

[LeetCode] Subarray Sum Equals K

1. 문제 : https://leetcode.com/problems/subarray-sum-equals-k/ 2. 풀이 다이나믹 프로그래밍 활용한 풀이법 3. 코드 class Solution { public int subarraySum(int[] nums, int k) { // 1. dp int len = nums.length; int cnt = 0; int[] dp = new int[len+1]; for (int i = 0; i < len; i++) { // dp[i]는 현재 인덱스 전(i-1)까지의 누적합 dp[i+1] = dp[i]+nums[i]; } for (int i = 0; i < dp.length; i++) { for (int j = i+1; j < dp.length; j++) { if(dp..

2023. 7. 23. 17:51

💻 Coding Problems Solving/Dynamic Programming

[BOJ 1890] 점프 (java)

1. 문제 : https://www.acmicpc.net/problem/1890 2. 풀이 dfs보다 반복문돌며 메모이제이션 해주는게 빠름 3. 코드 import java.util.Scanner; public class 점프 { static int n; public static void main(String[] args) { Scanner s = new Scanner(System.in); n = s.nextInt(); int list[][] = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { list[i][j] = s.nextInt(); } } long dp[][] = new long[n][n]; dp[0][0] = 1..

2023. 4. 20. 01:37

💻 Coding Problems Solving/Dynamic Programming

[LeetCode] Longest Increasing Subsequence

1. 문제 : https://leetcode.com/problems/longest-increasing-subsequence/ 말그대로 증가하는 배열 찾기 2. 풀이 dp 문제 역순으로 돌면서 자신보다 큰 수의 dp 중 가장 큰값 +1을 dp에 저장 이때 증가하는 것을 신경 쓸 필요가 없는 이유 -> 시작부터 나보다 큰수를 dp에 저장해가며 반복문을 돌기때문에 해당 dp에 저장된 값 자체가 증가하는 경우의 수만 고려한 것이기 때문 나보다 큰 수 dp중 가장 큰 값을 고르는 이유? -> 계속 증가하는 값 중 가장 많은 경우의 수를 구해야하기 때문 ex) 숫자 2는 코인2 한번에 만들 수 있음 -> 이걸 어떻게 dp로 자동으로 하냐? -> dp[i-money즉 0] +1 과 dp[i] 값 중 비교해서 넣으면됨..

2023. 3. 30. 05:07

💻 Coding Problems Solving/Dynamic Programming

[LeetCode] Coin Change

1. 문제 : https://leetcode.com/problems/coin-change/ 동전을 최소로 사용해 특정 숫자를 만들기 (중복사용 가능) 2. 풀이 dp 문제 동전 최소크기인 11보다 +1수를 max값으로 dp에 저장하고, 해당 숫자를 만들 수 있는 최소사용횟수를 비교하며 구하는 방식 (어려움...) ex) 숫자 2는 코인2 한번에 만들 수 있음 -> 이걸 어떻게 dp로 자동으로 하냐? -> dp[i-money즉 0] +1 과 dp[i] 값 중 비교해서 넣으면됨 3. 코드 class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; Arrays.fill(dp,amount+1); dp..

2023. 3. 29. 00:10

💻 Coding Problems Solving/Dynamic Programming

[LeetCode] Maximum Product Subarray

1. 문제 : https://leetcode.com/problems/maximum-product-subarray/ 하위 array 곱 중 최대값 2. 풀이 실시간으로 max, min 값을 가지고 현재 값에 곱해주고 값을 비교하는 방식으로 최대값을 update dp 기본문제..ㅠㅠ 3. 코드 class Solution { public int maxProduct(int[] nums) { int maxProducts = nums[0]; int minProducts = nums[0]; int ans = nums[0]; for(int i=1;i

2023. 3. 28. 21:57