학습목표 1. n개의 행렬의 곱 A1, A2, ... , An을 계산하는 최적의 순서의 순환식을 정의 2. Java언어 기반 행렬의 곱셉 최소 계산 동적계획법 구현 1. 행렬의 곱셈 p*q 행렬 A와 q*r 행렬 B를 곱하여 p*r 행렬 C를 계산한다고 가정할때 코드는 다음과 같습니다. void product(int A[][], int B[][], int C[][]) { for (int i=0; i

학습목표 1. Optimal Substructure에 대해서 학습 2. Optimal Substructure를 가지는 최단경로(Shortest-Path)에 대해서 학습 3. Optimal Substructure를 가지지 않는 최장경로(Longest-Path)에 대해서 학습 1. 동적계획법 수행과정 일반적으로 동적계획법 문제를 해결하기 위한 수행과정은 다음과 같습니다. 동적계획법 문제는 최적화문제(optimisation problem, 최솟값 혹은 최댓값 탐색) 혹은 카운팅(counting) 문제에 적용됨 주어진 문제에 대한 순환식(recurrence equation)을 정의함 정의된 순환식을 기반으로 memoization 혹은 bottom-up 방식으로 해결함 2. 동적계획법 특징 동적계획법의 특징은 다..

1. N-Queens 문제란 무엇인가? N-Queens 문제란 N x N 크기의 체스판에 N개의 퀸 기물끼리 서로 공격할 수 없도록 배치하는 경우의 수를 계산하는 문제입니다. 퀸 기물은 체스에서 가로, 세로, 대각선으로 이동할 수 있는 기물입니다. 예를 들어 N=4이라고 가정할 때 4개의 퀸이 서로를 공격할 수 없는 경우의 수는 아래와 같이 2가지 입니다. 2. N-Queens 접근 방법 2.1 Naive Algorithm N-Queens 문제를 푸는 가장 직관적인 방법은 퀸을 놓을 수 있는 모든 경우의 수중에서 조건(퀸끼리 서로 공격할 수 없는)을 만족하는 경우만을 세는 방법이 있습니다. 하지만 이 방법은 N=4라고 가정할때 모든 퀸을 놓을 수 있는 경우의 수는 4*4*4*4=256 가지입니다. N이 ..

학습목표 1. 행렬 경로 문제의 순환식 구성 2. 순환식 기반의 Memoization, Dynamic Programming 적용한 메서드 구현 3. 경로 구하기에 대해서 학습 1. 행렬 경로 문제 정수들이 저장된 nxn 행렬의 좌상단에서 우하단까지 이동합니다. 단 오른쪽이나 아래쪽 방향으로만 이동할 수 있습니다. 방문한 칸에 있는 정수들의 합이 최소화되도록 합니다. 위의 그림에서 (4,4)를 (i, j)라고 할때 (i, j)에 도달하기 위해서는 (i, j-1) 혹은 (i-1, j)를 거쳐야 합니다. 또한 (i, j-1) 혹은 (i-1, j)까지는 최선의 방법으로 이동해야 합니다. 위의 그림을 기반으로 순환식을 구성하면 다음과 같습니다. 재귀적인 알고리즘 구현 public class Driver { pub..

학습목표 1. 일반적인 피보나치수 재귀 메서드의 중복계산을 개선 2. 일반적인 이항게수 재귀 메서드의 중복계산을 개선 3. Memoization과 Dynamic Programming의 특징에 대해서 학습 1. 피보나치 수(Fibonacci Numbers) 피보나치 수란 0번째 및 1번째 항이 0과 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열입니다. 0 1 1 2 3 5 8 13 ... 피보나치 수의 점화식은 다음과 같습니다. f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2), if n>=2 위의 점화식을 기반으로 피보나치 수의 재귀적인 메서드를 구현하면 다음과 같습니다. public class Driver { public static int fibo(int n) { if(n

학습목표 1. Floyd-Warshall 알고리즘이 무엇인지 학습 2. Floyd-Warshall 알고리즘 수행과정에 대해서 학습 3. Java 언어 기반 Floyd-Warshall 알고리즘 구현 1. Floyd-Warshall 알고리즘이란 무엇인가? 이전글에서 작성한 Bellman-Ford, Dijkstra 알고리즘은 Single-Source 문제의 유형으로 임의의 한 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘이였습니다. Floyd-Warshall 알고리즘은 All-Paris 문제의 유형으로 모든 정점에서 다른 모든 정점으로의 최단 경로를 계산하는 알고리즘입니다. 즉, Floyd-Warshall 알고리즘은 모든 노드의 순서쌍에 대해서 최단 경로를 계산하는 알고리즘입니다. 예를 들어 인..