알고리즘

알고리즘_01.기초

강용민 2021. 9. 30. 17:57

1.알고리즘의 역할

1.1알고리즘

알고리즘은 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차.

즉, 어떤 입력을 어떤 출력으로 변환하는 일련의 계산 과정이다.

사례

해당 문제의 해를 계산하기 위해 필요한 입력으로 구성되며 문제의 정의에서 요구하는 입력에 대한 제약조건을 만족해야 한다.

 

알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 타당하다고 하며, 그 타당한 알고리즘이 주어진 계산 문제를 푼다(solve)고 말한다.

(하지만 타당하지 않은 알고리즘도 오류의 비율을 조절할 수 있으면 유용할 떄가 있다.)

 

알고리즘의 특징

  • 후보 해는 많지만 대부분이 문제의 해가 아니다. 
  • 실용적인 응용 예가 존재한다. (Q. 달리 말하면, 실용적인 응용의 예가 없다면 쓸모가 없는가?)

자료구조

자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조직하는 방법이다.

모든 목적에 가장 맞는 단일 자료구조는 당연히 없다. 그러므로 각 자료구조의 장점과 한계를 잘 아는 것이 중요하다.

 

병렬성

오랫동안 프로세서의 클록 속도가 일정한 비율로 증가하는 것을 기대할 수 있었지만 물리적 한계로 더 이상의 증가는 어려워졌다.

그래서 칩은 시간당 계산 성능을 늘리기 위해 단 하나가 아닌 여러 계산을 처리할 수 있도록 코어(core)를 가지도록 설계된다. 이는 일종의 병렬 컴퓨터(parallel computer)다.

멀티 코어 컴퓨터로부터 최고의 성능을 얻으려면 알고리즘을 설계할 때 병렬성을 염두에 두어야 한다. 대표적으로 멀티스레드 알고리즘을 위한 모델이 있다.

 

1.2 기술로서의 알고리즘

컴퓨터가 상당히 빠를 수는 있지만 무한히 빠를 수는 없다. 메모리도 매우 저렴할 수는 있지만 비용이 전혀 들지 않을 수는 없다. 그러므로 자원을 효율적으로 사용해야 하며, 시간과 공간 측면에서 효율적인 알고리즘이 필요하다.

 

효율성

알고리즘에 따라 시간 효율성은 엄청난 차이를 보인다. 그 예로 두 종류의 정렬 알고리즘을 살펴보자.

삽입 정렬 병합 정렬
n개의 값을 정렬하는데 대략 cn^2의 시간이 걸린다.
즉, O(n^2)의 시간이 걸린다.

1000만개의 숫자를 정렬한다고 쳤을때(대략 80MB정도밖에 안된다.), (10^7)^2라는 시간이 걸린다.		 n개의 값을 정렬하는데 O(nlg(n))의 시간이 걸린다.

1000만개의 숫자를 정렬한다고 쳤을때, 10^7lg(10^7)라는 시간이 걸린다. 삽입정렬보다 적어도 10^6만큼의 시간이 절약된다.

하드웨어처럼 알고리즘도 하나의 기술임을 보여준다. 전체 시스템의 성능은 빠른 하드웨어뿐만 아니라 얼마나 효율적인 알고리즘을 선택하느냐에 따라서도 결정된다.

2. 시작하기

알고리즘을 설계하고 분석하기 위해 사용하는 체계를 알아본다.

삽입 정렬, 분할 정복, 병합 정렬의 수행 시간 분석으로 나아가겠다.

 

2.1 삽입 정렬

문제.

무작위적인 n개의 수열을 규칙(적은 수부터 큰 수대로 or 큰 수부터 작은 수대로)적으로 재배치하여라.

 

삽입 정렬이란 정렬된 구간과 그렇지 않은 구간 둘로 나누고, 정렬되지 않은 구간의 맨 앞 원소를 가져와 정렬된 구간에 삽입하는 알고리즘이다.

 

for j= 2 to A.length
	key = A[j]
    //A[j]를 정렬된 배열 A[1..j-1]에 삽입한다.
    i = j -1
    while i > 0 그리고 A[i] > key
    	A[i+1] = A[i]
        i = i - 1
    A[i + 1] = key

 

루프 불변성과 삽입 정렬의 타당성

루프 불변성

알고리즘이 타당한 이유를 쉽게 이해할 수 있도록 하기 위해 사용된다. 루프 불변성을 보이려면 다음 세 가지 특성을 만족해야 한다.

  • 초기 조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.
  • 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.
  • 종료 조건: 루프가 종료될 때 그 불변 식이 알고리즘의 타당성을 보이는 데 도움이 될 유요한 특성을 가져야 한다.

이런 방법은 어떤 특성을 증명하기 위해 베이스 케이스와 귀납적 과정을 통해 증명하는 수학적 귀납법과 유사함을 알 수 있다.

 

2.2 알고리즘의 분석

알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것. 대부분의 경우 측정 대상은 계산 시간이다.

알고리즘을 분석하기에 앞서 이용할 구현 기술의 모델을 잘 정의해야 하는데, 여기에는 그 기술에 필요한 자원과 비용에 관한 모델도 포함된다.

앞으로는 알고리즘이 단일 프로세서와 랜던 접근 기계(RAM, random-access machine) 모델에서 컴퓨터 프로그램으로 구현된다고 가정한다.

더보기

RAM

명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다.

삽입 정렬의 분석

삽입 정렬의 수행 시간은 입력에 의해 결정된다. 입력 크기가 커질수록 알고리즘의 수행시간이 증가하므로 수행시간을 입력 크기의 함수로 표현한다.

 

INSERTION-SORT(A)
for j = 2 to A.length
	key = A[j]
    //A[j]를 정렬된 배열 A[1..j-1]에 삽입한다.
    i = j -1
    while i > 0 and A[i] > key						
    	A[i + 1] = A[i]
        i = i - 1c
    A[i + 1] = key

알고리즘의 수행시간은 각 명령문 수행 시간의 합니다. 즉, 수행 시간이 c(i) 단계만큼 걸리는 명령문이 n번 실행된다면 총 수행 시간에 c(i) n만큼 기여하게 된다.

 

분석의 종류

  • Worst case
    T(n) = maximum time of algorithm on any input of size n(어떤 n개의 input에 대하여 걸리는 최대 시간)
  • Average case
    T(n) = expected time of algorithm over all inputs of size n(n개의 input에 대하여 걸리는 예상 시간)
  • Best case
    Cheat with a slow algorithm that works fast on some input

θ

Ω ω

O o

 

분할과 정복

분할 : 여러개의 부분문제들로 쪼개는 것

정복 : 해결을 위해 쪼개진 분할문제를 푼다.

Combine : 해결된 부분문제를 합친다.

 

Merge Sort(병합 정렬)

MERGE_SORT(A, p, r)
	if p < r
    	then q <- L(p +1)/2ㅢ
        	MERGE_SORT(A, p, q)
            MERGE_SORT(A, q + 1, r)
            MERGE(A, p, q, r)
            
            
MERGE(A, p,q ,r)
n(1) <- q - (p-1)
n(2) <- r - q
create arrays L[1..n(1)+1] and R[q..n(2)+1]
for i <- 1 to n(1)
	do L[i] <- A[p + i -1]
for j <- 1 to n(2)
	do R[j] <- A[q + j]
 L[n(1) + 1] <- 무한
 R[n(2) + 1] <- 무한
i <- 1
j <- 1
for k <- p to r
	do if L[i] <= R[j]
    	then A[k] <- L[i]
        	i <- i + 1
        else A[k] <- R[j]
        	j <- j + 1

재귀정렬이기도 하다. 재귀함수를 하기에 높이 : lg(n), merge : n으로 θnlog(n)의 시간복잡도를 가지고 있다.

T(n) = 2T(n/2) + θ(n)

 

BubbleSort

BUBBLESORT(A)
for i <- 1 to A.length
	do for j <- A.length downto i+1
    	do if A[i] < A[j - 1]
        	then exchange A[j] <-> A[j - 1]

 

Recursion-Tree Method

 

Master Method

Recurrence must be of the form:T(n) = aT(n/b) + f(n)

  • If f(n) = O(n^log(b)a - i)
    for some constant i>0,
    then T(n) = θ(n^log(b)a
  • If f(n) = θ(n^log(b)a),
    then T(n) = θ(n^log(b)a lg n)
  • If f(n) = Ω(n^log(b)(a+i))
    for som8e constant i>0,
    and if af(n/b) <= cf(n) for some constant c<1
    and all sufficiently large n,
    then T(n) = θ(f(n))

스트라센 알고리즘

procedure matultiply(X, Y, Z, n);
comment multiplies n * n matrices X := YZ
for i := 1 to n do
	for j:= 1to n do
    	X[i,j] := 0;
        for k := 1to n do
        	x[i,j] := X[i,j] + Y[i,k] * Z[k,j]

O(n^3)인데 스트라센이라는 사람이 O(n^2.8)로 바꿈

 

 

 


출처: https://godgod732.tistory.com/12 [졸지말고..]

       introduction to algorithms

'알고리즘' 카테고리의 다른 글

알고리즘_POA  (0) 2021.10.24
알고리즘_06.HeapSort  (0) 2021.10.19
알고리즘_목차  (0) 2021.09.30

'알고리즘'의 다른글

  • 현재글알고리즘_01.기초

관련글

댓글

티스토리툴바