이야기에 앞서이번 이야기는 문자열 검색 (String search) 입니다.기본적인 개념은 주어진 문자열 (text)에서 특정 문자 (pattern)의 등장 위치를 찾는 것으로 문자열 검색, 문자열 탐색, String Matching  그리고 String Searching 등 다양한 이름으로 불리지만 모두 동일한 의미를 갖고 있습니다. 문자열 검색 알고리즘은 컴퓨터 과학에서 매우 중요한 주제 중 하나로 텍스트 에디터, 검색 엔진, 데이터 압축, 문자열 인코딩 등 다양한 분야에서 사용됩니다. 저희가 문서 작업에서 자주 사용하는 기능인 찾기 (CTRL+F)가 이러한 문자열 검색 알고리즘을 사용하는 대표적인 사례라고 볼 수 있죠. 이번 이야기에서는 가장 기본적인 방식의 Naïve 문자열 검색 알고리즘을 시작으..

이야기에 앞서이번 이야기는 메모이제이션 (Memoization) 입니다.정확히 같은 뜻은 아니지만 편의상 더 넓은 개념인 동적계획법 (Dynamic Programming) 이라고도 부르죠. 동일한 문제를 반복적으로 계산해야 할 때이전에 계산한 결과를 기억해 중복적인 계산 과정을 생략한다.  메모이제이션은 문제를 해결할 때 "이미 계산한 결과가 있으면 다시 계산하지 않는다"라는 간단한 개념에서부터 시작합니다. 정말 단순한 내용이지만 정확히 어떤 상황에서 사용할 수 있는 개념인지 그리고 어떤 방법으로 계산된 결과를 저장할 수 있는지는 말로만 듣고 이해하기란 쉬운 일이 아니죠. 그래서 이번 이야기에서는 백준 1520번 문제 내리막 길을 직접 풀어보면서 메모이제이션에 대한 전반적인 개념을 이해하고 코드로서 표현..