[IT개론🗃️] 알고리즘

출처  : 소프트웨어 세상을 여는 컴퓨터과학

1. 알고리즘의 개요

1) 알고리즘의 개념

(1) 알고리즘(algorithm)

- 어떤 문제를 해결하기 위해 구성된 일련의 절차

 

(2) 알고리즘의 조건

- 0개 이상의 입력, 1개 이상의 출력

- 반드시 종료되어야 함

- 모든 명령이 실행 가능해야 함. 

 

---

 

2. 정렬 알고리즘

1) 선택 정렬

(1) 선택 정렬(selection sort)

- 정렬되지 않은 데이터 중에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식

 

(2) 선택 정렬의 동작과정

 

(3) 파이썬으로 구현한 선택 정렬

def selection(ds):
	for a in range(0, len(ds)-1):
    	min_ind = a
        for b in range(a+1, len(ds)):
        	if (ds[b] < ds[min_ind]):
            	min_ind = b
        ds[a],ds[min_ind] = ds[min_ind],ds[a]

dataSet = [3, 7, 2, 5, 9]
selection(dataSet)
print(dataSet)

 2) 삽입 정렬 

(1) 삽입 정렬(insertion sort)

- 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해가며 정렬하는 방식

 

(2) 삽입 정렬의 동작 과정

 

(3) 파이썬으로 구현한 삽입 정렬

def insertion(ds):
	for a in range(1, len(ds)):
    	key = ds[a]
        b = a-1
        while (b>=0 and ds[b]>key):
        	ds[b+1] = ds[b]
            b -= 1
        ds[b+1] = key
        
 dataSet = [3,5,2,8,5]
 insertion(dataSet)
 print(dataSet)

3) 버블 정렬

(1) 버블 정렬(bubble sort)

- 서로 이웃한 데이터들을 비교해 가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식

 

(2) 버블 정렬의 동작 과정

(3) 파이썬으로 구현한 버블 정렬

def bubble(ds):
	for a in range(0, len(ds)-1):
    	for b in range(0, len(ds)-1-a):
        	if (ds[b] > ds[b+1]):
            	ds[b],ds[b+1] = ds[b+1],ds[b]
                
dataSet = [7,4,2,6,1]
bubble(dataSet)
print(dataSet)

 

---

 

3. 탐색 알고리즘

* 탐색(search) : 데이터 집합에서 어떤 조건이나 성질을 만족하는 데이터를 찾는 것

 

1) 선형 * 탐색 

(1) 선형 탐색(linear search)

- 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하며 찾는 방법

- 순차 탐색(sequential search)이라고 함.

 

(2) 선형 탐색 과정

(3) 파이썬으로 구현한 선형 탐색

def linear(ds,key):
	for i in range(0, len(ds)):
    	if (key == ds[i]):
        	return i;
    return 
    
 dataSet = [5,2,1,7,4]
 print(linear(dataSet, 1))

 

2) 이진 탐색

(1) 이진 탐색

- 정렬된 데이터 집합을 반으로 쪼개가며 탐색하는 방법

 

(2) 이진 탐색 과정

(3) 파이썬으로 구현한 이진 탐색

def binary(ds,key):
	low = 0
    high = len(ds)-1
    while (low<=high):
    	mid = (low+high)//2
        if (key == ds[mid]):
        	return mid
        elif (key < ds[mid]):
        	high = mid - 1
        else : 
        	low = mid + 1
    return
    
dataSet = [1,3,5,7,9,11,13]
print(binary(dataSet,9))

 

 

 

---

 

4. 재귀 알고리즘

1) 재귀 알고리즘

(1) 재귀 알고리즘(recursive algorithm)

1부터 n까지의 합 = n + (1부터 n-1까지의 합)

 

2) 피보나치 수열

fibo(n) = 1 (n<=2일 때)

fibo(n) = fibo(n-1) + fibo(n-2)

 

(1) 피보나치 수열의 수렴 : fibo(n)/fibo(n-1) ≒ 1.618

- 황금분할 (1.618:1)

: 수학적으로 가장 아름답다고 여겨지는 비율

 

(2) 파이썬으로 구현한 피보나치 수열 계산

① 기본 구현 ; 비효율적 (구한 값들을 계속 다시 구하는 과정에서 많은 시간 소모)

def fibo(n):
	if (n<=2):
    	return 1
    return fibo(n-1) + fibo(n-2)

② 개선된 구현

- 딕셔너리를 이용해 한 번 구한 피보나치 값은 다시 구하지 않음

fiboDic = {0:0, 1:1}

def fibo(n):
	if n not in fiboDic:
    	fiboDic[n] = fibo(n-1) + fibo(n-2)
    return fiboDic[n]

 

3) 하노이 탑

(1) 하노이 탑

- 1883년 프랑스 수학자 루카스에 의해 고안된 문제

가운데 기둥을 이용해서 왼쪽 기둥에 놓은 크기가 다른 원판을 오른쪽 기둥으로 옮기시오. 이때 원판은 한 번에 한 개만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다. 

(2) 하노이 탑의 이동 횟수

: n개의 하노이 탑을 목적지로 욺기기 위해 필요한 원반의 이동횟수는 2^n-1

 

(3) 파이썬으로 구현한 하노이 탑

def hanoi(n, A,B,C):
	if (n == 1):
    	print('board', n, 'move', A, '->', C)
    else:
    	hanoi(n-1, A,C,B)
        print('board', n, 'move', A, '-> ',C)
        hanoi(n-1, B,A,C)

 

4) 퀵 정렬

(1) 퀵 정렬 

- 기준 키를 중심으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법

 

(2) 퀵 정렬의 동작 과정

(3) 파이썬으로 구현한 퀵 정렬

def quick(ds):
	if (len(ds)<2):
    	return ds
    else :
    	key = ds[0]
        left = [data for data in ds[1:] if data < key]
        right = [data for data in ds[1:] if data > key]
        return quick(left) + key + quick(right)