이산수학 | 알고리즘 (Algorithms)

알고리즘

정의 : 계산을 수행하거나 문제를 해결하기 위한 정확한 지침의 유한한 집합

예시

정수의 유한한 수열에서 최대값을 얻는 알고리즘을 찾기

1. 임시 최댓값을 수열의 첫 번째 정수와 동일하게 설정한다
2. 수열의 다음 정수를 임시 최대값과 비교해 더 크다면 그 정수를 임시 최대값로 설정한다
3. 정수가 더 많으면 이전 단계를 반복한다
4. 알고리즘이 종료되면 임시 최대값은 수열에서 가장 큰 정수가 된다

의사 코드로 나타내면 다음과 같다

# procedure max(a[1], a[2], a[3] ..., a[n] : intergers)
max := a[1]
for i:=2 to n
    if max < a[i] then max := a[i]
return max

알고리즘의 속성

• 입력 : 알고리즘은 입력을 가진다
• 출력 : 알고리즘은 출력을 가진다
• 정확성 : 알고리즘은 항상 옳은 출력을 생성해야 한다
• 유한성 : 알고리즘은 유한한 단계 후 출력을 생성해야 한다
• 효율성 : 알고리즘은 한정된 시간 내 정확하게 수행할 수 있어야 한다
• 일반성 : 알고리즘은 원하는 형태의 모든 문제에 대해 작동해야 한다

알고리즘 문제의 예시

탐색 문제

탐색 문제는 고유한 원소 목록 $a_1$, $a_2$, $…$, $a_n$ 에서 원소 $x$를 찾거나 있는지 확인하는 것이다

예시

1. 선형 탐색

선형 알고리즘은 처음부터 시작해 수열의 요소를 한번에 하나씩 검사해 목록에서 항목을 찾는다.

1. 이진 탐색

정렬 문제

정렬 문제는 오름차순 또는 내림차순으로 리스트를 만드는 것이다

예시

1. 버블 정렬 (Bubble Sort)

• 리스트를 여러번 순회하며 다른 정렬되지 않은 인접한 쌍을 교환하는 방법으로 작동한다
• 액체의 기포가 올라가는 것처럼 보이기에 버블 정렬이라 부른다

1. 삽입 정렬 (Insertion Sort)

• 두번째 요소 부터 시작한다
• 이전 요소들과 비교하여 ‘적절한’ 위치로 요소를 이동한다
• 마지막 요소까지 반복한다

탐욕 알고리즘 (Greedy Alorithm)

선택의 순간마다 최적의 상황을 쫓아 답을 도출하는 방법이다

예시 1 : 센트 분배

25센트, 10센트, 5센트, 1센트를 사용해 n센트의 거스름돈을 가장 적은 동전으로 만드는 방법을 greedy algorithm을 설명하라

각 단계마다 남은 잔돈을 초과하지 않는 가장 큰 값을 가진 동전을 선택한다

예시 2 : 일정 짜기

시작시간과 종료시간이 명시된 회의가 있다. 다음과 같은 가정 하에서 강의실에서 최대한 많은 일정을 예약하는 greed-algorithm을 구축하라

• 둘 이상 겹칠 수 없다
• 회의가 끝나는 동시에 다른 회의가 시작 할 수 있다
• 회의 중 겹치는 다른 회의를 시작할 수 있다

해결

• 가장 짧은 시간을 고르는 것은 답이 될 수 없다
• 가장 빨리 끝나느 순서대로 고르는 방법

Halting Problem

입력과 함께 컴퓨터 프로그램을 입력으로 받아들이고 프로그램이 결국 중지되는지 여부를 확인하는 절차를 개발할 수 있나?