SK_MOUSE 개발일기

동적프로그래밍(Dynamic Programming)의 기본형이 되는 문제이다. Math.max값을 이용하여 이전 인덱스의 값과 비교하여 주어진 배열에 직접 업데이트 하는 방식이다. import java.util.Arrays; class Solution { public int solution(int[][] triangle) { int answer = 0; for (int height = 1; height < triangle.length; height++) { for (int i = 0; i < triangle[height].length; i++) { if (i == 0) {//맨왼쪽 triangle[height][0] += triangle[height - 1][0]; } else if (i == trian..

아래와 같이 number 와 N이 주어지면 N을 몇번을 사용해서 number값을 만들어 낼 수 있는지 구하는 문제이다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 아래와 같은 코드는 점화식을 이용하여, 완전탐색을 하는 방식이다. 아마도 DFS 방식이 이 방식이 아닌가 싶다. 아직은 DFS에 대해 다뤄보지 않아서, 추후 코멘트를 남기겠다. 유사, Combination을 떠오르게 하는 점화식이다. Set을 배열로 각각의 인덱스Set에 여러개의 값이 들어갈 수 있다는 방식을 알아야한다. Set[] setArr = new HashSet[9]; * : combination을 이용하여 각각의 연산기호에 따른 값을 넣는다. (A[2] *..

재귀함수형태로 점화식이 생기는 문제에서 일대일함수임이 만족될때 각 함수의 파라미터를 키로 결과를 캐싱하는걸 dp라함 이때 캐싱하는 자료구조를 편의상 상태공간이라 부르는데 별 의미는 없고 동적계획법(Dynamic programming)은 자료구조에서 동적할당(Dynamic Allocation)과는 다르다. 알고리즘에서 사용되는 "다이나믹(Dynamic)"은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍 문제인지 확인하려면 아래 조건을 만족하는지 확인하면 된다. 1. 최적 부분구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은..