[엘리스 AI 트랙 2기] 02주차-실시간 이론강의. 알고리즘(06/30)

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' 실시간 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

실습

알고리즘

알고리즘도 자료구조와 마찬가지로 컴퓨터 공학부에서도 1학기 전공 필수 과목

실시간 이론강의 시간에 모두 이해한다는 것은 거의 불가능하니 
 개인 시간을 내서라도 꼭 공부해야 하는 과목

01. 알고리즘이란?

어떤 문제를 해결하기 위한 일련의 방법

 

ex)

 

임의로 뿌려져 있는 정보들을 오름차순으로 정렬하기

지금 위치에서 집까지 가장 빠른 경로를 찾기

현재 바둑판에서 가장 승률이 좋은 경우의 수를 찾기

02. 재귀함수

자신을 재참조하는 함수 (# 구지함수(자신을 다시 부르는 함수)라고도 함)

재귀함수의 동작 분석

함수가 다시 나를 부를때, 미처 실행되지 않은 다음 코드들은

언젠가 실행될 예정!

유클리드 호제법

두 양의 정수 a, b(a>b)에 대하여, a = bq + r (0 <= r < b)라 하면,

a, b의 최대공약수는 b, r의 최대공약수와 같다.

 

gcd(a, b) = gcd(b, r)

r = 0이면, a, b의 최대 공약수는 b이다.

def gcd(a, b):
   if b == 0 :
       return a
   else:
       return gcd(b, a % b)

03. 정렬

배열을 정렬하는 방법에 대해 알아보자

버블 소트

가장 기본적인 배열의 정렬 방법

시간복잡도 O(n^2)
- 삼각형에 비유해서 실제로는 1/2*n(n-1)이나 시간복잡도는 숫자를 제외하여 생각한다

class Array:
    def __init__(self):
        self.arr = [5,4,3,2,1,10,9,8,7,6]
 
    def bubble_sort(self):
        # for i = 0; i < arr.length; i++
        for i in range(0, len(self.arr)):
            # for j = i+1; j < arr.length; j++
            for j in range(i + 1, len(self.arr)):
                if i < len(self.arr) - 1:
                    if self.arr[i] > self.arr[j]:
                        tmp = self.arr[j]
                        self.arr[j] = self.arr[i]
                        self.arr[i] = tmp
 
                        # [4, 3] => [3, 4]
                        # tmp = 3
                        # [4, 4]
                        # [3, 4]

퀵소트

- 아무거나 비교할 원소를 하나 정한다.

- 이 원소보다 작은 원소, 큰 원소, 같은 원소를 분할한다.

- 이후 작은 원소/큰 원소들에 대해 재귀적으로 퀵 소트를 진행한다.

 

 

분할 정복을 이용한 정렬 방법

분할 정복이란, 큰 문제를 작은 문제 단위로 쪼개며 문제를 해결하는 방법

# 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다

L는 L번째 값이 pivot보다 클 때까지 움직임

R는 R번째 값이 pivot보다 작을 때 까지 움직임

 

L과 R을 바꿈

 

L > Pivot, R < Pivot을 찾을 때 까지 계속 이동

 

R<L이 되면 R을 기준으로 왼쪽과 오른쪽이 R과 Pivot을 바꾸어주면,

왼쪽이 Pivot보다 작게, 오른쪽이 Pivot보다 크다.

 

왼쪽 배열과 오른쪽 배열에 대해 같은 작업을 반복한다.

 

좀 더 정확히 표현하자면

왼쪽 배열 = (L, pivot – 1)

오른쪽 배열 = (pivot + 1, R)

정렬의 시간 복잡도는 n*logn이다.

 

일반적인 경우 O(nlogn), 최악의 경우 O(n^2)

최악의 경우는 보통 역으로 정렬돼있는 경우,
피벗을 어떻게 정하냐에 따라 속도가 달라지는 경우가 있어서

STL의 sort함수는 피벗을 랜덤하게 정하는 기능들이 추가돼있음.

 

 

def quickSort(array): o(N^2)

def quickSort(array):
    iterable_size = len(array)
    answer = []

    for i in range(0, iterable_size):
        array_min = min(array)
        answer.append(array_min)
        array.pop(array.index(array_min))
    return answer

def quickSort(array): o(N log N)

def quickSort(array):
   if len(array) <= 1:
        return array
    
    pivot = array[0]
    
    left = []
    right = []
    
    for i in range(1, len(array)):
        num = array[i]
        
    return quickSort(left) + pivot + quickSort(right)

04. 트리 탐색 (DFS, BFS)

트리를 탐색하는 방법

자료구조 시간에 배운 트리를 탐색하는 방법 크게 2가지로 구분

• DFS: 깊이우선탐색
• BFS: 너비우선탐색

DFS

트리의 깊이(Depth)를 우선으로 탐색하는 방법

자식->자식->자식->...

 

탐색의 시간복잡도 O(n)

DFS 구현 방법

재귀함수 또는 스택을 이용하여 구현

BFS

트리의 너비를 우선으로 탐색하는 방법

자식1->자식2->자식3->자식1의자식1->자식1의자식2->...

BFS 구현 방법

큐를 이용하여 구현!

자식들을 큐에 다 넣으면서 탐색을 진행한다!

 

자식들을 큐에 삽입

큐에서 원소를 pop하고 그 노드로 이동

자식들을 큐에 삽입

큐에서 pop

자식들을 큐에 삽입

큐에서 pop, 이동

자식이 없는 경우 바로 pop 후 이동

큐가 빌 때 까지 반복

DFS와 BFS를 언제 사용하면 좋을까?

• 보통 길찾기 또는 배열에서 움직임을 구현할 때 많이 사용
• DFS:재귀를통해간단하게구현할수있지만, 
  100번 이상 재귀호출이 반복될 경우 Call Stack이 터질 수 있음
• BFS : 큐를 이용해야 하므로 구현이 조금 복잡하지만,
  DFS보다 조금 더 큰 사이즈의 문제를 해결할 수 있다.

05. 동적 계획법 (Dynamic Programming)

어떤 범위까지의 값을 구하기 위해, 그것과 다른 범위의 값을 이용하는 방법

• 수학에서 점화식!
• “기억하며 풀기" # 조금더 적합한 용어가 아닐까..

DP를 이용한 피보나치 수열

피보나치 수열은 a(n+1) = a(n) + a(n-1) 이라는 점화식으로 구성 가능  
따라서 “그 전에 계산해뒀던 결과를 재활용”할 수 있다

class Fib():
    def __init__(self):
        self.memo = []
	def fibonacci(self, num): 
        for n in range(0, num+1): 
            if n == 0:
                self.memo.append(0)
            elif n == 1:
                self.memo.append(1)
            else:
                self.memo.append(self.memo[n - 2] + self.memo[n - 1])  
    	return self.memo[num]
        

def main():
    Fi = Fib()
    print(Fi.fibonacci(10)) # should return 55


if __name__ == "__main__":
    main()
``

# 재귀를 통해 불러오지 않고 결과값을 미리 리스트에 저장해놓는다.   

# 간단한 케이스를 생각해서 직접 그리고, 본질을 파악한 후 코드를 작성하면 더 쉬움

# 메모리를 저장해놓음으로써 더 효율적인 프로그램 실행 가능 

06. 탐욕 알고리즘

탐욕 알고리즘이란?

지금 이 순간 최적인 답을 찾아가는 알고리즘

Ad-Hoc이라고도 표현함

“최적의 해” 를 보장하지는 않는다!

최적 부분 구조

문제를 부분 문제로 나누어, 부분 문제에 대한 최적 방법 찾기

근사 알고리즘

적당히 괜찮은 방법을 찾을 때 사용하는 방법

최적의 해를 보장하지는 않는다.

다익스트라 알고리즘

그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘

최적해를 구하지 못하는 경우

배낭문제

외판원 문제

- 외판원이 n개의 도시를 모두 방문하고 원래 도시로 돌아올 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?

P 문제와 NP 문제

P 문제 : 쉬운 문제, 즉 시간복잡도가 다항식(Polynomial)으로 표현가능한 문제  

NP 문제: 어려운문제, 즉 시간복잡도가 다항식으로 표현되지 않는 문제

P-NP 문제

• NP-완전 문제
• NP-난해 문제

NP 완전 문제

어떤 문제의 답이 YES일때, 그 답에 대한 힌트가 주어지면 검산할 수 있는 문제

ex)

• 어떤 집합 Z의 부분집합들 중, 원소들의 합이 0이 되는 집합이 존재하는가?
• 이 문제에 대한 일반적인 해답은 없다.
• 그러나 어떤 해답이 주어졌을때, 그 답이 정답인지 아닌지는 다항시간에 판단할 수 있다.
• {-5, 6, 1, 2, -10, -7, 13}
• 이 집합의 부분집합 중 합이 0이되는 부분집합을 구하는 “쉬운” 방법은 없지만
• {6, 1, -7} 이라는 어떤 부분집합의 합이 0이라는 것은 쉽게 알 수 있다.