안녕

1. DP의 개발절차 1. 최적의 해답을 주는 재귀 관계식을 세운다. -> Divide and Conquer를 해본다. 2. bottom-up 방식으로 최적 해를 찾는 계산한다. 3. bottom-up 방식으로 최적 해를 구축한다. 보통은 2번과 3번이 동시에 이루어집니다. 만약 답만 구하고 최적화를 하지 않는다면, 3번이 빠져있는 것입니다. 최적화 문제를 모두 DP로 풀 수 있는 것이 아닙니다. 문제에 최적의 원칙이 반드시 성립해야합니다. 최적의 원칙은 다음과 같습니다. The Principle of Optimality if an optimal solution to an instance of a problem always contains optimal solutions to all subinstance..

from os import sep import sys from copy import deepcopy input = sys.stdin.readline def func(T, P, n): # 최대 경로를 찾는 함수 # T[i][j]는 T[i-1][j-1]과 T[i-1][j]중에 큰 값을 고르면 된다. for i in range(1, n): for j in range(i + 1): k = max(T[i-1][j-1], T[i-1][j]) T[i][j] += k if k == T[i-1][j]: P[i][j] = 2 else: P[i][j] = 1 def path(T, P, i, j, p): # 경로를 찾는 함수 if i > 0: k = P[i][j] if k == 2: path(T, P, i-1, j, p) #..

문제)

문제)

최단 경로를 찾는 두 가지 대표적인 알고리즘 중에 하나입니다. 다른 하나는 다익스트라 알고리즘이 있는데, 이는 탐욕법에서 알아봅니다. 프로이드의 알고리즘은 모든 점에서 모든 다른 점까지의 거리를 알아냅니다. 최단 경로 문제는 Optimization Problem입니다. 여러 가지 해답의 후보가 있고, 각 후보마다 값이 있고, 우리는 최적의 값을 찾아야 합니다. (여기서는 경로의 최솟값) 최단 경로의 문제에서 한 마디에서 다른 마디로 가는 최단 경로는 하나 이상이 있기 때문에, 여기서는 최단 경로 중 하나를 찾습니다. 1. 알고리즘 시작은 단순무식한 접근법 (Brute-Force)입니다. 한 정점에서 다른 정점으로 가는 모든 경로를 구한 후, 그 경로 중 최솟값을 찾는 방법입니다. 이때 경우의 수는 (n-..

문제)

다들 이항 계수 아시죠? \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0

1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, DP는 bottom-up 방식을 이용합니다. 가장 작은 instance의 답을 먼저 구하여 저장하고, 필요하면 꺼내 쓰는 '동적 계획'입니다. 여기서 계획이란 문제 해결을 위한 배열(테이블)을 구축한다는 뜻입니다. DP 알고리즘의 개발 절차는 다음과 같습니다. 문제의 instance의 해답을 구하는 재귀 관계식을 세운다. (top-down approach, Divide and Conquer 방식) 작은 instance부터 해결하는 bottom-up 방법으로 전체 instance에 ..

Description 우리 교재의 Chapter 2, Exercise 42번 (p. 94)을 풀어보자.이 문제는 분할정복의 대표적인 문제로, 트로미노 타일링 문제로 널리 알려져있다.단, 이 실습과제에서 트로미노 타일의 번호는 트로미노를 놓는 순서로 정한다.예를 들어, 다음과 같은 트로미노 퍼즐은 아래와 같은 순서로 트로미노를 놓는다. Input 첫 번째 줄에 n, row, col이 주어진다.n은 n*n 트로미노 퍼즐 보드의 크기이다. (2의 거듭제곱 수라고 가정해도 된다.)row, col은 구멍의 행과 열이다. 0 <= row, col <= (n - 1) Output 트로미노를 놓는 순서대로 타일에 번호를 부여한 보드를 출력한다.구멍 타일의 번호는 0으로 한다. Sample Input 1..

가능하다면 다음 두 가지 경우에 대해서는 분할 정복을 피해야 합니다. instance of size N is divide into two or more instances each almost size n. 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때 이렇게 분할하면 지수 시간 알고리즘이 나옵니다. instance of size N is divied into almost n instances of size n/c, where c is a constant 4개로 쪼갰는데, 다시 4번의 재귀할 때, 혹은 2개로 쪼갰는데, 2번 재귀할 때 이렇게 분할하면 \(n^{\Theta(nlgn)}\)의 알고리즘이 나옵니다. 만약 피보나치수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결..