이것이 코딩테스트다 - 6일차

주제

dfs/bfs

자료구조

스택과 큐를 사용한다.

• 스택 : 후입선출 (ListInputFirstOutput)
• 큐 : 선입선출 (FirstInputFirstOutput)

# 스택
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()

# 큐
from collection import deque
queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()

재귀함수

자기 자신을 호출하는 함수

단, 너무 많이 호출하면 함수는 구조적으로 스택으로 되어있기 때문에 오류가 남

따라서, 꼭 종료조건이 필수

def recursive_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result
        


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

DFS

깊이 우선탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

1. 인접행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
2. 인접 리스트 : 리스트 그래프의 연결 관계를 표현하는 방식

인접행렬

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

-	0	1	2
0	0	7	5
1	7	0	무한
2	5	무한	0

matrix = [
    [0, 1, 1],  # 0
    [1, 0, 0],  # 1
    [1, 0, 0]   # 2
]

INF = 999999999
graph = [
    [0, 7, 5],      # 0
    [7, 0, INF],    # 1
    [5, INF, 0]     # 2
]

인접리스트

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

graph = [
    [1, 2], # 0
    [0],    # 1
    [0]     # 2
]

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))