안녕

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming) [알고리즘] 동적 계획법 (Dynamic Programming) 1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, D hi-guten-tag.tistory.com 2022.05.27 - [Computer Science/알고리즘] - [알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법) [알고리즘 - 이론] Branch-and-B..

문제)

1. BST (Binary Search Tree)란? 아마 자료구조 시간에 다 배웠으실 텐데요. BST는 ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 이진 트리이고, 다음의 조건을 만족합니다. 각각의 노드는 하나의 unique한 key를 갖고 있다. node의 left subtree는 node의 key보다 작거나 같다. node의 right subtree는 node의 key보다 크거나 같다. 생각보다 간단하죠? 우리의 목적은 BST에서 검색하는 key와 같은 원소를 찾는 average time을 최소화하는 데 있습니다. 만약에 각 원소가 검색될 확률이 모두 동일하다면, 트리의 높이는 낮을 수록, 그리고 좌우의 높이 차가 덜 클수록 효율적입니다. 하지만 만약에 각 원소가 검색..

문제)

우선 2x3 행렬과 3x4 행렬을 곱해봅시다. 결과물은 2x4 행렬이 나오겠죠? 또한 곱셈의 횟수는 2 x 3 x 4 = 24입니다. 즉 i x j 행렬과 j x k행렬의 곱의 횟수는 i x j x k가 됩니다. 또 다른 예시를 들어봅시다. A X B X C X D이고, A = 20 x 2, B = 2 x 30, C = 30 x 12, D = 12 x 8입니다. 행렬 곱셈은 결합 법칙이 성립하므로, 곱셈의 순서는 결과에 영향을 미치지 않습니다. 즉, (AB)(CD) = (A(B(CD))와 같습니다. 이때 4개의 행렬은 총 5개의 다른 순서로 곱할 수 있습니다. A(B(CD)) : 3680 A((BC)D) : 1232 (AB)(CD) : 8880 ((AB)C)D : 10320 (A(BC))D : 3120 ..

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-..