[Chapter 2] 쉽게 배우는 알고리즘[알고리즘 설계와 분석의 기초]

몇가지 기초 사항들

1. 알고리즘 분석의 필요성
   • 알고리즘을 설계하고나면 알고리즘이 자원을 얼마나 소모하는지 분석애햐 할 때가 많다. 자원이란 소요 시간이나 메모리, 통신대역 등이 될 수도 있지만 대부분은 소요 시간이 가장 중요한 관심 대상이 된다. 물론 다른 자원도 관심 대상이다. 
   • 메모리나 통신대역 등은 대부분 주어진 범위 내에서 문제가 되지 않지만 가끔 가장 중요한 대상이 되기도 한다.
   • 시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다.
   • 시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다.
   • ex) 디스크에 있는 3,000만 명의 고객 레코드를 한 시간 내에 생년월일 순으로 정렬하라는 요구를 받았을 떄, 사용하고자 하는 알고리즘의 소요 시간이 입력의 크기에 대해 어떤 비율로 비례하는지 안다면 주어진 시간에 요구하는 작업을 완료할 수 있을지 대략 짐작할 수 있다.
   • 입력의 크기가 n일 때, 최악의 경우에 n^2에 비례하는 시간을 소모하는 알고리즘도 있고, nlogn에 비례하는 알고리즘도 있다. 
   • 특수한 조건을 만족하는 경우에는 n에 비례하는 시간이 소요되기도 한다.
   • 같은 문제에서도 효율이 아주 큰 차이가 나는 다양한 알고리즘이 존재한다. 
2. 알고리즘의 수행 시간
   • 알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현한다. 무엇이 입력의 크기인지는 대부분 자명하다.
   • ex) 정렬의 경우 정렬하고자 하는 개체의 수가 입력의 크기가 된다. 도시 간의 최단 거리를 구하는 경우에는 계산에 관여도는 도시의 총수와 도시 간 간선(도로)의 총수가 입력의 크기가 된다. 계승을 구하는 경우에는 계승치를 구하고자 하는 자연수의 크기가 입력의 크기가 된다.

입력의 크기가 n인 경우에 간단한 연산으로 계산할 수 있는 알고리즘의 예시

sample1(A[], n)
{
	k=[n/2];
    return A[k];
}

이 알고리즘이 하는 일은[n/2]을 계산하는 것과 A[|A/2|]값을 리턴하는 일 밖에 없다. 입력 배열의 크기 n에 상관없이 일정한 시간(상수 시간)이 소요된다.

다른 알고리즘 예시

sample2(A[], n)
{
	sum<-0;
    for i <- 1 to n
    	sum <- sum+A[i];
    return sum;
}

배열A[1...n]의 모든 원소를 더하는 알고리즘이다. for 루프를 제외한 나머지 부분은 상수 시간이 소요되므로 for 루프가 시간을 지배한다. for 루프는 n번 반복되고 각 루프에서는 단순한 덧셈만 하므로 상수 시간이 소요되어 for 루프 관련 수행 시간은 n에 비례한다. 따라서 알고리즘의 수행 시간은 n에 비례한다.

for 루프 중첩 예시

sample3(A[], n)
{
	sum <-0;
    for i <- ito n
    	for j <-1 to n
        	sum <-sum+A[i]*A[j];
    return sum;
}

배열 A[1...n]의 모든 원소 쌍을 곱한 합을 구하는 알고리즘이다. for 루프가 총 n x n = n^2번 반복되고 각 루프에서는 덧셈 한번과 곱셈 한번, 즉 상수 시간 작업이 수행된다. 

비슷한 구조의 다른 알고리즘

sample4(A[], n)
{
	sum<-0;
    for i<-1 to n
    	for j <-1 to n{
        	k <- A[1...n]에서 임의로 [n/2]개를 뽑을 때 이들 중 최댓값;	//1
            sum <- sum + k;
        }
    return sum;
}

• for 루프를 n^2번 왕복하면서 매번 배열에서 반을 임의로 뽑아 그중 최댓값을 계속 더하는 알고리즘이다. 크기가 n인 배열에서 [n/2]개를 뽑으면서 이들 중 최댓값을 구하는 것은 n/2에 비례하는 시간이 든다.
• 이것은 n에 비례하는 시간이다. 즉, 1을 수행하는데 n에 비례하는 시간이 드다. 전체적으로 for 루프의 반복 횟수와 1의 수행 시간이 시간을 좌우하므로 총 수행 시간은 n^2 x n = n^3에 비례한다.

중첩된 구조이지만 반복 횟수가 매번 변하는 예시

sample5(A[], n)
{
	sum <- 0;
    for(i <-1 to n-1)
    	for(j<-i+1 to n)
        	sum <- sum + A[i] * A[j];	//1
    return sum;
}

• 배열 A[1...n]에서 i < j인 모든 원소 쌍의 곱을 환산하는 알고리즘이다. 두 개의 for 루프가 중첩된 구조다. for 루프의 가장 안쪽에 있는 1은 상수 시간이 드는 간단한 작업이다. 따라서 for(루프의 총 반복 횟수가 수행 시간을 좌우한다. 
• 바깥 for 루프에서 i=1일 때 안쪽 for 루프가 n-1 반복되고 바깥 for 루프에서 i=2일 때 안쪽 for 루프가 n-2회 반복되고, ..., 마지막으로 바깥 for 루프에서 i = n-1일 때 안쪽 for 루프가 1회 반복된다. 
• for 루프의 총 반복 횟수는 이 되어 n^2에 비례한다. 알고리즘의 총 수행 시간은 n^2에 비례한다.

자기호출이 발생하는 알고리즘은 조금 다르다.

factorial(n)
{
	if(n=1) return 1;
    return n * factorial(n-1);	//1
}

• 자기호출 알고리즘으로, 앞의 예시처럼 단순 산술로는 되지 않는다. 우선 1에서 재귀적으로 계속 호출되는 상황을 고려하지 않으면 알고리즘은 단순한 상수 시간이 소요된다.
• 이 경우 함수 factorial()이 총 몇 번 호출되는지가 시간을 좌우한다.
• factorial(n)이가 factorial(1)을 호출한다. factorial(1)은 1에 이르지 못하고 첫 행에서 끝나버린다. factorial()의 총 호출 횟수는 n이다. 그러므로 알고리즘의 총 수행 시간은 n에 비례한다.
• 이것은 가장 유명하고 단순한 자기 호출의 예시이며, 자기 호출 구조가 좀 복잡해지면 알고리즘의 수행 시간 분석도 복잡해진다. 

재귀(자기호출)와 귀납적 사고

• 자기 호출은 컴퓨터 과학 이론의 근간을 이루는 중요한 개념이다.
• 자기 호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다.
• 고등학교 수학에서 배우는 귀납법이 이와 관련이 깊다. 수열의 점화식도 이의 기초적인 형태다.
• 귀납적 사고라는 것은 성격이 같지만 크기가 다른 문제간의 "관계"를 파악하는 것이다.
• 대부분의 프로그래밍 언어는 함수의 내부에서 자신을 호출하는 자기호출 기능을 제공한다. 
• 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다.
• 자기 호출 개념이 가장 대표적으로 사용하는 부분은 정렬이다. 여러가지 정렬중 병합 벙렬과 퀵 정렬은 자식 호출이 명시적응로 사용되는 예시이며, 힙 정렬도 자기 호출이 일부 사용된다. 
• 일반적으로 자기 호출과 별 관계 없이  생각하는 선택 정렬, 버블 정렬, 삽입 정렬도 재귀적 관점에서 보면 이해하기 쉽다.

 

• 자기 호출을 이용하는 알고리즘의 정당성은 수학적 귀납법과 관련이 깊다. 수학적 귀납법이란 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것이다.
• 재귀 알고리즘이 자신보다 작은 문제를 자기 호출하는 것은 수학적 귀납법에서 자신보다 작은 문제에 대해 결론이 옳음을 가정하는 것과 일치한다.
• 즉, 자신보다 작은 문제에서는 이 알고리즘이 제대로 작동한다고 가정하는 것이다.
• 자기 호출을 이용하는 알고리즘에서 자기호출을 제외한 나머지 부분은 대부분 크기가 다른 문제간의 관계를 반영하는 것이다.

병합 정렬 알고리즘

mergeSort(A[], p, r)	//A[P...r]을 정렬한다.
{
	if(p<r) then{
    q <-l(p+r)/2];	//1 p, r의 중간 지점 계산
    mergeSort(A, p, q);	//2 전반부 정렬
    mergeSort(A, q+1, r);	//3 후반부 정렬
    merge(A, p, q, r);	//4 병합
    }
}

merge(A[], p, q, r)
{
	정렬되어 있는 두 배열A[p...q]와 A[q+1...r]을 합쳐
    정렬된 하나의 배열 A[p...r]을 만든다.
}

배열 A[p...r]에 있는 수를 정렬하는 알고리즘이다.

• 1에서 정렬하고자 하는 배열의 중간 지점을 계산해 전체 배열을 이등분한다.
• 2, 3에서 이등분된 두 배열을 각각 재귀적으로 정렬한다. 
• 4에서 정렬된 두 배열을 합쳐서 하나의 정렬된 배열을 만든다. 
• 정리하면 2, 3은 자기호출에 해당하며, 1, 4는 크기가 n인 배열과 이를 이등분한 배열 간의 관계를 반영하는 것이다.

알고리즘으로 어떤 문제를 푸는가

예시

• 자동차에서 사용하는 내비게이션에서 가장 중요한 기능은 두 지점 간의 최단 경로나 최단 시간이 걸리는 경로를 찾는 것이다 이것은 최단경로 알고리즘을 기보혀응로 한다. 최단 경로 알고리즘은 가장 기본적인 알고리즘이지만 제약사항을 추가해 변형해야 하므로 어설프게 설계하면 개발하기 쉽지 않다. 게다가 각 도로의 교통상황을 실시간으로 제공하려면 더욱 복잡한 최단 경로 알고리즘이 필요하다.
• ATM(현금 자동 입출기)은 은행 뿐만 아니라 편의점이나 지하철역에도 설치되어있다. 다양한 주체들이 ATM을 상업적으로 운용하고 있는데, 어떤 회사는 200억의 자금으로 2,000여 대의 ATM을 운용한다. 고객이 ATM에서 돈을 찾으려는데 기계 안에 돈이 하나도 없다면 수수료 수입이 줄어들 뿐 아니라 이런 일이 잦으면 회사의 평판도 떨어진다. 또 기계에 돈이 필요 이상으로 많이 남아 있는 것도 자금 운용 효율을 떨어뜨린다. 한 기계에 돈을 채워 넣기 위해 인력이 한번 방문하면 5만원 정도의 인건비가 든다. 어떤 날에 어떤 기계에 돈을 얼마나 채워 넣을 것이며, 어떤 순서로 이 기계들을 방문할 것인가? 여기에도 스케줄링을 비롯한 알고리즘으로 해결해야 할 문제들이 포함되어 있다.
• 인간 지놈 프로젝트의 1차적 완성을 비롯해 생물학계의 연구 결과로 방대한 DNA 데이터가 누적되었다. 이들에 존재하는 관계를 파악하는 일이 알고리즘 설계자들에게 새로운 영역을 제공했다. 여러가지 짖놈 서열 간의 유사성을 파악하는 알고리즘 여러 생물의 DNA에서 최적의 진화 계통도 만들어내는 알고리즘 등 실로 다양한 요구가 존재한다.
• 인터넷에는 수조 페이지 이상의 데이터가 존재한다. 이들 중에서 원하는 검색의 결과를 최대한 빨리, 최대한 만족스럽게 제공하는 것은 고난도의 알고리즘을 요구한다. 이것은 또한 효율적인 자료구조도 같이 요구하는 좋은 알고리즘 응용 문제이다. 역사가 아주 오래된 "검색"이 인터넷 데이터의 폭발적 증가와 함께 다시 핫이슈가 되었다.
• 고객이 1,000만 명 이상인 신용카드 회사에서는 신용카드 사용 내역을 매달 우편이나 이메일로 고객들에게 통보한다. 이런 작업들은 순차적으로 진행하므로 모든 고객을 어떤 순서로 처리할지 결정해야 한다. 그리고 어떤 식이든 고객들이 정렬되어야 한다.
• 물건 하나를 만드는 공정은 여러 작업으로 구성된다. 작업 간에는 선후 관계가 존재하기도 하고 그렇지 않기도 하다. 여러 가지 선후 관계를 만족시키면서 한 사람이 공정을 담당하려면 각 직업을 어떤 순서로 하면 될까? 대부분의 알고리즘 책에서 배우는 위상 정렬을 이용하면 간단히 해결할 수 있는 문제다.
• 신도시를 설계할 때 가스 파이프나 수도관은 어떻게 배치하는 것이 가장 효율적일까? 최소 신장 트리 등 여러 알고리즘이 개입할 여지가 많은 주제이다.
• 하나의 반도체 칩에는 수천수만 개의 게이트가 존재할 수 있다. 이러한 방대한 칩의 설계는 수동으로는 불가능하다. 게이트의 배치와 게이트 간의 논리적 연결 구조를 설계 프로그램이 자동으로 결정한다. 또 각 게이트에 가능하면 시차가 없도록 클록을 공급하는 것도 중요하다. 복잡하고 다양한 알고리즘을 요구한다.

---

Reference

쉽게 배우는 알고리즘