반응형

분할정복 2

A Marketing Strategy (Closest-pair problem)

입력 파일이 좌표(x,y)로 주어지고 가장 가까운 두 점을 찾는 문제. Divide-conquer 기법을 사용한 Closest-pair problem(최근접 점의 쌍)으로 문제를 해결한다. Problem A telephone company seeks to claim they provide high-speed broadband access to customers. It will suffice for marketing purposes if they can create just one such link directly connecting two locations.  As the cost for installing such a pair of locations are the shortest distance ap..

문제 2022.12.12

[알고리즘] Dynamic Programming (동적 계획법)

동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다. 답을 구하기 위한 계산을 반복하는 구조, 즉 같은 답을 계속 내서 다른 값을 이용해야 하는 문제(대표적으로 피보나치 수열)에 매우 뛰어난 방법이다. 분할 정복 기법 - 큰 문제를 작은 문제로 쪼개어 풀이하는 알고리즘에서 값을 저장하는 로직이 추가되었다고 할 수도 있다. 가장 중요한 아이디어는 문제를 재계산(예를 들어 재귀적으로 풀이하는 기법)하지 않는 것이고, 이를 막기 위해 값을 기억하거나 테이블을 만들어 해결한다. 그러므로, 최종 목표를 달성하기 위한 단계를 한 번 씩만 풀게 된다는 것을 ..

알고리즘/DP 2022.10.11