Algorithm_08

DP

• 동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제 를 해결하는 알고리즘 이다.
• 동적계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.
• 동적계획법은 메모이제이션과 함께 사용되기도 한다. 동적계획법은 작은 부분 문제들을 해결하는 데 사용되고, 메모이제이션은 각 부분 문제의 해답을 저장하고 재활용하는 데 사용된다.

피보나치 수 DP 적용

• 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.

def fibo2(n):
	f = [0] * (n+1)
    f[0] = 0
    f[1] = 0
    for i in range(2, n+1):
    	f[i] = f[i-1] + f[i+2]
    return f[n]

• memorization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적
• 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문

DFS

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요
• BFS (너비 우선 탐색)
• DFS (깊이 우선 탐색)
• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

DFS 알고리즘

1) 시작 정점 v를 결정하여 방문
2) 정점 v에 인접한 정점 중에서

• 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 정점 w를 방문한다.
• 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 방문 정점을 v로하여 반복한다.

3) 스택이 공백이 될 때까지 반복한다

Case_1: List 활용

def DFS(graph, start_node):
 
    ## 초기화
    need_visited, visited = list(), list()
 
    ## 시작 노드
    need_visited.append(start_node)
    
    ## 만약 아직도 방문이 필요한 노드가 있다면,
    while need_visited:
 
        ## 그 중에서 가장 마지막 데이터를 추출 (스택 구조의 활용)
        node = need_visited.pop()
        
        ## 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
 
            ## 방문한 목록에 추가하기 
            visited.append(node)
 
            ## 그 노드에 연결된 노드를 
            need_visited.extend(graph[node])
            
    return visited

Case 2: 재귀 함수 활용

def DFS_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐 
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            DFS_recursive(graph, node, visited)
    return visited

Case 3 : deque를 활용한 DFS 구현

def DFS2(graph, start_node):
    ## deque 패키지 불러오기
    from collections import deque
    visited = []
    need_visited = deque()
    
    ## 시작노드
    need_visited.append(start_node)
    
    ## 방문필요가 있다면
    while need_visited:
        ## 시작 노드 지정
        node = need_visited.pop()
 
        ##만약 방문한 리스트에 없다면
        if node not in visited:
 
            ## 방문 리스트에 노드를 추가
            visited.append(node)
            ## 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])
                
    return visited