러시안 페인트공 (2) 썸네일형 리스트형 메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬) 이 포스팅에서는 메모이제이션을 논하려고 합니다. 메모이제이션은 중복되는 연산의 결과를 저장하여, 연산 횟수를 줄이는 소프트웨어 엔지니어링 기술입니다. 소프트웨어 개발 중에는 항상 하게 되는 선택이 cpu를 사용하는가 메모리를 사용하는가입니다. 이 기술은 컴퓨팅 리소스 중 cpu의 사용량을 줄이는 대신 메모리의 사용량을 늘려줍니다. 메모이제이션을 잘 사용하면 다양한 알고리듬을 가속화할 수 있는 아주 중요한 기술입니다. 긴 글과 개념적인 설명은 여기서 마치겠습니다. 자세한 설명을 원하시면... 전공서적이나 위키피디아를 참고하세요. 여기선 간단한 예제로 설명하겠습니다. 사용하는 예제는 피보나치수열입니다. 피보나치 수열의 알고리듬 구조상 설계는 자연스럽게 재귀 호출이 되고, 메모이제이션을 이용하면 구동 시간을 .. 러시안 페인트공 알고리듬 오래전 조엘 스폴스키 의 책을 보면서 여러 가지를 배웠습니다. 그중 하나가 러시안 페인트공 알고리듬이었습니다. 지금은 아마도 누군가에게 책을 빌려 준거 같고, 개요만 머릿속에 남아 있습니다. 기억을 더듬어 알고리듬을 설명하고, 해결 방법과 함께 짧은 포스팅을 하려고 합니다. 러시안 페인트공 알고리듬(정확한 내용이 필요하시면 책을 보시거나, 조엘의 블로그를 보거나, 다른 분들의 포스팅을 보세요. ) 어떤 건설 업자가 도로를 만들었습니다. 긴 도로가 완성되고, 이제 남은 일은 도로에 차선을 그리는 일입니다. 마침 도로의 시작위치에 러시안 페인트공이 운영하는 페인트 가게가 있습니다. 업자는 러시안 페인트공에게 차선을 그리는 일을 맡겼습니다. 첫째날 러시안 페인트공은 300미터의 차선을 그립니다. 업자는 결과에.. 이전 1 다음
