Next dream Next dream

어떤 리스트가 있다고 할 때, 그 리스트에서, 값이 상승하는 순서로, 가장 긴 리스트를 찾는 문제입니다. 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 ..

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) 인 박스가 있으면, // 실제로 박..

루프를 3번 사용해서, 모든 부분집합의 곱을 구한 뒤에, 가장 큰 값을 찾는 방식으로 푸는 방법이 있습니다. 하지만 이방법으로는 time limit에 걸립니다. 길이가 1인 부분집합을 구하고 최대값을 구하고 길이가 1일 부분집합을 길이가 2인 부분집합으로 만들기 위해서, 길이가 1인 부분집합의 다음번 수를 곱합니다. 최대값을 구합니다. 3번 ~ 4번을 반복해서, nums와 같은 부분집합을 만들때 까지 반복합니다. 이렇게 구현하면, accpected는 되지만, 그렇게 속도가 빠른 방식은 아니네요. 곱하기만 하기 때문에, 0과 음수의 개수를 고려 해서, 구현하면 보다 빠른 방식찾을 수 있을 것 같습니다. class Solution { public int maxProduct(int[] nums) { int r..

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

역시나 DP강의 MIT OpenCourseWare에서는 Knapsack도 잠시 스처 지나가듯이 설명하고 지나갑니다. 강의를 보실 분은 여기 클릭 해주세요. DP에서 자주나오는 Kanpsack 입니다. 오늘은 geekofgeek의 knapsack 문제를 풀어 보겠습니다. 문제 링크 https://practice.geeksforgeeks.org/problems/0-1-knapsack-problem/0 코드는 아래 참고하세요~ java source file github ← 클릭~! package com.tistory.skysign.Knapsack; import java.util.Scanner; public class Knapsack { // Knapsack 문제 링크 // https://practice.gee..

hackerrank.com 의 Java 1D Array (Part 2) 문제를 풀어 보겠습니다. 문제 링크 : https://www.hackerrank.com/challenges/java-1d-array/problem 답 코드 링크 : https://github.com/skysign/WSTT/blob/master/hackerrank/Java%201D%20Array%20(Part%202)/src/com/tistory/skysign/hackerrank/Java_1D_Array_Part_2/Main.java Discussion에 보면, loop를 사용해서 풀이도 가능한 것으로 보이지만, 요즘 Dynamic Programming을 공부중이기도 하고, 문제를 봤을 때, DP로 풀어보는 방법이 떠올라서, DP로 풀..

Coin change problem은 어떤 잔돈을 만들 수 있는 동전의 조합의 수를 알아내는 문제입니다. 앞에서 설명한 Minimum Coin Change Problem 문제와 함께, Dynamic Programming에서 주로 다뤄지는 문제입니다. 조건 S = {1,2,3} 동전의 종류는 3개 1, 2, 3 잔돈은 4 잔돈 4를 만들 수 있는 동전종류의 조합의 수 (단, 여기서 동전의 순서는 무시한다.) github link ← 여기 클릭 package com.tistory.skysign.MITOpenCourseWare.R5_Dynamic_Programming; // 코드 보시기 전에, 아래 유튜브 DP영상을 꼭 보시고 코드를 봐주세요. // https://www.youtube.com/watch?v=P..

Minimum Coin Change Problem 은, 아래의 가정에서, 최소 동전의 숫자를 찾는 문제입니다. 몇개의 동전 종류가 있고 S 동전 종류의 수는 M 만들어야할 잔돈 change 문제 자체는 아래링크에 잘 설명되어 있습니다. https://algorithms.tutorialhorizon.com/dynamic-programming-minimum-coin-change-problem/ 좀 무식한 방법으로 recusion으로 풀어 보면 아래와 같습니다. github 에서 보실분은 → Java Source Click!! package com.tistory.skysign.MITOpenCourseWare.R5_Dynamic_Programming; import java.util.ArrayList; // 동전..