SK_MOUSE 개발일기

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. DynamicProgramming 기술에 의거한다. "거쳐가는 정점"을 기준으로 최단거리를 구한다. 코드는 단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 구현에 있어 크게 어려운 부분은 없다. 단, 유의하여야 할 점은 for문에서 가운데 노드(m)이 제일 위에 있어야 한다는 점이다. 시간복잡도는 O(V^3)O(V3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다. 1을 거쳐가는 경우를 갱신한다 하면 => D[2,3] 과 ( D[2,1] + D[1,3] ) 을 비교하여 최솟값으로 업..

동적프로그래밍(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) : 동일한 작은..