2.4알고리즘

알고리즘에 관하여

18. 알고리즘과 초콜릿 케이크 레시피

알고리즘 : 결과를 정확하게 계산하도록 보장된 일련의 단계

각 단계는 기본 연산으로 표현, 연산의 의미는 완전히 명시
- 한치의 모호함도 있어선 안됨
- 입력 데이터가 어떤 유형이어야 하는지도 제공
- 모든 가능한 상황을 다루어야 하며, 다음에 무엇을 해야할지 모르는 상황이 발생하면 안 된다.
- 결국엔 멈춰야 한다.

반에서 가장 키 큰 사람 찾기, 평균 키 구하기 등을 구하려면 알고리즘적으로 대략 아래의 단계들이 필요하다.

하지만, edge case들이 있다 : 예를 들어 아무 사람이 없을때(N=0) 0으로 나누게 되는데 이 경우는 정의되지 않은 연산

⇒ 따라서, 위의 경우 합계를 계산며 항목의 개수도 세어야함

위의 예시에서 수행할 단계의 수, 또는 컴퓨터가 이 작업을 처리하는데 걸리는 시간은 데이터의 양에 정비례

⇒ 선형 시간(linear-time)이 걸리는 선형 알고리즘

⇒ 선형 알고리즘은 기본적으로 아래의 단계를 거침

전화번호부에서 사람 이름 찾기:

보통은 전화번호부 중간을 펼침
- 찾는 이름이 중간 페이지의 이름보다 앞에 있으면 뒷쪽 절반 무시, 앞쪽 절반에서 또 1/2 지점을 펼침
- 반복

⇒ 이와 같은 알고리즘을 이진 검색(binary search)이라고 함.

⇒ 이진 검색은 분할 정복(divide and conquer)이라는 전략의 한 예.

⇒ 작업의 양은 데이터의 양에 비해 천천히 증가(logarithm)

⇒ 정렬(sorting)은 또 다른 핵심적인 알고리즘 문제

⇒ N개의 항목이 있다면, 필요한 일의 양은 N + (N -1) + (N -2) + …. + 2 + 1 (= N * (N+1) /2)

수가 커질수록 N^2에 거의 비례. 이러한 증가율을 2차(quadratic)라고 함.
퀵 정렬(quicksort) : 토니 호어(Tony Hoare), 1959년.
- 먼저 쭉 훑고 절반 정도로 나눈 그룹을 모음
  - 또 절반 정도로 나눈 그룹들을 모음
  - 이렇게 반복하며 쪼개나가면 일의 양은 N * log N(여기서 log는 밑이 2)
  - 앞선 n^2과 비교하면 훨씬 작업량이 줄어드는 결과

지수(exponential) 알고리즘 : 2^N , 3^N 등 지수 비율로 복잡도가 증가
- Nondeterministic Polynomial(NP) 문제 : N^2, N^3 같은 어떤 변수의 정수 거듭제곱 꼴인 다항(Polynomial) 문제와 달리, 다항 시간 내에 해결할 수 없는 비결정적 다항 문제.
여행하는 외판원 문제(traveling salesman problem) : 다른 도시를 모두 방문하고 나서 출발점으로 돌아오는 외판원, 각 도시를 정확히 한 번씩 방문하고, 전체 여행한 거리를 최소로 만듦
- 최단 경로를 찾는 방법은 모든 가능한 경로를 시도해 보는 것밖에 없음
- 1971년, Stephen Cook : 이런 문제 중 다수가 서로 동등하다는 것 증명 ⇒ 어느 한 문제를 해결하는 다항 시간 알고리즘(N^2등)을 찾을 수 있다면, 이 모든 문제에 대한 다항 시간 알고리즘을 찾아낼 수 있음
- 밀레니엄 문제 중 하나는 P와 NP가 같은지 밝히는 것(난해 문제가 쉬운문제와 정말로 같은 부류인지 증명)

알고리즘은 ‘얼마나 빨리 계산할 수 있는가?’에 관한 문제

⇒ N, NlogN, N^2, logN과 같이 데이터의 양과 관련해서 실행 시간 표현

⇒ 어떤 문제의 본질적인 복잡도와 그 문제를 풀기 위한 알고리즘의 복잡도가 같을 필요는 없음

⇒ 어떤 문제가 계산 가능하고 어떤 것이 그렇지 않은지, 어떻게 하면 빨리 계산할 수 있는지, 메모리를 필요 이상으로 사용하지 않고 계산할 수 있는지, 처리 속도와 메모리 소비 간 균형을 유지하며 계산할 수 있는지