내가보려고만든 메자노트

DP란? 부분 문제의 결과 값을 이용해 전체 문제를 풀어나가는 알고리즘 방법이다. 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제 (overlapping subproblems)라고 한다. 이를 한 번만 계산하여 저장하고 다음에는 이 결괏값을 이용해서 풀이하면 된다. 메모이제이션(Memoization) 이미 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션(Memoization)이라 한다. 1) 특정 함수가 호출되었을 때, 배열에 해당 값이 저장되어 있는지 확인. 존재한다면, 해당 값을 return. 2) 존재하지 않는다면, 값을 계산하고 배열에 저장한 뒤 해당 값을 return. - 메모이제이션은 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수, 참조적 투명 함수(referent..

문제보러가기 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 DP문제로 크게 어렵지는 않았지만 나의 경우 마지막 날짜인 n일까지 일할 수 있다는 것을 놓쳐서 시간이 좀 더 걸렸던 문제였다 ㅎ,,, 문제풀이 -주어진 시간을 저장하는 t [] 배열과 금액을 저장하는 p [] 배열을 생성한 후 값을 저장한다. -해당 날짜까지 받을 수 있는 최대 금액을 저장하는 dp배열을 생성한다. -총금액 중 최대 금액을 저장하는 max를 선언한다. -여기서 중요한 점 dp배열은 dp [n]..

문제보러가기 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이문제는 DP의 개념과 배열로 삼각형을 접근하는 방법만 알면 어렵지않게 풀 수 있는 문제였던것 같다. 문제풀이 -DP배열에 이전까지와 현재 값을 더한것중 큰것을 넣는다. -위의 그림처럼 배열이 생성되고 따라서 빨간 화살표부분이 DP[i][j]이면 DP[i-1][j-1],DP[i-1][j]에서 내려올 수 있는 것이다. -따라서 DP[i][j] =Math.max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j] 가 된다. -여기서 고민해 봐야할 것은 삼각형 면들에 있는 즉 j==0일때와 j==i일때의 경우..

문제보러가기 코딩테스트 연습 - N으로 표현 programmers.co.kr 이문제는 dp로 분류되어있는 문제이다. dp란 작은 문제로 쪼개서 그 작은 문제를 저장해 놓았다가 다시 사용하며 답을 구하는 것이다.라고 생각했는데 처음에 이 문제가 어떻게 dp로 접근하지..? 여기부터 막혔었다..ㅎ 1개 사용 2개 사용을 이용해서 3개 사용을 할 수 있다는 것을 깨닫고 저장하여서 풀었던 문제이다! 개념이 흔들리니 문제 풀기가 막막했다는... dp알고리즘에 대한 개념을 제대로 정리해봐야겠다고 생각했다 문제풀이 -주어진 N이 1 ~ 8개로 만들 수 있는 모든 숫자를 dp에 저장한다. -dp [i] = {dp [j] , dp [j-i]} -> ex) dp [3] = {dp [1] , dp [2]} , {dp [2]..