[가장 쉬운 알고리즘 책] 언제라도 쉽게 오를 수 있는 "알고리즘의 계단"을 향하여

■ 본문 중에서

#1-1 이해하기 쉬운 알고리즘이 좋은 알고리즘은 아니다

#1-2 작은 문제를 풀 수 있다고 큰 문제를 풀 수 있는 것은 아니다 - 문제 크기의 유형을 어떻게 평가할 것인가? - 25∼29p.

그림2. 계산량을 증가시키는 방법

1) Log(n) 배 : 데이터의 양이 10배가 되면 계산량은 3.3배 (문제의 복잡도에 의해 증대)

2) N 배 : 데이터의 양이 10배가 되면 계산량도 10배 (문제의 크기에 의해 증대)

3) n log(n) 배 : 데이터의 양이 10배가 되면 계산량은 3.3 * 10 = 33배 (문제의 복잡도와 크기에 의해 증대)

4) n2 배 : 데이터의 양이 10배가 되면 계산량은 100배 (문제의 난이도와 크기 이외에 다른 요인에 의해 증대)

데이터의 양에 대해 계산량이 어떻게 증가하는지에 대한 지표로서 알고리즘 세계에서는 "Order 표기법"을 주로 사용합니다. 한마디로 말해 Order 표기법은 "자리수의 문제"입니다.

Order 표기법으로 위의 1)-4)를 표현하면

- 1) 문제의 복잡도에 의해 계산량이 증대하는 O(log(n)) 알고리즘

- 2) 데이터의 양에 의해 계산량이 증대하는 O(n) 알고리즘

- 3) 문제의 복잡도와 데이터의 양에 의해 계산량이 증대하는 O(n log(n)) 알고리즘

- 4) 문제의 복잡도와 데이터의 양 이외에 다른 요인에 의해 계산량이 증대하는 O(n²)알고리즘 

그림3. 문제의 복잡도는 사람에 따라 달라진다!?

#2-6 이진검색 트리에 "익숙해지기 힘들다"고 느끼는 이유 - 56p.

이진트리 검색이란 "이진검색 트리"라고 불리는 데이터 구조를 만든 다음, 이 데이터 구조를 구성하는 단순한 규칙인

좌측 자식 < 부모 ≤ 우측 자식

에 의해 데이터를 검색하는 방법입니다. 데이터는 이미 정렬되어 있다고 합시다. 이번 장에서 다뤘던 알파벳의 경우 ABC 순으로 정렬되어 1∼26의 번호가 부여된 상태라고 할 수 있습니다.

그리고 이 데이터를 이진검색 트리구조에 나열합니다. 예를 들면 다음과 같습니다.

이진검색 트리구조의 규칙은 매우 단순합니다. "좌측자식 < 부모 ≤ 우측 자식"을 만족시키기만 한다면 어떤 식으로 정렿해도 괜찮습니다. 이 단순한 규칙에 의해 강력한 검색을 할 수 있게 되는 것입니다.

#4-0 계산하기 전에 계산에 필요한 시간을 알지 못해도, 처리 규모를 추측할 수 있다 (Order 표기법) - 85∼86p.

"Order 표기법" 이라는 것은 규모(order)의 증가/감소의 유형을 주목하기 위해 도입된 것으로 O(□) 으로 표기합니다. "O"는 Order 의 "O"입니다. "Zero"가 아니므로 주의하세요. "□"에는 정수 혹은 수식이 들어갑니다. 

예1) 정수가 홀수인지 짝수인지 판단한다 - O(1)

예2) 순차검색 - O(n)

# "3 lon n"과 "n log n"은 왜 다를까? - 98∼99p.

→ O(log n)과 O(n log n)은 다르다.

문제의 규모, 즉 "n"이 커졌을 때 "log n"과 "(log n) + 3" 사이에 의미 있는 차이는 없습니다. 그러므로

O(log n) = O((log n)+3) 과 같이 됩니다. 

여기서 O(log n)과 O(3 log n)의 경우는 어떨까요?

3 log n = log (n³) 입니다.

"n"과 "n³"에는 큰 차이가 있습니다. "c=n"과 "c=n³"의 그래프(그림6)을 살펴본다면 일목요연하게 보입니다.

그림8. O(log n)과 O(n log n)의 그래프

"n log n"은 "log n" 과는 매우 다른 유형으로 빠르게 증가합니다. 문제의 규모에 대해 계산량의 증가 방식의 유형이 "n log n인데 매무 빠르게 증가한다"고 느껴질 경우에는 "n log n"의 유형으로 나타나지 않았는지 주의해야 합니다.

#4-2 Order 표기법을 충분히 활용하기 - 105p.

표1. 계산 규모의 증가 유형 (log = log₁₀)

문제의 규모	O(1)	O(log n)	O(n)	O(n log n)	O(n2)
1	1	0.1	1	0.1	1
10	1	1	10	10	100
100	1	2	100	200	10,000
1000	1	3	1,000	3,000	1,000,000

실제로 해결해야만 할 문제가 어느 정도의 규모인지에 따라 다르지만, 대체로 O(n log n) 유형을 넘어가기 시작하면 "계산량 폭발"에 주의가 필요합니다.

#부록. 알고리즘 서적을 읽어본다 - 158p.

A-1: 초급편 / 유키 히로시의 「프로그래머, 수학으로 생각하라」, 프리렉, 2014

A-2: 중급편 / G.T.Heineman의 「사전처럼 바로 찾아 쓰는 알고리즘」, 한빛미디어, 2008

A-3: 상급편 / D.E.Knuth의 「The Art of Computer Programming 1」, 한빛미디어, 2006

<가장 쉬운 알고리즘 책>

미와 요시코 지음, 김대희, 장재호 옮김

비제이퍼블릭, 2014

가장 쉬운 알고리즘 책 국내도서 저자 : 미와 요시코 / 김대희,장재호역 출판 : 비제이퍼블릭 2014.09.29 상세보기