OSgood의 개발일기

이번 포스팅에서는 Dynamic Programming의 개념적인 내용을 살펴보겠다. 자세한 적용 예는 좀 더 공부한 후에 더 자세히 포스팅하도록 하겠다. Dynamic Programming는 간단히 말해 부분 문제의 해를 결합해 문제를 해결하는 것을 의미한다. 부분 문제가 서로 중복될 때,즉 부분 문제가 다시 자기 자신의 부분 문제를 공유할 때 적용할 수 있다. 부분문제를 푸는 것은 분할정복 기법(재귀방법)과 비슷하지만 다른 점이 있다. 분할 정복 기법 VS Dynamic Programming 분할 정복 기법(재귀적 방법) Dynamic Programming 부분 문제를 단순히 반복적으로 계산하여서 해결한다. 필요 이상의 계산이 필요하기 때문에 시간이 오래걸릴 수 있다. 부분 문제를 해결한다는 점은 분할..

Conjugate Gradient 에 대해서 일단 간략하고 이해하고 쉽게 포스팅을 하도록 하겠다. Conjugate Gradient에 대해 정확하진 않지만 이해하기 쉽게 설명하도록 하겠다. 좀 더 자세한 내용을 알고 싶으신 분은 J. Shewchuk. An introduction to the conjugate gradientmethod without the agonizing pain. 을 쭉 읽어보는 것을 적극 추천한다. Conjugate Gradient을 이용하는 이유는 Ax = b(이 때, A는 matrix, x는 vector, b도 vector) 을 풀고 싶을 때(즉, 연산을 통해 x를 구하고자 할 때) A의 매트릭스가 너무 커지게 되면 A의 역행렬을 b에 곱해서 구하는 계산자체가 매우 부담이 된다..