12. 알고리즘을 통한 문제해결

알고리즘(algorithm)

: 주어진 문제를 해결하기 위해 필요한 여러 가지 단계들을 체계적으로 명시해놓은 것

1) 입력(input) : 문제를 풀기 위한 입력이 있어야함

2) 출력(output) : 문제를 해결했을때 답이 나와야함

3) 유한성(finiteness) : 유한번의 명령이 수행된 후에는 끝나야함

4) 정확성(correctness) : 주어진 문제를 정확하게 해결해야함

5) 확정성(definiteness) : 각 단계가 실행된 후에는 결과가 확정됨

6) 일반성(generality) : 같은 유형의 문제에 모두 적용됨

7) 효율성(effectiveness) : 정확하면서도 효율적이어야함

 

유사코드(pseudo code) : 알고리즘을 프로그래밍 언어와 유사한 형태로 풀어써놓은 것

 

순서도(flow chart) : 처리하고자 하는 문제를 분석한 후 처리 순서를 단계화하고 상호간의 관계를 표준 기호를 사용하여 입력, 처리, 결정, 출력 등의 박스와 연결선으로 일목요연하게 나타낸 도표(diagram)

 

알고리즘에 대한 평가와 비교

1) 문제의 해결에 있어서 주어진 알고리즘을 사용하는데 드는 비용이 얼마인가?

2) 문제를 해결하는데 비용이 가장 적게 드는 알고리즘은 무엇인가?

** 비용 : 연산하는데 필요한 시간과 기억장소의 크기

 

효율성을 분석하기위해서는 시간 복잡성(time complexity)과 공간 복잡성(space complexity)의 두가지 요소를 검토

일반적으로 알고지름을 분석할때 입력의 개수를 n으로 생각하고 효율성을 그에 대한 함수로 나타낸다

 

** 대부분 문제를 해결하는데 필요한 기억장소의 크기보다는 알고리즘의 수행시간에 큰 비중을 둔다

 

알고리즘의 복잡성

알고리즘의 복잡성을 측정하는데 있어서 일반적으로 빅오(Big-Oh) 표현을 사용하며, 대문자 O를 써서 표시한다

ex) f(n) = O(n) 으로 표시가 되었다면 f(n)의 차수가 n이라고 하며 'Big-Oh of n'이라고 읽는다

 

재귀함수(Recursive function)

주어진 문제를 해결하는데 있어서 f(n)이 필요한 함수라고 했을 때, f(n)의 식에 f(n-1)... 함수 중 하나 이상이 포함되는 함수

재귀함수에서 현재의 함수 값은 항상 그 전에 있던 함수에 의해 영향을 받는다

 

탐색 알고리즘

탐색 : 주어진 파일 또는 원소들 중에서 어떤 특정한 원소를 찾는것

1) 순차 탐색(sequential search) : 원소들이 정렬되어 있지 않을 경우에 원소들을 처음부터 비교하여 찾는것

2) 이진 탐색(binary search) : 원소들이 정렬되어 있을 경우에 찾는 방법으로서 순차 탐색보다 빠르다

 

1. O(n) 알고리즘

- 순차 탐색은 배열에 있는 특정한 원소를 찾기 위해 배열의 처음 원소부터 차례로 모든 원소들을 비교하여 탐색

- 효율x 효과o

- 모든 원소들을 조사하는 탐색을 선형 탐색(linear search)이라고 한다

 

2. O(log2n) 알고리즘

원소들이 순서대로 정렬되어 있을때는 처음부터 찾을 필요없이 중간의 원소와 비교하여 그보다 작을때에는 그 원소의 왼쪽 원소들 중에서, 클 때는 오른쪽 원소 중에서 다시 같은 형식으로 찾으면 시간 절약

 

3. 분할 정복 알고리즘(Divide and conquer algorithm)

: 전체 집합을 찾으려는 원소와 비교하여 부분집합으로 나누어 찾는 알고리즘

-> 큰 문제를 작은 문제로 나누어서 해결

 

이진 탐색 알고리즘의 수행 시간은 O(log2n)

 

정렬 알고리즘

: 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 또는 큰 순서부터 늘어놓는것

 

O(n2) 알고리즘

버블정렬(bubble sort)과 삽입정렬(insertion sort) 두가지가 있다

1) 버블 정렬

이웃한 두개의 원소를 비교하여 순서가 서로 다르면 원소의 자리를 서로 바꾸고, 그렇지 않으면 그 위치에 그대로 놓음

 

O(nlog2n) 알고리즘

퀵정렬, 병합정렬, 힙 정렬 등

1) 퀵 정렬(quick sort)

- 모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법

- 현재 정렬 과정에서 처리되고 있는 피벗 키(pivot key) p를 기준으로 원소를 두 부분으로 나눔

- 나누어진 두 부분을 따로 다시 퀵 정렬로 재귀함으로써 원소가 순서대로 정렬될 때까지 실행

 

2) 병합 정렬(merge sort)

- 크기가 1인 정렬된 두 파일을 병합하여 크기가 2인 파일들을 생성 -> 반복하여 한개의 파일 만들기

 

3) 힙 정렬(heap sort)

- 자료를 정리할때 모든 자료들을 동시에 처리하지 않고 모든 자료 중에서 가장 큰 자료를 찾아 출력

- 나머지 자료 중에서 앞의 과정을 반복하여 가장 큰 자료(실제로는 두번째 큰 자료)를 찾아 출력시키면서 정렬