Algorithm 이란?

생각하는 방법을 터득한 것은 미래의
문제를 미리 해결한 것이다.

- 제임스 왓슨

알고리즘이란 무엇인가?
• 문제 해결 절차를 체계적으로 기술한 것
• 문제의 요구조건
– 입력과 출력으로 명시할 수 있다
– 알고리즘은 입력으로부터 출력을 만드는 과정을 기술

입출력의 예
• 문제
– 100명의 학생의 시험점수의 최대값을 찾으라
• 입력
– 100명의 학생들의 시험점수
• 출력
– 위 100개의 시험점수들 중 최대값


알고리즘 공부의 목적
• 특정한 문제를 위한 알고리즘의 습득
• 체계적으로 생각하는 훈련
• 지적 추상화의 레벨 상승
– Intellectual abstraction
– 연구나 개발에 있어 정신적 여유를 유지하기 위해 매우 중요한 요소


바람직한 알고리즘
• 명확해야 한다
– 이해하기 쉽고 가능하면 간명하도록
– 지나친 기호적 표현은 오히려 명확성을 떨어뜨림
– 명확성을 해치지 않으면 일반언어의 사용도 무방
• 효율적이어야 한다
– 같은 문제를 해결하는 알고리즘들의 수행시간이 수백만배 이상 차이
날 수 있다





알고리즘( Algorithm )이란

어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 수학과 컴퓨터 과학에서 알고리즘이란 작동이 일어나게 하는 내재하는 단계적 집합이다. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다.
 

알고리즘의 조건

알고리즘은 다음의 조건을 만족해야 한다.

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.

출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)

명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.

유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.

효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

 

연구 분야

고안 : 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리즘을 개발하는데 그 의미가 있다.

검증 : 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요하다. 알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는 데 그 목적이 있다.

분석 : 고안된 알고리즘을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.

테스트 : 디버깅, 성능분석

좋은 알고리즘의 분석 기준

정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.

작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산

기억 장소 사용량 : 수행에 필요한 저장 공간

최적성 :그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다

복잡도 (점근 표기법 : Big-O Notation)

O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘

O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.

O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.

O(N log N) : 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.

O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.

O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.

O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.

O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법

알고리즘 수행시간

알고리즘의 수행시간을 좌우하는 기준은 다양하게 잡을 수 있
다
– 예: for 루프의 반복횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟
수, …
• 몇 가지 간단한 경우의 예를 통해 알고리즘의 수행시간을 살
펴본다

sample1(A[ ], n)
{
        k = ;
        return A[k] ;    
}
n에 관계없이 상수 시간이 소요된다.

sample2(A[ ], n)
{
        sum ← 0 ;
        for i ← 1 to n
                sum ← sum+ A[i] ;
        return sum ;     
}

n에 비례하는 시간이 소요된다.

sample3(A[ ], n)
{
        sum ← 0 ;
        for i ← 1 to n                
                for j ← 1 to n
                        sum ← sum+ A[i]*A[j] ;
        return sum ;     
}

n2에 비례하는 시간이 소요된다.

sample4(A[ ], n)
{
        sum ← 0 ;
        for i ← 1 to n                
                for j ← 1 to n {
                    k ← A[1 ... n] 에서 임의로 개를 뽑을
때 이들 중 최대값 ;
                        sum ← sum + k ;
                }
        return sum ;     
}

n3에 비례하는 시간이 소요된다.

sample5(A[ ], n)
{
        sum ← 0 ;
        for i ← 1 to n-1                
                for j ← i+1 to n
                        sum ← sum + A[i]*A[j] ;         
return sum ;     
}
알고리즘의 수행시간
i=1일때 for 루프는 (n-1)회 반복, i=2일때 (n-2)회 반복, ... ,
i=n-1일때 1회 반복.
총 반복 횟수는 n(n-1)/2
따라서, n2에 비례하는 시간이 소요된다.

factorial(n)
{
        if (n=1) return 1 ;
        return n*factorial(n-1) ; -> 재귀(자기호출)
}

n에 비례하는 시간이 소요된다.