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

158

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

if less(A[j-1], A[j]):

➊

break

A[j],A[j-1] = A[j-1],A[j]

➊

제공된 비교 함수

less

를 사용해 정렬 방향을 결정한다.

less(A[x], A[y])

가

True

이면

A[x]

는

A[y]

보다 앞에

있는 값이다.

선택 정렬과 삽입 정렬은 값이

N

개인 배열을 정렬하기 위해

N

-

1

개의 단계를 거친다. 각 단계

는 문제 크기를

1

씩 줄인다. 또 다른 전략인

분할 정복

divide

and

conquer

은 한 문제를 해결하기 위

해 작은 하위 문제 두 개로 나눈다.

5.5

재귀와 분할 정복

재귀

recursion

라는 개념은 수세기 동안 수학에 존재해왔으며, 함수가 자기 자신을 호출할 때 일어

난다.

TIP

피보나치

Fibonacci

수열은 두 정수,

0

과

1

로 시작한다. 수열의 다음 정수는 이전 두 수를 더한 값이며, 다

음 정수 몇 개를 보면

1

,

2

,

3

,

5

,

8

,

13

과 같이 진행한다. 수열의

n

번째 정수에 대한 재귀적 공식은

F

(

n

)=

F

(

n

-

1

)+

F

(

n

-

2

)이다. 즉

F

(

n

)은 자기 자신을 두 번 호출하도록 정의된다.

정수

N

의 팩토리얼은

N

보다 작거나 같은 양의 정수를 모두 곱한 것이며 ‘

N

!’으로 쓴다. 예를

들어

5

!=

5

×

4

×

3

×

2

×

1

=

120

이 된다. 이 연산을 다른 방식으로 ...