알고리듬 프로젝트(Dynamic Programming, Perceptron)

1. Algorithm_Project_1_Dynamic_Programming.pdf

알고리즘 프로젝트 1의 주제는 동적 프로그래밍(Dynamic Programming)이다. 동적 프로그래밍은 복잡한 문제를 간단한 부분 문제로 나누어 해결하는 방법론으로, 일반적으로 최적화 문제에 적용된다. 이 방법의 핵심은 중복되는 하위 문제를 기억하여 효율적으로 계산하는 것이다. 동적 프로그래밍은 두 가지 주된 접근법, 즉 메모이제이션과 바텀업 방식으로 구현할 수 있다. 메모이제이션은 재귀적으로 문제를 해결하며, 각 하위 문제의 결과를 저장하여 같은 계산을 반복하지 않도록 한다. 이 방식은 주로 상향식 접근에 적합하며, 각 하위 문제의 답이 확보되면 그것을 다시 쓰는 방식으로 활용한다. 반면 바텀업 방식은 작은 문제부터 해결해 나가며 점진적으로 더 큰 문제를 해결하는 방식을 채택한다. 바텀업 방식은 보통 표를 사용하여 각 단계의 결과를 저장하고 업데이트한다. 동적 프로그래밍의 대표적인 예제로는 피보나치 수열이 있다. 피보나치 수열은 각 항이 이전 두 항의 합으로 정의된다. 일반적인 재귀적인 구현은 지수 시간 복잡도를 가지지만, 동적 프로그래밍을 이용하면 선형 시간 복잡도로 해결할 …