백준 - 퇴사2예전에 풀었던 문제인데 풀지 못했다. 대신 확실하게 다시 알고 넘어가자.앞에서부터 뒤로 채워간다. dpi = i일까지 일했을 때 최대 값이다. 그래서 만약 최대 일하는 날짜를 넘어가면 해당 해당 값을 채우지 않는다. i날까지 일했을 때 최대 값은 항상 i

백준 - 점프이번에 DFS를 시도하다가 시간이 터졌다. 예전에 쉽게 푼건데도 안풀린다.

백준 - 출근 경로다른 사람들 풀이를 보고도 이해가 안가서 고민을 많이 했다. 이제는 이해 했다. 결국 DP는 풀고나면 비슷한 형태인 것 같다.

백준 - 1학년

백준 - 도로포장처음에는 K개의 범위가 그리 크지 않아서 백트랙킹으로 완탐을 이용하여 각 경우에 대해 다익스트라를 쓰려고 했다. 하지만 메모리 초과가 났다.dp를 활용해서 풀었다.

백준 - 로봇 조종하기로봇이 왼쪽, 오른쪽, 아래쪽으로 움직일 수 있으니 이전 위치는 현재 위치의 오른쪽, 왼쪽, 위쪽이라는 뜻이 된다. 그 중에서 max 값을 찾으면된다. 하지만 일반적인 이중 for문으로 풀게되면 오른쪽에서 오는 것을 잘 반영할 수 없다. 따라서 t

백준 - 우수 마을거의 다 풀었는데 점화식에서 사소한 실수를 했다.특정 노드가 꺼져 있을 때 최대 값은 그 자손들이 각각 켜져있을때 혹은 꺼져있을 때의 최대값을 더해주면 된다.

백준 - 트리와 쿼리기초적인 트리 dp문제다. 그래프를 만들고 dp 배열을 만드는데 dpi는 i를 루트로 하는 서브트리에서 루트를 포함한 정점의 개수라고 정의했다. 그러면 리프노드에서 1을 반환하면 된다.

백준 - 욕심쟁이 판다그냥 DFS를 다 돌리면 시간 초과가 난다.이번에도 역시 점화식이 중요했는데, dpi를 (i,j)에서 출발해서 갈 수 있는 루트 중 가장 긴 루트의 길이라고 하자. 그러면 이미 dpi는 최적해라는 것이 보장되었기 때문에, 다른 지점에서 길을 찾다가

백준 - LCS예전에 풀었던 문제인데 풀지 못했다. 점화식 설명dpi는 str1의 i번째까지와 str2의 j번째까지 비교했을 때 가장 긴 수열이다. Case1: 만약 str1의 i번째 문자와 str2의 j번째 문자가 다르다면 길이는 dpi-1와 dpi중 최대 값이다Ca

백준 - 평범한 배낭처음에는 이중 for문에서 j를 0부터 시작해서 K까지 돌게했다. 그랬더니 에러가 났는데 그 이유는 배낭에는 물건이 하나씩 있는데, 예를 들어 무게 4에 행복 8짜리가 있으면 무게 4일때 8을 만들고 무게 8일때 또 카운팅하여 무게 16을 만들기 때

백준 - 이동하기dpi를 위치 i에서 가질 수 있는 최대 사탕 개수다. 그렇다면 dpi = Max(dpi-1, dpi-1, dpi)+graphi다. 다만 인덱스가 벗어나지 않는지 체크해줘야한다.

백준 - 동전 2점화식을 어떻게 세우냐가 관건이었다. dpk = k원을 만드는데 드는 동전의 최소 개수 = Min {dp\[k-coin0]+1, dp\[k-coin1]+1, ...}

백준 - 동전 1예전에 풀어봤지만 그때도 풀이를 찾아보고 풀었거나 기억에 의존해 풀었기에 이번 기회에 정리를 한다.N가지 종류의 동전으로 K원을 만드는 방법은 두 가지다.1) N번째 동전 없이 N-1가지의 동전으로 K를 만들기2) N가지 동전으로 K - coinsn의

백준 - 퇴사처음에는 어떻게 재귀로 풀까 고민하다가 N의 길이가 15가 최대인 것을 보고 백트랙킹으로 풀었다. 해당 날짜에 들어갔다면 경우의 수는 두 가지이다. 그 날에 일을하고, 걸리는 시간만큼 건너뛰거나, 그날 일은 건너뛰고 다음날부터 또 결정하거나.

백준 - 하노이 탑 이동 순서로직은 비교적 간단하다. n개의 원판이 있을 때 우선 n-1개의 원판을 2번으로 옮긴뒤 맨밑 원판을 3번으로 옮기고, n-1개의 원판을 3번으로 옮기는 것이다. 처음에는 Stack을 List로 저장해서 쓰려고 했으나 저장은 되는데, List

백준 - 괄호의 값다소 복잡하게 풀었다. 우선 전체 스트링에 대해 for문을 돌면서 stack이 맞아떨어져서 올바른 괄호열이면 그만큼 구분해서 재귀에 들어가게 했다 (단 양측의 괄호는 제거하고 괄호에 따라 점수를 곱한다). 그리고 나머지 부분에 대해 또 재귀를 돌리고해

백준 - 포도주 시식처음에는 dpi = i번째를 마셨을때 i번째까지 최대값이라고 했다가 틀렸었다. 1000, 1000, 1 같은 경우 세번째는 1001 밖에 되지 않는다. 이렇게 되면 맨 마지막에 최대값이 들어가있다고 장담할 수 없다.처음 dp가 0으로 초기화 되어있고

백준 - 계단 오르기dpi를 i번째를 밟았을 떄 i번째까지 최고 점수라고 정의했다. 그러면 dpi = Math.max(dpi-2, dpi-3 + arri-1) + arri가 된다. dpi-1을 사용하지 못하는 이유는 dpi-1의 값이 두번 연속으로 밟아서 얻은 값일 수

백준 - 블랙잭2진법 사용하듯이 해당 인덱스의 수를 취하는 경우, 취하지 않는 경우로 나눠서 backTracking을 진행하였다.