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

23

1

장

문제 해결

최근

CPU

는

1

초에

수십억

개 명령을 실행할 수 있기 때문에, 알고리즘을 위한 기계 명령어가

수행된 총 횟수를 계산하기는 거의 불가능하다! 대신에 ‘배열 내 두 값이 서로 비교된 횟수’나

‘함수가 호출된 횟수’와 같이 각 알고리즘에서 주요 연산이 수행된 횟수를 계산하자.

max

()

에

서 주요 연산은 ‘미만 (

<

) 연산자가 호출된 횟수’다.

2

장에서 이 계산 원리를 확장할 것이다.

이제

max

()

알고리즘의 동작을 자세히 살펴보자.

1.2

리스트에서 가장 큰 값 찾기

[코드

1

-

1

]의 파이썬 구현에는 결함이 있다. 적어도 하나의 값을 가지는 리스트

A

에서 각 값을

my

_

max

와 비교하고 더 큰 값이 있으면

my

_

max

를 업데이트함으로써 가장 큰 값을 찾는다.

코드

1-1

리스트에서 가장 큰 값을 찾는 코드 - 결함이 있는 코드

def flawed(A):

my_max = 0

➊

for v in A:

➋

if my_max < v:

my_max = v

➌

return my_max

➊

my_max

는 최댓값을 가진 변수다. 이 예제에서는

0

으로 초기화한다.

➋

for

루프에서

A

의 각 요소를 순회해 저장할 변수

v

를 정의한다.

if

문은 각

v

값에 대해 한 번 실행한다.

➌

v

가

my_max

보다 크면

my_max

를 업데이트한다.

솔루션의 핵심은