CS

메모이제이션 메모이제이션이란 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술입니다. 이는 동적 계획법(Dynamic Programming)에서 핵심이 되는 기술입니다. 캐싱이라고 표현되기도 합니다. 예를 들어 재귀 함수를 사용한 피보나치 수열 함수가 있다고 해봅시다. func fibonacci(_ n: Int) -> Int { if n Int { var fiboArray: [Int] = [0, 1] guard n > 1 else { return n } for num in 2...n { fiboArray.append(fiboArray[num - 2] + fiboArray[num - 1]) } return fiboArray..

LCS LCS란 보통 최장 공통 부분수열(Longest Common Subsequence)을 의미하지만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 여기에서 부분수열(Subsequence)과 문자열(Substring)의 차이는 문자열이 연속적인지 아닌지에 따라 달라지는데요, 연속적이라면 문자열(Substring)이고, 비연속적이면 부분수열(Subsequence)입니다. 다음과 같은 예시가 있다고 가정해봅시다. [AUTABBEHNSAAB, BCUAMEFKAJNAAB] 위 예시에서 AAB는 연속적이기 때문에 문자열이라고 할 수 있고, UAENAAB는 비연속적이기 때문에 부분 수열이라고 할 수 있습니다. 위에서 말한 두 가지의 LCS를 구현하는 방법에 대해 알아보겠습니..