전체 글
-
B - Frog 2 / atcoder.jpatcoder.jp 2019. 12. 26. 19:49
A - Frog 1을 푸셨다면 충분히 풀 수 있는 문제입니다. \begin{aligned} 문제 정의에 따라서, 2\leq N \leq 10^5 \\ v_i : i 번째\quad 까지도착하는대\quad 도달하는\quad 최소\quad 비용 (0 \leq i < N) \\ h_i 는 각 돌의 이동 비용 \\ v_i = min(abs(h_{i-k}-h_i)+v_{i-k}) \quad 1 \leq k < K \quad and \quad i-k \geq 0 \\ \end{aligned} import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..
-
A - Frog 1 / atcoder.jpatcoder.jp 2019. 12. 26. 16:10
문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_a 답 자바 코드 링크 : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/A%20-%20Frog%201/src/Main.java $$ 코드에서\quad 배열\quad v[i]\quad : \quad개구리가\quad i번째\quad stone에\quad 도달하는\quad 최소비용 $$ 이 문제를 식으로 풀어 보면 배열 v[i] 는 아래와 같이 계산됩니다. $$ v_i = min(abs(s_{i-1} - s_{i}) + v_{i-1}, abs(s_{i-2} - s_i) + v_{i-2}) $$ import java.util.Scanner; // A - Frog 1 / a..
-
Hamiltonian Path / geeksforgeeks.orggeeksforgeeks.org 2019. 12. 25. 20:13
Hamiltonian Path / geeksforgeeks.org 주의사항 1 8 이렇게 되어 있어도, 1,8 8,1 2개의 방향 모두 이동 가능함 시작이 항상 1부터가 아니고, 모든 vertex에서 시작할 수 있음 문제 링크 : https://practice.geeksforgeeks.org/problems/hamiltonian-path/0 문제 해설 : https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/ 정답 코드 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Hamiltonian%20Path/src/GFG.java import java.util.Scanner; // Ha..
-
Nth Fibonacci Number / geeksforgeeks.orggeeksforgeeks.org 2019. 12. 25. 07:16
사실 풀기는 어제 저녁에 풀었는대, 오늘 올리네요... 점점 게을러 저서 큰일입니다. ps : 어제 시켰던 삼겹살은 맛있었다는 ㅋㅋ 문제 링크 : https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0 문제 해설 : https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ 정답 자바 소스 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Nth%20Fibonacci%20Number/src/GFG.java import java.util.Scanner; // Nth Fibonacci Number / geeksforgeeks..
-
Longest Increasing Subsequence / geeksforgeeks.orggeeksforgeeks.org 2019. 12. 24. 09:23
어떤 리스트가 있다고 할 때, 그 리스트에서, 값이 상승하는 순서로, 가장 긴 리스트를 찾는 문제입니다. 5 8 3 7 9 1 이 주어졌다고 하면, 5, 7, 9 이렇게 3이 Longest Increasing Subsequence 가 됩니다. Box stacking문제를 풀기전에 미리 풀어 봤더라면, 좋았을 문제입니다. DP의 Memoization을 공부할 수 있는 좋은 문제입니다. Longest Increasing Subsequence 문제 링크 Longest Increasing Subsequence 문제 해설 문제 푼 자바 소스 import java.util.Scanner; public class GFG { public static void main(String[] args) { Scanner sc ..
-
Box Stacking / geeksforgeeks.orggeeksforgeeks.org 2019. 12. 23. 16:46
Dydnamic Programming의 대표적인 문제 중의 하나입니다. Box Stacking geeksforgeeks.org 사이트의 Box Stacking문제를 풀어 보겠습니다. 문제 링크 → Box Stacking 자바 소스를 찾으 시는 분은 여기→Github link import java.util.Arrays; import java.util.Scanner; // https://practice.geeksforgeeks.org/problems/box-stacking/1 // 문제 설명이 부족한 부분이 있습니다. // 박스를 돌릴 수 있다고만 설명 되어 있지, // 돌린 박스는 중복해서 사용할 수 있는 것으로 풀어야 합니다. // 즉, 1, 2, 3 (h, w, l) 인 박스가 있으면, // 실제로 박..
-
152. Maximum Product Subarray / LeetCode카테고리 없음 2019. 12. 16. 18:37
루프를 3번 사용해서, 모든 부분집합의 곱을 구한 뒤에, 가장 큰 값을 찾는 방식으로 푸는 방법이 있습니다. 하지만 이방법으로는 time limit에 걸립니다. 길이가 1인 부분집합을 구하고 최대값을 구하고 길이가 1일 부분집합을 길이가 2인 부분집합으로 만들기 위해서, 길이가 1인 부분집합의 다음번 수를 곱합니다. 최대값을 구합니다. 3번 ~ 4번을 반복해서, nums와 같은 부분집합을 만들때 까지 반복합니다. 이렇게 구현하면, accpected는 되지만, 그렇게 속도가 빠른 방식은 아니네요. 곱하기만 하기 때문에, 0과 음수의 개수를 고려 해서, 구현하면 보다 빠른 방식찾을 수 있을 것 같습니다. class Solution { public int maxProduct(int[] nums) { int r..
-
70. Climbing Stairs / LeetCode카테고리 없음 2019. 12. 16. 16:25
Dynamic Programming을 recurssion으로 사용해서 아래와 같이 풀면, 시간 초과로 failed 이 됩니다. 시간 초과에 대한 자세한 내용은 아래 블로그에 잘 설명되어 있습니다. https://sedew.tistory.com/m/44 입력값 N 의 N+1만큼 메모리를 사용해서, sub problems의 결과를 메모리에 저장해서, 한번 계사한 sub problem은 다시 계산하지 않도록 코딩해보겠습니다. class Solution { public int climbStairs(int N) { if(N < 2) { return N; } int r[] = new int[N+1]; r[0] = 1; r[1] = 1; for(int i=2; i