이것이 코딩테스트다 with 파이썬 기반 정리 내용입니당
이코테 3강

스택과 큐

스택 ? 선입후출 방식

큐 ? 선입선출 방식

stack = []
stack.append(5)
stack.pop()
stack.append(3)
stack.append(1)
print(stack[::-1])
print(stack)

from collections import deque

queue =deque()
queue.append(5)
queue.append(3)
queue.append(1)
#queue.popleft()

#queue.reverse()
print(queue[0])

재귀함수

함수를 재귀적으로 호출
단순히 반복문을 사용하는것보다 코드가 간결해질 수 있음

유클리드 호제법

• 두 자연수 A와 B에 대하여 (A>B)일 때 A를 B로 나눈 나머지를 R

• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같음

• 이 아이디어를 그대로 재귀함수로 작성할 수 있음

def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

print(factorial_recursive(5))

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

print(gcd(192,162))

• 스택을 사용할 때 재귀 함수를 이용하는 경우가 많음

DFS

• 깊이 우선 탐색,그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀함수)를 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

graph = [ [],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [False]*9

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)
dfs(graph,1,visited)

BFS

• 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 모두 큐에 삽입하고 방문 처리합니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

from collections import deque
graph = [ [],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [False]*9

def BFS(graph,v,visited):
    queue=deque([v])
    visited[v]=True
    while queue:
        v=queue.potleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

후기.. 알고리즘은 재밌구나... 성취감이 있다.. 하지만 어렵다....