[이산수학] 알고리즘 선형탐색 이진탐색 정렬 알고리즘

알고리즘

컴퓨터 프로그래밍의 기초/ 기반입니다. 

 

알고리즘은 input, output, definiteness(명확성), correctness(정확성), finiteness(유한성), effectivenesS(효율성), generality(일반성) 등이 있습니다. 

 

결정성은 각 단계의 중간 결과는 유일하고 그리고 입력과 이전 단계의 결과에 의해서만 결정됩니다. 

 

의사코드 (3개의 수 중 최대의 수 찾기)

Algorithm to find the largest of three numbers a, b, c

Input : a, b, c

Output : large(the largest of a, b, and c)

 

procedure max3(a, b, c:integers)

{

large := a

if (b > large)

      large := b

if (c > large)

      large := c

    return large

}

 

탐색 알고리즘

정렬된 리스트에서 주어진 값을 찾아내는 검색을 수행하는 문제입니다.

 

따라서 n개의 요소에 대한 리스트 L이 주어졌을 때, 이 리스트는 어떠한 정의된 순서(오름차순 or 내림차순)으로 정렬되어 있다고 가정합니다. 이 리스트에서 특정 원소가 있는지 찾기 위해서 특정 원소를 제시를 합니다. 그러면 해당 원소 x가 리스트에 있는지 판단을 합니다.

 

따라서 x라는 원소가 리스트에 존재하면 존재하는 index를 출력하고 없다라는 값이 출력이 됩니다. 이 탐색 문제는 프로그래밍에서 상당히 많이 사용되는 알고리즘입니다. 

 

선형탐색

 

리스트의 첫 번째 원소부터 차례대로 검색하는 방법입니다. 

ex) Find 12 in {3, 6, 9, 12, 15, 18, 21, 24}

 

선형 탐색의 알고리즘은 다음과 같습니다.  찾고자 하는 정수가 x로 주어지고 list가 a1, a2. ... an 으로 n개의 원소를 가진 리스트가 주어집니다. 

 

list i := 1로 되고 계속 index를 증가시켜가면서 비교를 합니다. list i: = i + 1 이렇게 반든 다음 i <=n 이면 then location := i로 나오고 else 이면 location := 0 이 나오도록 합니다. 이 선형탐색은 정렬된 리스트 뿐만 아니라 정렬되지 않은 리스트에도 등장을 합니다. 

이진 탐색

 

가정 : 이진탐색은 오름차순으로 정렬된 항목들의 리스트

기본 아이디어 : 찾으려는 원소와 리스트의 중간에 위치한 항목과 비교해보면서 진행

 

-탐색은 찾으려는 원소와 중간 항을 비교하여 적절한 부분 리스트로 탐색을 제한함으로써 계속된다. 탐색 범위는 전체 리스트에서 계속 반복할 때마다 1/2 식 줄여가면서 탐색합니다. 예를 들어서 다음의 리스트에 18이라는 값이 있는지를 찾으려고 합니다. 

 

ex) Find 18 in {3, 6, 9, 12, 15, 18, 21, 24}

 

여기에서 중간의 위치의 값을 비교를 합니다. 계속해서 비교를 해나가는 것입니다. 중간 위치의 값이 찾을려고 하는 18과 비교했을 때, 큰지 작은지를 판단해서 찾으려는 값이 중간 위치의 값보다 크니깐 찾으려는 값은 이 리스트의 오른쪽에 존재를 할 것입니다.

 

따라서 다음 반복에서 찾으려는 것이 오른쪽의 절반으로 좁혀집니다. 따라서 해당 값은 왼쪽 부분에는 존재하지 않고 오른쪽 부분에 존재하니 오른쪽 부분에서 다시 중간 위치의 값을 index를 계산해서 비교를 합니다. 

 

따라서 여기서 오른쪽 부분의 중간 위치의 부분을 비교했을 때, 오른쪽 절반이냐, 왼쪽 절반인지 판단하면 왼쪽 절반으로 줄어들게 되고 이런 방식으로 검출을 하는 것입니다. 

 

정렬 알고리즘

정렬은 리스트의 원소들을 어떤 순서로 정리하는 것을 의미합니다. 어떤 데이터들을 순서대로 정렬하는 것은 상당히 중요한 문제가 됩니다.  

 

정렬 알고리즘은 중요한 역할을 합니다. 왜냐하면 상당한 비율의 계산 자원들이 다양한 종류의 리스트들을 정렬하는데 사용됩니다. 특히 특정 순서로 표현될 필요가 있는 대규모 정보 데이터베이스를 포함하는 어플리케이션에선 중요한 역할을 합니다.

 

상당히 많은 정렬 알고리즘들이 각기 다른 전략을 이용하여 새롭게 고안되어 소개되어 왔습니다. 15개 이상의 정렬 알고리즘이 존재하며 컴퓨터 과학의 기본 개념을 설명하는 데 유용하게 사용됩니다. 

 

Bubble sort

무작위 배열수의 거품 정렬의 예이며 Sort L = { 3 , 2, 4, 1, 5} 에서 어떻게 거품 정렬이 되는지 알아보겠습니다. 

삽입 정렬 알고리즘

두 번째 원소로부터 시작합니다. 이 두 번째 원소를 첫 번째 원소와 비교합니다.

 

다음으로 세 번째 원소는 첫 번째 원소, 두 번째 원소와 차례로 비교해서 정확한 위치에 삽입됩니다. 각 단계에서 n+1번째 원소가 처음 n+1개의 원소들과 비교하여 정확한 위치에 삽입됩니다. 

 

탐욕적 알고리즘

-최적화 알고리즘 : 모든 가능한 입력에 대해 어떤 파라미터를 최소화하거나 최대화하는 문제의 해를 찾는 것입니다. 

 

다양한 최적화 문제들이 존재합니다.

-두 도시 간의 가장 짧은 거리의 길을 찾는 것

-메세지를 가능한 적은 수의 비트를 사용하여 부호화하는 것

-최소량의 광섬유를 사용하여 네트워크 노드 간의 연결을 찾는 것 

 

최적화 알고리즘을 찾기가 어렵다?

-> 알고리즘의 각 단계에서 최선의 선택을 수행하는 greedy algorithm을 사용할 수 있다.

 

Greedy algorithm은 최적일 수도 있다. 최적임을 보이기 위해서는 증명이 필요하고, 최적이 아님을 보이기 위해서는 반례를 든다. 

 

예제

- 25, 10, 5, 1 센트의 동전이 있을 때, 동전의 수를 최소화하면서 67퍼센트의 거스름돈을 만들어라

아이디어

각 단계에서 지엽적으로 최선인 선택을 통해 n 센트의 거스름돈 계산 -> 즉 각 단계에서 n센트를 초과하지 않는 가능한 한 가장 큰 액면의 동전을 선택하여 거스름돈을 추가

 

정지문제

계산 복잡도 이론에서 정지문제는 판정 문제의 일종입니다. 정지 문제는 다음과 같은 프로시저가 있는가를 묻습니다. 이 문제의 입력은 컴퓨터 프로그램과 이 프로그램에 대한 입력입니다.