컴퓨터/수학이랑25 다익스트라(Dijkstra) 알고리즘의 재발견 다익스트라 알고리즘의 pseudo-code와 C 코드는 위키피디아에 잘 나와 있으므로 그곳을 참고한다. 이 글은 어떻게 그 알고리즘을 생각하게 되었을까 를 내 나름대로 생각해 본 후 그에 대하여 쓴 글이다. 요약 다익스트라 최단경로 알고리즘은 다음과 같이 생각해 볼 수 있다. 즉, 경로의 그래프를 실로 되어 있다고 생각하고, 각 지점은 매듭으로 되어 있다고 가정하자. 이와 같은 상황에서 주어진 두 지점을 잇는 최단경로를 찾기 위해서는 그 주어진 두 점을 양 끝으로 잡아 당겼을 때 생기는 직선이 된다. 이것은 자명하다. 다익스트라 알고리즘은, 주어진 경로(그래프)에서 시작점이 주어졌을 때, 각 점으로 가는 최단경로를 구하는 알고리즘이다. 어느 날 나는 그가 어떻게 그 알고리즘을 생각했는지 궁금했다. 그 후.. 2010. 2. 7. Savitzky-Golay smoothing 스무딩은 자료를 매끄럽게 하는 것이라 할 수 있다. 이러한 작업은 데이터를 다루는 것에 있어 거의 필수적이다. 왜냐 하면, 관측되는 거의 모든 데이터는 여러 요인으로 인해 '오차'를 포함하고 있기 때문이다. 그래서 그와 같은 오차를 없애기 위해 여러 통계적 기법을 사용하는데, 스무딩은 통계적이진 않지만 오차를 없애고 원래의 데이터를 추정해 내기 위한 단순한 기법이면서도 효과적인 방법이다. 가장 쉽게 생각할 수 있는 방법은 이동평균(moving average)로, 주어진 데이터 전/후의 일정 개수의 데이터의 평균을 그 데이터의 값으로 추정하는 방법이다. 만약 주어진 데이터에서 멀어지는 점일수록 중요도가 떨어진다면 중요도를 낮추어 주면 된다. 즉, 이동평균은 주어진 데이터와의 거리에 상관없이 모두 동일한 가.. 2010. 1. 16. monotone cubic Hermite interpolation 이전 글에서 설명한 cubic spline interpolation 은 원 데이터의 monotonicity를 보장해 주지 않는다. 말로 설명하는 것보다 그림으로 보면 쉽게 알 수 있다. 위의 그림에서 보면, 파란 열린 원이 원래의 데이터이다. 앞쪽 열에 있는 그림에서 보면 가장 뒤의 두 점을 보면 두 점은 증가하고 있음에도 cubic spline 으로 연결한 것은 아래로 갑자기 내려 갔다 올라가는 것을 볼 수 있다. 오른쪽 열에 있는 그림은, 앞쪽 두 데이터는 올라가고 있는데, cubic spline으로 연결한 곡선은 올라갔다 내려 오는 것을 볼 수 있다. 만약 이와 같이, 원래 데이터가 올라가는 구간이면 interpolation으로 한 것도 올라가고(최소한 내려오는 곳이 있지는 않고), 원래 데이터가 .. 2010. 1. 12. cubic spline interpolation cubic spline은 주어진 점을 매끄럽게 연결하는 알고리즘이다. 왜 cubic 이냐 하면, 두 점을 잇는 곡선을 3차 다항식(a0 + a1x + a2x2 + a3x3)으로 사용하기 때문이다. 즉, 다시 말해, 서로 떨어져 있는 두 점 사이를 연결해야 하는데(그래서 interpolation), 그 연결하는 선을 3차 다항식으로 만들고자 하는 것이다. 이와 같은 목적에 부합하는 알고리즘 중 널리 사용되는 것의 원리는 다음과 같다. 우리가 갖고 있는 점은 위의 녹색점 뿐이라고 하자. 그 중간을 곡선으로 매끄럽게 연결하고 싶다. 즉, 각 데이터 xi, xi+1은 곡선 Si로 연결을 시키는데, 각 Si가 3차 다항식이라고 가정하는 것이다. 이 상황에서, 각 xi+1에서 두 곡선 Si와 Si+1이 부드럽게 연.. 2010. 1. 11. 이전 1 ··· 3 4 5 6 7 다음
