cloge 이야기

venntum.tistory.com 로 이전했습니다.

보통의 점화식의 경우, 매 항의 값을 식의 정의를 통해 구하게 된다. 하지만 구하고자하는 항이 10억번째 항과 같이 매우 큰 수번째 항을 구해야 하는 경우, 모든 값을 일일이 계산하기엔 처리 속도에서 문제가 생긴다.하지만 최대 10억번째 항까지의 값이 필요하다고 해도 한 개의 항의 값만 필요하거나 그 범위 내 10만개 등 몇 개의 항의 값만을 알아내야한다면 전체를 다 계산하는 것이 아닌, 일부를 계산하는 방법으로 해결할 수 있다. 행, 열의 길이가 최대 m인 행렬로 표현 가능한 점화식의 한 항을 O(lgN * m^3)에 해결할 수 있는 방법 위와 같이 주어진 점화식이 있을 경우, 이를 행렬로 다음과 같이 표현 가능하다. 이 때, 라 정의하면, 행렬의 거듭제곱의 성질을 이용하면임을 알 수 있고, 이로써 A..

Sliding Window(슬라이딩 윈도우)란 수행 과정에서 필요한 전체 메모리를 할당하는 것이 아닌 매 수행마다 필요한 부분만큼만을 저장하여 사용함으로 메모리를 절약, 공간 복잡도를 낮추는 기법이다. 즉, 수행한 이후에 사용하지 않게 되는 기록을 버림으로 매 순간 필요한 정보들만을 저장, 이용한다. 이러한 형태가 실제로 필요한 메모리 할당들을 지정된 크기의 창문에 할당한 이후, 그 메모리를 창문으로 밀어넣음으로서 매 순간에는 창문 크기 내의 정보만을 이용하는 것과 같아 Sliding Window라고 불린다. 창문 창문에 밀어넣을 배열 창문과 배열에서 값의 이동 피보나치 함수를 예로 들어보자. Fn+1 = Fn + Fn - 1 (n > 2) , F2 = 1, F1 = 1 DP를 이용하여 임의의 N에 대해..