[알고리즘][비선형 자료구조] - 비선형(Non-Linear) 자료구조

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

[비선형 자료구조란?]

• 순차적(Sequential)으로 또는 선형으로 배열되지 않는 자료구조를 비선형 자려구라고 한다.
• 비선형 자료구조는 선형과 달리 멀티 레벨로 구성된다.
• 이는 트리나 그래프(그래프의 범주에 있는 트리)를 떠올리면 쉽다.

[그래프 순회]

그래프 순회란 그래프 탐색(Search)라고도 불리우며 그래프의 각 정점을 방문하는 과정을 이야기 한다.

[그래프 순회의 종류]

• 깊이 우선 탐색(Breadth-First Search BFS)
  • 주로 큐(Queue)를 사용해서 구현한다.
  • 그래프의 최단 경로를 구하는 문제에서 사용한다.
• 너비 우선 탐색(Depth-First Search DFS)
  • 대부분의 코딩테스트에서의 그래프 탐색은 DFS를 사용해서 진행하게 될 것이다.
  • 주로 스택이나 재귀로 구현한다.

[그래프 표현 방법]

• 인접 행렬(Adjacency Matrix)
• 인접 리스트(Adjacency List)

[DFS(깊이 우선 탐색)]

• 스택과 재귀를 사용해서 구현하고 코딩테스트에서는 재귀를 더 선호되는 편이다.

[재귀를 사용한 DFS 구현 코드]

def recursive_dfs(v, visited = []):
    visited.append(v)
    for i in graph[v]:
        if i not in visited:
            visited = recursive_dfs(i, visited)
        return visited

• 이때 graph가 있다고 가정하고 쓴 코드이다.

[스택을 사용한 DFS 구현 코드]

def stack_dfs(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for i in graph[v]:
                stack.append(i)
    return visited

[BFS(너비 우선 탐색)]

• DFS보다는 쓰임새가 적지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 사용된다.

[큐를 사용한 BFS 구현 코드]

def Queue_bfs(start_v):
    visited = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for i in graph[v]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
    return visited

[BFS는 재귀로 구현이 불가하다.]

• BFS는 큐를 사용한 반복 구현만 가능하다.
• 재귀를 통한 BFS 구현은 불가능 하다.

[백트래킹]

• DFS보다 좀 더 광의의 의미를 지닌다. (더 넓은 의미를 가진다는 뜻이다.)
• 탐색을 하다 더 갈 수 없을 때 온 길을 되돌아가는 데서 유래했다.
• DFS는 백트래킹의 골격을 이루는 알고리즘이다.
• 백트래킹은 주로 재귀로 구현한다.
• 기본적으로 DFS의 범주에 속한다.

[브루트 포스와 다른 점]

• 브루트 포스는 방문했던 곳을 계속 방문할 수 있는 무식한 방법이지만 백트래킹의 경우 한번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기하고 다른 길을 모색한다는 점에서 브르투포스와의 큰 차별점을 가지고 있다.
• 이를 가지치기라고 하며 이처럼 불필요한 부분을 일찍 포기한다면 탐색을 최적화할 수 있기 때문에 가지치기는 트리의 탐색 최적화 문제와도 관련이 깊다.

[제약 충족의 문제]

• 제약 충족의 문제(Constraint satisfaction problem, CSP)란 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 일컫는다.
• 백트래킹은 제약 충족 문제의 필수적 알고리즘이다. 가지치기를 통해 제약 충족 문제를 최적화 하기 때문이다.