똑똑한 코드 작성을 위한 실전 알고리즘

19

1

장

문제 해결

이 장에서 배울 내용은 다음과 같다.

●

문제를 해결하는 여러 알고리즘

●

크기가

N

인 문제 인스턴스에서 알고리즘의 성능을 고려하는 방법

●

주어진 문제 인스턴스를 해결할 때, 주요 작업이 수행된 횟수를 세는 방법

●

문제 인스턴스를 두 배씩 늘리며 증가 기준을 결정하는 방법

●

크기가

N

인 문제 인스턴스에서 알고리즘이 주요 작업을 수행한 횟수를 세어 시간 복잡도를 측

정하는 방법

●

크기가

N

인 문제 인스턴스에서 알고리즘이 요구하는 메모리 양을 결정해 공간 복잡도를 측정

하는 방법

1.1

알고리즘이란

알고리즘 동작 방식을 설명하는 일은 스토리텔링과 같다. 각 알고리즘은 참신한 개념 혹은 원

래 해결책을 뛰어넘는 혁신을 가져온다. 이번 장에서는 간단한 문제에 대한 몇 가지 해결책을

탐구해보면서 알고리즘 성능에 영향을 미치는 요소들을 알아본다. 그 과정에서 알고리즘의 구

현과 독립적으로 성능을 분석하는 기술을 소개하되, 실제 구현을 통한 경험적인 증거를 제공할

것이다.

문제 해결

CHAPTER

1

20

똑똑한 코드 작성을 위한 실전 알고리즘

NOTE

_ 알고리즘은 예측 가능한 시간에 ...