TIL-231003(자료구조 & 알고리즘 2주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 2주차 강의 듣기

 

알게 된 점❗

[  트리의 표현 방법  ]

트리

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조

 

자료구조는 크게 비선형구조, 선형구조로 구분된다.

선형구조 : 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있다.

비선형구조 : 표현에 초점이 맞춰져 있다.

 

노드(Node) : 연결 관계를 가진 각 데이터를 의미. 정점(Vertex)이라고도 함.

간선(Edge) : 노드 간의 관계를 표시한 선.

인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)

 

유방향 그래프(Directed Graph) : 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.

무방향 그래프(Undirected Graph) : 방향이 없는 간선을 갖는다.

 

트리의 표현방법

그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있다.

인접행렬(Adjacnecy Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

인접 리스트(Adjacnecy List) : 링크드 리스트로 그래프의 연결 관계를 표현

 

[  DFS  ]

DFS(Depth First Search)

갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조

1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.

2. 또, 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.

3. 위 과정을 반복한다.

 

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited


def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

 

[  BFS  ]

현재 인접한 노드를 먼저 방문한다.

1. 루트 노드를 큐에 넣는다.

2. 현재 큐의 노드를 빼서 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가 비면 탐색을 종료한다.

 

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited


assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

 

[ DFS vs BFS ]

DFS는 탐색하는 원소를 최대한 깊게 따라가야 한다.

이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. -> 그래서 스택을 사용함!

 

BFS는 현재 인접한 노드를 먼저 방문해야 한다.

즉, 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. -> 큐를 이용!

 

[ 백트래킹 ]

필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법