Go Gradually - Repository

188. Best Time to Buy and Sell Stock IV - Streak 1

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..

배낭(knapsack) 문제는 보통 제한된 용량의 컨테이너에 물건들의 부분집합을 넣되, 물건과 관련된 어떤 양을 세거나(카운트) 최적화하는 문제를 다룬다.거의 항상 각 물건은 양의 무게를 가지며, 우리가 선택한 물건들의 총 무게는 어떤 수로 주어지는 컨테이너의 용량을 초과해서는 안 된다. 배낭 유형 문제의 변형으로는 다음과 같은 것들이 있다.0/1 배낭 문제: 물건들의 부분집합을 골라 총 가치를 최대화하되, 총 무게가 컨테이너의 용량을 넘지 않도록 한다.가능한 총 무게 찾기: 컨테이너 용량을 넘지 않게 임의의 부분집합으로 만들 수 있는 모든 총 무게를 구한다.정확히 채우는 경우의 수 세기: 총 무게가 정확히 컨테이너 용량이 되도록 하는 물건의 순서열이 몇 개인지 센다(순서가 중요할 수도 있고 중요하지 않..

사실 이번 장에서는 밑바닥부터 시작하는 딥러닝 1의 경우 계산 그래프를 이용해 설명을 진행한다.해당 방식의 경우 그래프 개념으로 이해하기 쉽게 설명되어 있지만, 기계적인 암기 방법이라 시간복잡도 개선에 대한 인사이트를 얻긴 쉽지 않았다.따라서 이번 장의 내용은 책의 내용이 아닌 수식으로 정리한 방식으로 설명을 진행한다.계산 그래프와 시각 자료를 이용한 설명이 필요하시다면, 해당 책을 구입하셔서 보시는 것을 추천드립니다. 책 내용도 좋습니다.기존 방식먼저 들어가기 전에, 기존 방식의 문제점을 파악해보자.식 정리모델이 갖고 있는 가중치의 집합을 θ라 하자.아래를 "특정 y에 대한 손실 함수"라고 하자.전체 우리가 최소화하고자 하는 전체 손실 함수(Cost function)은 다음과 같이 표현될 것이다.수식에..