알고리즘이란?

알고리즘의 정의

•

 어떤 문제를 컴퓨터로 풀기 위한 효율적인 절차

•

문제를 푸는 단계별 절차를 명확하게 기술

알고리즘을 공부하는 목적

•

다양한 문제 해결 방법(=알고리즘 설계 기법)을 공부함.

알고리즘

→ 어떤 문제의 모든 입력 사례에 대해서 해답을 찾아주는 단계별 절차

1.1 sequential search 순차 검색

def seqsearch (n, S, x):
	location = 1
	while (location <= n and S[location] != x):
		location += 1
	if (location > n):
		location = 0
	return location
Python
복사

1.2 Add Array Elements 리스트 합 구하기

def sum (n, S):
	result = 0
	for i in range(1, n + 1):
		result = result + S[i]
	return result
Python
복사

1.3 오름차순 정렬 Exchange Sort(교환 정렬)

def exchange (S):
	n = len(S)
	for i in range(n - 1):
		for j in range(i + 1, n):
			if (S[i] > S[j]):
				S[i], S[j] = S[j], S[i] #swap
Python
복사

1.4 행렬 곱셈 Matrix Multiplication

def matrixmult (A, B):
	n = len(A)
	C = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			for k in range(n):
				C[i][j] += A[i][k] * B[k][j]
	return C
Python
복사

알고리즘의 효율성

알고리즘의 성능: 시간과 공간 사용량의 효율성

순차 탐색 vs 이분 검색(binary search)

•

입력 리스트의 조건에 따른 탐색 알고리즘의 선택

- 정렬되지 않은 리스트에서 키 찾기: 순차 탐색

- 정렬된 리스트에서 키 찾기 : 이분 검색

이분 검색

주어진 리스트 S와 키 x에 대해서,

먼저 x를 리스트의 중앙에 위치한 원소와 비교

만약 같으면, 찾았으므로 알고리즘을 종료

만약 x가 그 원소보다 작으면 x는 왼쪽에 있을 것이므로 왼쪽 리스트에 대해서 이진탐색 실행(재귀 호출)

만약 x가 그 원소보다 크면 x는 오른쪽에 있을 것이므로 오른쪽 리스트에 대해 이진 탐색 실행(재귀 호출)

더 이상 찾을 리스트가 없으면 알고리즘을 종료

1.5 Binary Search( Iterative) 이진 탐색 이분 검색

def binsearch(n, S, x):
    low = 1
    high = n
    location = 0
    while(low <= high and location == 0):
        mid = (low + high) //2
        if (x == S[mid]):
            location = mid
        elif (x < S[mid]):
            high = mid -1
        else:
            low = mid + 1
    return location
Python
복사

1.6 n-th Fibonacci Term (Recursive) n번째 피보나치수 찾기(재귀)

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)
Python
복사

→ 비효율적임. 예를 들어 fib(5)실행하면 fib(1)은 4번이나 호출됨

1.7 n-th Fibonacci Term (Iterative) n번째 피보나치수 찾기(반복)

def fib2 (n):
    f = [0] * (n+1)
    if n> 0:
        f[1] = 1
        for i in range(2, n+1):
            f[i] = f[i-1] + f[i-2]
    return f[n]
Python
복사

분할정복법(Divide-and-Conquer)

2.1 Binary Search (Recursive) 이분검색 (재귀)

def location(S, low, high):
    if low > high:
        return 0
    else:
        mid = (low + high)//2
        if x == S[mid]:
            return mid
        elif x < S[mid]:
            return location(S, low, mid -1)
        else:
            return location(S, mid+1, high)
Python
복사

2.2 Merge Sort 합병정렬 - 사실상 가르고 붙이기

def mergesort(S):
    n = len(S)
    if n <= 1:
        return S
    else:
        mid = n // 2
        U = mergesort(S[0:mid])
        V = mergesort(S[mid:n])
        return merge(U, V)
Python
복사

2.3 Merge 합병 - 여기서 사실상 정렬

def merge(U, V):
    S = []
    i = j = 0
    while (i < len(U) and j < len(V)):
        if (U[i] < V[j]):
            S.append(U[i])
            i += 1
        else:
            S.append(V[j])
            j += 1

    if i < len(U):
        S += U[i : len(U)]
    else:
        S += V[j : len(V)]
    return S
Python
복사

2.4 MergeSort2 (Enhanced Merge Sort)

def mergesort2 (S, low, high):
	if low < high :
		mid = (low + high) // 2
		mergesort2(S, low, mid)
		mergesort2(S, mid + 1, high)
		merge2(S, low, mid, high)
Python
복사

2.5 Merge 2(Enhanced Merge)

def merge2(S, low, mid, high):
		U = []
		i = low
		j = mid + 1
		while( i <= mid and j <= high):
				if(S[i] < S[j]):
						U.append(S[i])
						i += 1
				else:
						U.append(S[j])
						j += 1
if i <= mid:
		U += S[i : mid + 1]
else:
		U += S[j : high + 1]
for k in range(low, high + 1):
		S[k] = U[k-low]
Python
복사

2.6 Quick-Sort (퀵솔트)

def quicksort (S, low, high):
		if (high > low):
				pivotpoint = partition(S, low, high)
				quicksort(S, low, pivotpoint - 1)
				quicksort(S, pivotpoint + 1, high)
Python
복사

기준 원소(pivot)는 어떻게 정할까? 편의상, 일단 리스트의 첫 원소를 기준 원소로 정하도록 하자

2.7 Partition(for QuickSort)

def partition (S, low, high):
		pivotitem = S[low]
		j = low
		for i in range(low + 1, high + 1):
				if (S[i] < pivotitem):
						j += 1;
						S[i], S[j] = S[j], S[i] # swap
		pivotpoint = j
		S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
		return pivotpoint
Python
복사

동적계획법(Dynamic Programming)

-문제를 더 작은 문제로 분할하되, 상향식으로 문제를 해결한다.

문제를 해결할 수 있는 재귀 관계식을 구한다.(점화식)

가장 작은 입력 사례로부터 상향식 방법으로 문제를 해결한다.

분할정복법 vs 동적계획법

-문제를 작은 사례로 분할하여 해결한다는 점에서 동일

분할정복: 재귀 호출을 통해 분할하여 정복 (Top - Down)

동적 계획: 메모이제이션을 통해 상향식으로 정복 (Bottom- up)

ex) 피보나치 수열

이항계수는 뛰어넘고.

최단경로(플로이드 알고리즘)

-주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로를 구하시오.

*단순무식한 방법

-각 정점에서 다른 정점으로 가는 모든 경로를 구한 뒤 그 경로들 중에서 가장 짧은 경로 찾기

효율성 (n-2)!

그래프의 표현 : 인접 행렬(adjacency matrix)

1단계 : 재귀관계식을 찾는다.

-D : 각 정점의 쌍이 가지는 최단 경로의 길이를 나타내는 행렬

-D[i][j] : Vi 에서 Vj로 가는 최단 경로의 길이

2단계: 상향식 방법으로 해답을 구한다

3.1 Floyd’s Algorithm for Shortest Path

def floyd(W):
		D = W
		n = len(W)
		for k in range(n):
				for i in range(n):
						for j in range(n):
								D[i][j] = min(D[i][j], D[i][k] + D[k][j])
		return D
Python
복사

최단 경로는요?

P[i][j] : Vi에서 Vj로 가는 최단 경로가 거쳐야하는 새로운 정점

최단 경로의 중간에 놓여있는 정점이 없는 경우에는 -1

3.2 Floyd’s Algorithm for Shortest Path 2

def floyd2(W):
		n = len(W)
		D = W
		P = [[-1] * n for _ in range(n)]
		for k in range(n):
				for i in range(n):
						for j in range(n):
								if (D[i][j] > D[i][k] + D[k][j]):
										D[i][j] = D[i][k] + D[k][j]
										P[i][j] = k
		return D, P
Python
복사

P[i][j] = -1 이면, 간선 (Vi, Vj)가 최단 경로임.

P[i][j] = k인 경우 inorder 탐색 (Vi, Vk)의 최단경로 출력 후 Vk를 출력하고 (Vk, Vj)의 최단경로 출력

3.3 Print Shortet Path

def path(P, u, v):
		if(P[u][v] != -1):
				path(P, u, P[u][v])
				print('v%d' %(P[u][v]), end = '-> ')
				path(P, P[u][v], v)
Python
복사