알고리즘 필수. Stack/Queue/재귀/bfs/dfs

1. Stack

 삽입 append()

 삭제 pop()

 

2. Queue

 from collections import deque

 queue = deque()

 queue.append(5)

 queue.popleft()

 queue.reverse()

 

3. Recursive Function

 def recursive_function(i):

   if i == 100:

       return

   recursive_function(i+1)

 

 recursive_function(1)

 

3-1. Recursive Function - Factorial

 def fac(i):

    while i>1:

        return (i*fac(i-1))

    if i<=1:

        return 1

 

3-2. 최대공약수 구하기: 유클리드 호제법과 Recursive Function을 이용

 A%B = R일때 A와 B의 최대공약수는 B와 R의 최대공약수이다.

 GCD(192,162)

  A        B

 192     162

 162     30 

 30       12

 12       6

 

def gcd(a,b):

    if a%b ==0:

        return b

    else:

        return gcd(b,a%b)

 

4. DFS : Depth-First Search

  - 깊은부분 우선탐색

  - 스택 자료구조 or 재귀함수로 구현

  (1) 탐색 시작노드를 스택에 넣고 방문처리

  (2) 스택 최상단 노드에 방문하지않은 노드를 스택에 넣고 방문처리

  (3) 더이상 2를 수행할 수 없을 때까지 반복

 

ex. 그래프준비. v=시작노드번호. 방문기준은 번호가 낮은 인접노드부터.

def dfs(graph,v,visited):

    visited[v]=True

    for i in graph[v]:

        if not visited[i]:

            dfs(graph,i,visited)

graph=[

            0,[],

             0,[2,3,8],

             0,[1,7],

             0,[1,4,5],

             0,[3,5],

             0,[3,4],

             0, [7],

             0,[1,7]

             ]

 visited=[False]*9

 

dfs(graph,1,visited)

 

*stack: 1 2 7 6 8 3 4 5 

 

5. BFS: Breadth-First Search

 - 최단거리 문제

 - queue 이용

 (1) 탐색 시작 노드를 큐에 삽입 & 방문처리 

 (2) 인접 노드를 모두 큐에 삽입 & 방문처리

 (3) 더이상 2를 할 수 없을 때까지 반복