[알고리즘 분석] 01 - 1 알고리즘: 효율, 분석 그리고 차수

알고리즘에서 효율, 분석 그리고 차수

알고리즘을 만들어 얼마만큼의 효율성이 있는지 더불어 그것을 분석하여 얼마만큼 빨리 문제를 해결할 수 있는지 알아야합니다. 그리고 분석을 위한 척도로 차수를 정의합니다.

 

알고리즘 단어의 기원

페르시아의 수학자이자 천문학자, 지리학자인 알코와리즘(780-850)의 이름을 따와 알고리즘이라는 단어가 탄생했습니다.

 

알고리즘 사용 예시

ex1. 24와 16에 대해 최대공약수, 최소공배수 구하기

이러한 절차를 어떻게 표현할지를 알고리즘 분석을 통해 배우게 됩니다.

 

ex2. a에서 b로 가는 최단거리?

어떻게 최단거리를 찾을 것인지?

 

ex3. 화랑 문제

박물관에서 모든 공간을 감시하기 위한 최소 인원 배치는?

ex4. 선분교차문제

컴퓨터 그래픽에서 평면 또는 3차원 공간상의 두 선분이 교차하는지 확인하는 방법

ex5. 미로 탐색 문제

위와 같은 문제들을 해결하는 다양한 알고리즘들이 존재합니다.

 

알고리즘(algorithm)의 정의

• 문제를 해결할 수 있는 잘 정의된/분명하게 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(procedure), 간단히 말해 입력을 받아서 출력으로 전환시켜주는 일련의 계산절차를 의미합니다.
• 계산과 데이터 처리에 사용되는 일련의 명령
• 작업을 수행하기 위해 만들어진 잘 정의된 명령들이 주어진 초기 상태에서 출발하여 잘 정의된 이후의 가태들로 변화하면서 종료사태로 되는 효과적인 방법
• 하나의 상태에서 다음 상태로 바뀌는 것이 반드시 결정적이어야 하는 것은 아니다. 이는 확률적 알고리즘(하나 이상의 경우로 뻗어 나가는 경우)과 같은 알고리즘은 무작위성을 포함한다는 의미입니다.

*알고리즘은 프로그램의 엔진에 해당하는 중요한 절차입니다. 이러한 알고리즘을 잘 만들어 줘야 효율적인 프로그램을 만들 수 있습니다.

 

*홀로그램, 빅데이터(GPS, 신용정보 관련 정보수집)와 같은 곳에서도 알고리즘은 필수적으로 사용됩니다. 추가로 자율주행 자동차 시스템을 만든다고 했을 때 자동차의 위치와 주변 건물, 도로와 같은 정보들을 다루는 소프트웨어 개발에는 알고리즘이 존재합니다.(ex. 알파고와 같은 인공지능에서 가장 핵심은 알고리즘의 탐색에 근거합니다.)

 

학습목표

• 설계(Design) - 알고리즘 설계 기법 학습
• 분석(Analysis) - 알고리즘 분석과 시간/공간 복잡도 도출 방법 학습
• 계산복잡도(Computational Complexity) - 문제 분석과 계산적 복잡도 도출 방법 학습
• 응용력(Application Capability) - 새로운 문제를 분석하여 효과적인 알고리즘 개발 능력 배양

 

알고리즘과 Method의 차이

Algorithm - 유한시간 내에 종료되는 것이 밝혀진 방법

Method - 유한시간 내에 종료하는 것을 밝혀지지 않은 방법

 

문제 표기 방법

• 문제 - 답을 찾고자 주어진 질문
• 파라미터(parabeter) - 문제에서 특정값이 주어지지 않은 변수(매개변수)
• 문제 사례(instance, 입력) - 파라미터에 특정 값을 지정한 것
• 사례에 대한 해답(solution, 출력) - 주어진 사례에 관한 질문에 대한 답

ex. 정렬

문제 : n개의 수로 구성된 리스트 S를 비내림차순(nondecreaing order)으로 정렬(sort)하라.

파라미터 : S,n

사례

- 입력의 예: S = [10,7,11,5,13,8], n = 6

- 출력의 예: S = [5,7,8,10,11,13]

 

알고리즘의 표기

• 자연어 - 한글 또는 영어 표기 / 해석의 다양성 존재(해석에 어려움이 있음)
• 프로그래밍언어 - C, C++, Java와 같은 언어 표기 / 알고리즘을 이해하는데 어려움
• 의사코드(pseudo-code) - 실제와 비슷, 프로그래밍언어는 아니지만 거의 실제 프로그럄에 가깝게 계산과정을 표현할 수 있는 언어

*알고리즘은 보통 의사코드로 표현

 

배열(array) - 공통의 성질을 갖는 변수가 여러 개 일 때 하나의 변수명을 정하고, 위치를 나타내는 인덱스를 이용해서 변수를 나타내는 자교구조

 

흐름도

*흐름도로 알고리즘을 표현시 전체적인 개요를 쉽게 파악할 수 있습니다.

ex. 최대값 찾기 흐름도

 

C++와 의사코드의 차이점

• 배열 인덱스의 범위에 제한없음(C++는 반드시 0부터 시작, 의사코드는 임의의 값 사용가능)
• 프로시저의 파라미터에 2차원 배열 크기의 가변성 허용(ex. void pname(A[][]){...}
• 지역배열에 변수인덱스 허용(ex. keytype S[low..high];
• 수학적 표현식 허용(ex. low <= x && x<== high -> low<=x<=high)
• C++에 없는 타입 사용가능(ex. index, number)
• 제어 구조(repeat)
• 프로시저와 함수(프로시저: void, 함수: return존재)
• 참조파라미터를 사용하여 프로시저의 결과값 전달(배열 - 참조 파라미터로 전달, 기타 - 데이터타입 이름 뒤에 &를 붙임, const 배열 - 전달되는 배열의 값이 불변)

의사코드(pseudo-code)와 알고리즘 구현

순차검색 알고리즘(sequential search, 데이터를 처음부터 순차적으로 검색)

• 문제:크기가 n인 배열 S에 x가 있는가?
• 입력(파라미터): 양수n, 배열[1..n], 키x
• 출력: x가 S의 어디에 있는지의 위치. 만약 없으면 0.
• 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사합니다. 만일 x와 같은 아이템을 찾으면 S에서 위치를 리턴하고, S를 모두 검사하고도 찾지 못하면 0을 리턴합니다.

ex. 순차검색 알고리즘 예시

프로그래밍언어 예시

결론

순차 검색 알고리즘에서 키를 찾기 위해 시행되는 검색의 횟수는 키와 같은 항목의 위치에 따라 다르고 최악의 경우 n번을 갖습니다. -> S에 있는 항목에 대한 정보가 없는 한 더 빨리 찾을 수 없습니다.

 

배열의 수 더하기

문제: n개의 수로 된 배열 S에 있는 모든 수를 더하라

입력: 양의 정수 n, 수의 배열 S(첨자는 1부터 n)

출력: S에 있는 수의 합, sum

교환정렬

문제: 비내림차순(nondecreasing order)으로 n개의 키를 정렬하라

입력: 양의 정수 n, 키의 배열 S(첨자는 1부터 n)

출력: 키가 비내림차순으로 정렬된 배열 S

*출력: 키가 비내림차순으로 정렬된 배열 S

 

행렬곱셈

문제: 두 개의 n × n 행렬의 곱을 구하기

입력: 양의 정수 n, 수의 2차원 배열 A와 B. 여기서 이 행렬의 행과 열은 모두 1부터 n까지의 첨자를 갖습니다.

출력: A와 B의 곱이 되는 수의 2차원 배열 C. 이 행렬의 행과 열은 모두 1부터 n까지의 첨자를 갖습니다.

시간복잡도 O(N^3)을 가집니다.

 

이분검색 알고리즘(binary search)

문제: 크기가 n인 정렬된 배열 S에 x가 있는가?

입력: 양수 n, 배열 S[1..n], 키 x

출력: x가 S의 어디에 있는지의 위치. 만약 없으면, 0.

*분할정복 방법(큰 문제를 작은 문제로 나누어 풀어가는 것)을 사용합니다.

이러한 경우  최악의 경우에도 log(n) + 1만 검사하면 됩니다.

 

*순차검색은 데이터의 정렬 여부가 상관없는 반면 이분 검색은 데이터가 정렬되어 있어야합니다.

 

n번째 피보나치 수 구하기

피보나치 수 구하기(재귀적 방법)

문제: n번째 피보나찌 수를 구하라.

입력: 양수 n

출력: n 번째 피보나찌 수

알고리즘

단점 - 재귀 알고리즘은 속도가 매우 느립니다.

이유 - 같은 피보나치 수를 중복해서 계산하기 때문입니다.

fib(5)를 계산할 때 fib(2)가 여러 번 중복되어 계산됩니다. -> 총 25(15 + 9 + 1)번의 계산이 발생합니다.

 

fib(n)의 함수 호출 횟수 계산

*n이 홀수일 때도 증명이 가능, 트리의 가지수가 매우 많아집니다.

 

수학적 귀납법 (mathematical induction)

1. 귀납출발점 (basis, base case): n = 0(또는 1) 일 때 주장이 사실임을 보임.
2. 귀납가정 (induction(inductive) hypothesis): 어떤 n에 대해서 주장이 사실 임을 가정
3. 귀납절차(inductive step): n+1에 대해서 주장이 사실임을 보임

수학적 귀납법 사용 예시

계산한 호출 횟수의 검증

피보나찌 수 구하기 알고리즘 (반복적 방법)

• 반복 알고리즘은 수행속도가 훨씬 더 빠르다. (이유: 중복 계산이 없음)
• 계산하는 항의 총 개수 (T(n) = n + 1. 즉, f[0]부터 f[n]까지 한번씩 만 계산)

 

두 피보나치 알고리즘의 비교

* 알고리즘 문제를 해결할 때 작은 단위의 문제를 우선 해결하고 큰 단위의 문제까지 해결해봐야 알고리즘의 효율성을 정확하기 파악할 수 있습니다.

 

정렬 알고리즘의 차이 예시

*수 많은 트렌젝션을 받을 경우에는 엄청난 차이를 보이는 것을 알 수 있습니다.

알고리즘을 사용할 때 반드시 알고리즘의 효율성, 복잡도를 따져보면서 사용해야합니다.

 

정리

재귀법

• 분할정복방법(divide-and-conquer)
• 어떤 문제에서는 매우 효율적
• 피보나치 문제에서는 비효율적

반복법

• 동적계획법(dynamic programming)

 

*문제에 따라 효율족인 방법이 다를 수 있음을 명심해야합니다.