알고리즘 3주차

알고리즘의 일반적 특성

정확성
– 알고리즘은 주어진 입력에 대해 올바른 해를 주어야(랜덤 알고리즘은 예외)
수행성
– 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야
유한성
– 알고리즘은 유한 시간 내에 종료되어야
효율성
– 알고리즘은 효율적일수록 그 가치가 높아진다.

최초의 알고리즘

유클리드(Euclid)의 최대공약수 알고리즘

기원전 300년경에 만들어진 가장 오래된 알고리즘
최대공약수란 2개의 자연수의 공약수들 중에서 가장 큰 수 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀수와 작은 수와의 최대공약수와 같다.

최대공약수(24, 14)
= 최대공약수(24-14, 14) = 최대공약수(10, 14)
= 최대공약수(14-10, 10) = 최대공약수(4, 10)
= 최대공약수(10-4, 4) = 최대공약수(6, 4)
= 최대공약수(6-4, 4) = 최대공약수(2, 4)
= 최대공약수(4-2, 2) = 최대공약수(2, 2)
= 최대공약수(2-2, 2) = 최대공약수(0, 2)
= 2
유클리드의 최대공약수 알고리즘에서 뺄셈 대신에 나눗셈을 사용하면 빠르게 해를 찾는다.

import java.util.Scanner;
public class GCD {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("첫 번째 정수를 입력하세요: ");
        int a = scanner.nextInt();
        System.out.print("두 번째 정수를 입력하세요: ");
        int b = scanner.nextInt();
        int result = gcd(a, b);
        System.out.printf("%d와 %d의 최대공약수는 %d입니다.", a, b, result);
    }
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

이 코드는 두 개의 정수 a와 b를 인수로 받아 최대공약수를 구합니다. 만약 b가 0이라면 a가 최대공약수가 되며, 그렇지 않은 경우에는 b와 a % b의 최대공약수를 구하는 재귀호출을 한다. 이 알고리즘은 재귀호출을 반복하면서 b가 0이 될 때까지 나머지 연산을 수행합니다. 최종적으로 나온 결과값이 두 수의 최대공약수가 된다.

알고리즘의 표현 방법

알고리즘의 형태는 단계별 절차이므로, 마치요리책의 요리를 만드는 절차와 유사
알고리즘의 각 단계는 보통 말로 서술할 수 있으며,컴퓨터 프로그래밍 언어로만 표현할 필요는 없음
일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드(pseudo code)로 표현

최대 숫자 찾기 문제를 위한 알고리즘

최대 숫자 찾기

카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 찾는다.
마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다

보통의 말로 표현된 알고리즘

첫 카드의 숫자를 읽고 머릿속에 기억해 둔다.
다음 카드의 숫자를 읽고, 그 숫자를 머릿속의 숫자와 비교한다.
비교 후 큰 숫자를 머릿속에 기억해 둔다.
다음에 읽을 카드가 남아있으면 line 2로 간다.
머릿속에 기억된 숫자가 최대 숫자이다.

의사 코드로 표현된 알고리즘 배열 A에 10개의 숫자가 있다면

max = A[0]
for i = 1 to 9
if (A[i] > max) max = A[i]

return max

public static int findMax(int[] arr) {
 int max = arr[0];
 for (int i = 1; i < arr.length; i++) {
     if (arr[i] > max) {
         max = arr[i];
     }
 }
 return max;
}

이 코드는 arr 배열에서 가장 큰 값을 찾아 리턴합니다. 먼저 max 변수를 배열의 첫 번째 값으로 초기화하고, 배열의 두 번째 값부터 끝까지 반복문을 돌면서 max보다 큰 값을 찾으면 max를 해당 값으로 대체합니다. 반복문이 끝난 후 max를 리턴합니다. 이렇게 하면 배열에서 가장 큰 값을 찾을 수 있습니다.

알고리즘의 분류

문제의 해결 방식에 따른 분류

분할 정복(Divide-and-Conquer) 알고리즘
그리디(Greedy) 알고리즘
동적 계획(Dynamic Programming) 알고리즘
근사(Approximation) 알고리즘
백트래킹(Backtracking) 알고리즘
분기 한정(Branch-and-Bound) 알고리즘

문제에 기반한 분류

정렬 알고리즘
그래프 알고리즘
기하 알고리즘

특정 환경에 따른 분류

병렬 알고리즘
분산 알고리즘
양자 알고리즘

알고리즘의 효율성

알고리즘의 효율성

알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 크기로 나타낼 수 있다.
시간 복잡도(time complexity), 공간 복잡도(space complexity)
일반적으로 알고리즘들을 비교할 때에는 시간 복잡도가 주로 사용됨

시간 복잡도

시간 복잡도는 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다

기본 연산(Elementary Operation)이란 데이터 간 크기비교, 데이터 읽기, 갱신, 숫자 계산 등과 같은 단순한 연산을 의미

[예] 10장의 숫자 카드들 중에서 최대 숫자 찾기 – 순차 탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 총 비교 횟수는 9번
– n장의 카드가 있다면, (n-1)번의 비교 수행으로 시간 복잡도는 (n-1)

알고리즘의 복잡도 표현 방법

최악 경우 분석(Worst-case Analysis)

‘어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다‘라는 상한(Upper Bound)의 의미
평균 경우 분석(Average-case Analysis)
입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등 분포(Uniform Distribution)를 가정
최선 경우 분석(Best-case Analysis)
가장 빠른 수행 시간을 분석하며, 최적(Optimal) 알고리즘을 찾는데 활용
상각 분석
일련의 연산을 수행하여 총 수행 시간을 합하고 이를 연산 횟수로 나누어 수행 시간을 분석
[조건] 알고리즘에서 적어도 두 종류의 연산이수행되고, 그 중 하나는 수행 시간이 길고, 다른 하나는 짧으며, 수행 시간이 짧은 연산은 많이 수행되고 수행시간이 긴 연산은 적게 수행되어야 상각 분석이 의미를 갖는다.
amortize는 ‘분할 상환하다’라는 뜻을 가짐. 그리고 상각(償却)은 ‘보상하여 갚아주다’라는 뜻 일반적으로 알고리즘의 수행 시간은 최악 경우 분석으로 표현

등교 시간 분석

집에서 지하철역까지 6분, 지하철을 타면 학교까지 20분, 강의실까지 걸어서 10분 걸린다.
최선 경우
– 집을 나와서 6분 후 지하철역에 도착하고, 운이 좋게 바로 열차를 탄 경우를 의미 – 최선 경우 시간은 6 + 20 + 10 = 36분
최악 경우
– 열차에 승차하려는 순간, 열차의 문이 닫혀서 다음열차를 기다려야 하고 다음 열차가 4분 후에 도착한다면,
최악 경우는 6 + 4 + 20 + 10 = 40분 평균 경우
– 대략 최악과 최선의 중간이라고 가정했을 때, 38분
상각 분석
– 단순히 1회의 등교 시간을 분석하는 것이 아니라, 예를 들어, 한 학기 동안의 등교 시간을 분석해본다는 점에서 그 의미를 가짐
– 한 학기 동안 100번 학교에 갔는데 대부분은 지하철을 이용하지만 실제로 지하철보다 시간이 오래 걸리지만버스를 타고 가끔 학교에 갈 때도 있다면
– 최악 경우 분석은 버스를 타고 등교하는 시간이 60분이라면 60x100 = 6,000분을 넘지 않는 것으로 표현
– 상각 분석은 한 학기 동안 학교에 가는데 소요된 시간을 모두 합해서 학교에 간 횟수인 100으로 나눈 값을 1회 등교 시간으로 분석
– 대표적인 분석 예제: 크러스컬(Kruskal)의 최소 신장 트리 알고리즘

복잡도의 점근적 표기

자주 사용하는 O-표기

O(1) 상수 시간(Constant time)
O(logn) 로그 시간(Logarithmic time)
O(n) 선형 시간(Linear time)
O(nlogn) 로그 선형 시간(Log-linear time)
O(n2) 이차 시간(Quadratic time)
O(n3) 3차 시간(Cubic time)
O(nk) 다항식 시간(Polynomial time), k는 상수
O(2n) 지수 시간 (Exponential time)

요약

알고리즘이란 문제를 해결하는 단계적 절차 또는 방법이다.
알고리즘의 일반적인 특성
– 정확성: 주어진 입력에 대해 올바른 해를 주어야 – 수행성: 각 단계는 컴퓨터에서 수행 가능하여야. – 유한성: 유한 시간 내에 종료되어야 – 효율성: 효율적일수록 그 가치가 높다. 알고리즘은 대부분 의사 코드(pseudo code) 형태로 표현된다.
알고리즘의 효율성은 주로 시간 복잡도 (Time Complexity)가 사용된다.
시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현
알고리즘의 복잡도 표현 방법:

최악 경우 분석(Worst case Analysis)
평균 경우 분석(Average case Analysis)
최선 경우 분석(Best case Analysis) 점근적 표기(Asymptotic Notation): 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
O-(Big-Oh) 표기: 점근적 상한
Ω-(Big-Omega) 표기: 점근적 하한
Θ-(Theta) 표기: 동일한 증가율

정리