[크래프톤 정글 5기] week01 알고리즘 주차 네번째 날, 스택, 큐, DFS, 그래프, 백트래킹, 이분 탐색

스택(Stack)

- 후입선출(Last In First Out) 구조

- 마지막에 들어온 데이터가 가장 먼저 나간다

- 파이썬에서는 리스트와 pop(), append() 메소드로 스택을 구현할 수 있다

 

큐(Queue)

- 선입선출(First In First Out) 구조

- 먼저 들어온 데이터가 가장 먼저 나간다. “공정한 자료구조”

- from collections import deque 사용해서 deque 자료구조를 활용하는 게 좋다

- deque는 스택, 큐의 장점을 모두 채택한 것인데 리스트에 비해 빠르고 queue 라이브러리를 이용하는 것 보다 간단하다

- append(), popleft()를 이용하여 큐를 구현할 수 있다

 

DFS(Depth-First Search, 깊이 우선 탐색)

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

- 스택 자료구조를 이용하며, visited(방문 처리)를 이용해서, 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 한다. 방문 처리를 통해 각 노드를 한번씩만 처리한다.

- 일반적으로 방문하지 않은 노드 중에서, 번호가 낮은 순서부터 처리한다. ( DFS 기능 상 순서와 상관없이 처리해도 되지만, 관행적으로 그렇다 )

- 재귀 함수를 이용하면 구현이 간단하다.

- O(N)의 시간 복잡도를 가진다.

 

Graph(그래프)의 기본 구조

- 그래프는 노드(Node)와 간선(Edge)으로 표현된다. 노드는 정점(Vertex)이라고도 한다

- 두 노드가 간선으로 연결되어 있다면, 두 노드는 인접하다(Adjacent)라고 표현한다

 

그래프와 이동 거리(비용)

 

- 노드와 간선으로 이루어진다.

- 0과 1간의 이동은 비용7, 0와 2간의 이동은 비용5가 든다.

- 간선으로 연결되지 않은 노드간의 비용은 “무한”으로 표기한다.

- “무한”은 999999999나 987654321같은 논리적으로 정답이 될 수 없는 값 중에서 초기화하는 경우가 많다.

 

그래프를 표현하는 두 가지 방식

인접 행렬(Adjacency Matrix)

- 2차원 배열로 그래프 연결 관계 표현

- 위 그림의 오른쪽 표처럼 인접 행렬은 2차원 배열 형태로 구현하게 된다.

 

인접 리스트(Adjacency List)

- 리스트로 그래프 연결 관계 표현

- 인접 리스트는 "연결 리스트" 라는 자료구조를 이용해 구현한다.

- 파이썬은 리스트 자료형이 연결 리스트 기능을 제공한다.

- 인접 행렬과 비슷하게 2차원 배열 형태로 저장한다.

- graph = [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]   -> 인접 행렬과 다르게 연결되지 않은 곳은 저장하지 않는다!!

- graph[i]는 출발지를 의미하며, (목적지, 거리) 식으로 저장된다.

- 저장되지 않았다면 간선으로 연결되지 않은 것이다.

 

인접 행렬과 인접 리스트의 장단점

- 메모리 측면에서, 인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 낭비된다. 반면 인접 리스트는 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

- 하지만 인접 리스트는 인접 행렬 방식에 비해, 두 노드가 연결되어 있는지 확인하는 속도가 느리다.

- 만약 “모든 인접 노드를 순회”해야 하는 경우, 인접 리스트 방식이 더 효율적이다.

 

 

DFS 탐색 과정

- 시작 노드를 스택에 삽입하고 방문 처리 (삽입하면 최상단에 위치한다)

- 스택의 최상단 노드의 방문하지 않은 인접 노드 중, 가장 작은 노드를 스택에 넣고 방문 처리를 반복한다.

- 방문하지 않은 인접 노드가 없다면, 해당 노드를 스택에서 꺼낸 후 돌아간다.

- 방문하지 않은 인접 노드가 있는 노드로 돌아갈 때까지 노드를 스택에서 꺼낸다.

- 모든 노드에 방문 처리가 될 때까지 진행한다.

- 한번 스택에 들어갔다면 반드시 방문 처리를 해야 한다.

 

DFS 탐색 과정

 

아래는 DFS 예제 코드이다.

 

def dfs(graph, v, visited): # (노드연결정보, 시작노드, 방문정보)

    # 현재 노드 방문 처리

    visited[v] = True

    print(v,'방문')

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문

    for i in graph[v]: # v는 현재 노드, i는 현재 노드에 대한 인접 노드

        if not visited[i]: # 인접 노드에 아직 방문하지 않았다면

            dfs(graph, i, visited) # 해당 인접 노드부터 다시 탐색 시작 ( 스택의 최상단에 담기 ),

                                    # 이렇게 깊은 곳까지 가다가 인접 노드가 없으면 스택에서 빠지면서 인접 노드가 존재하는 상위 노드까지 돌아가 다시 탐색 시작

                                        # 모든 노드를 방문했다면 (visited가 전부 True일 경우) 함수는 종료된다

           

graph = [ # 노드번호와 인덱스를 동기화하기 위해 처음에 빈 리스트 추가

  [],

  [2, 3, 8],

  [1, 7],

  [1, 4, 5],

  [3, 5],

  [3, 4],

  [7],

  [2, 6, 8],

  [1, 7]

]

visited = [False] * 9 # 8개 노드이지만 빈 리스트가 있으므로 9개로 초기화

dfs(graph, 1, visited)

 

연결된 모든 노드를 한번 씩 방문하고 방문할 때마다 방문했다는 문구를 출력한다.

이 코드를 이해하고 DFS, 백트래킹 문제를 푸니 훨씬 수월했다.

 

백트래킹(backtracking)

- DFS처럼 모든 경우의 수를 탐색하되, 조건을 걸어서 유망하지 않을 경우(더이상 탐색해도 의미가 없을 경우) 가지치기를 하고 이전 노드로 되돌아가 다른 경우의 수를 탐색한다.

- 불필요한 부분을 쳐내는 걸 가지치기 라고 한다. ( 불필요한 부분 : 더이상 탐색해도 답이 되지 않을 경우의 수 )

 

이분 탐색(Binary Search)

- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

- 시간 복잡도는 O(logN)으로 빠른 편이다.

- 특정 배열에 특정 데이터가 있는지 조사할 때, 이분 탐색을 사용하면 굉장히 효율적이다.

- 일반적으로 start, end, mid 값을 이용해 구현한다. start는 탐색 시작지점, end는 탐색 끝 지점, mid는 start와 end의 중간지점이다.

- 찾을 데이터가 mid보다 위에 있다면 start를 올리고, mid보다 아래에 있다면 end를 내려가며 진행한다. 

 

# 이분 탐색 알고리즘 함수

def binarySearch(originList, n, data): # 배열, 배열 길이, 찾을 값

    start = 0

    end = n - 1

    while start <= end:

        mid = (start + end) // 2

        if originList[mid] == data:

            return True

        elif originList[mid] < data:

            start = mid + 1

        else:

            end = mid - 1

    return False

 

- 배열에서 특정 데이터를 찾기 원할 때 이 함수를 이용하기만 하면 된다.