항해 3주차 WIL

오늘의 과제는 그래프, BFS, DFS, 트리 중 최소 2개.

 

그저 한 주 배웠던걸 다시 되짚는건데... 왜... 난 항상 일요일마다 과제에 쫓기는가...

답 = 배울 때 제대로 안 배워서 그러함

 

 

1. 그래프

연결돼 있는 정점과 정점 간의 관계를 표현할 수 있는 자료구조. 그래프는 연결 관계에 초점이 맞춰져 있다.

그래프는 유방향 그래프 Directed Graph와 무방향 그래프 Undirected Graph가 있다. 유방향 그래프는 방향이 있는 간선을 갖고, 각 간선은 한 방향으로만 진행할 수 있는 단방향 관계를 나타낸다. 무방향 그래프는 말 그대로 방향이 없는 간선을 갖는다.

 

1) 그래프에서 사용되는 용어 :

노드 Node - 연결관계를 가진 각 데이터. 정점 Vertex 라고도 한다.

간선 Edge - 노드 간의 관계를 표시한 선.

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

 

2) 그래프의 표현 방법 :

인접행렬 Adjacency Matrix - 2차원 배열로 그래프의 연결관계를 표현

인접리스트 Adjacency List - 링크드 리스트로 그래프의 연결관계를 표현

이 두 방식의 차이는 시간과 공간이다. 인접행렬로 표현하면 0과 1이 연결되었는지 여부를 바로 알 수 있다. 하지만 모든 조합의 연결 여부를 저장하기 때문에 O(노드^2)만큼의 공간을 사용한다.

인접리스트로 표현하면 연결여부를 바로 알 수는 없고, 각 리스트를 돌아봐야 한다. 따라서 연결 여부를 알기 위해서는 최대 O(간선) 만큼의 시간이 필요하다. 대신 모든 조합의 연결 여부를 저장할 필요는 없으니 공간은 O(노드+간선) 만큼만 사용하면 된다.

 

 

 

 

2. DFS

DFS는 Depth First Search, 깊이 우선 탐색 방식이다. 갈 수 있는 만큼 계속해서 탐색하다가 더이상 갈 수 없게 되면 다른 방향을 다시 탐색하는 구조이다.

DFS 실행 과정:

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

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

- 위 과정을 반복한다.

테스트코드

from dfs_bfs.prac import dfs_recursive, dfs_stack

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

구현코드

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

 

 

 

 

3. BFS

BFS는 Breadth First Search, 너비 우선 탐색 방식이다. BFS는 현재 인접한 노드 먼저 방문한다.

* DFS와 BFS가 다른 점 : DFS는 탐색하는 원소를 최대한 깊게 따라간다. 이를 구현하기 위해 스택을 사용해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색했다.

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

-> 가장 처음에 넣은 노드를 탐색하려면 큐를 사용하면 된다.

DFS 구현 과정 :

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

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

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

- 2번째부터 반복한다.

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

코드 구현

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]

 

 

 

4. 트리

트리는 나무를 거꾸로 뒤집어 놓은 형태의 비선형 자료구조다. 비선형 구조는 선형구조와 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

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

비선형 자료구조를 사용하는 이유는, 선형 자료구조로는 표현할 수 없는 상황 등 효율적이지 못할 때가 있기 때문이다. (참고 : https://luv-n-interest.tistory.com/980)

 

트리의 구성 및 용어들 :

Node : 트리에서 데이터를 저장하는 기본 요소

Root Node : 트리 맨 위에 있는 노드 (시작 부분)

Level : 최상위 노드를 Level 0으로 했을 때, 하위 Branch로 연결된 노드의 깊이를 나타낸다

Parent Node : 부모노드. 어떤 노드의 상위 레벨에 연결된 노드

Child Node : 자식노드. 어떤 노드의 하위 레벨에 연결된 노드

Leaf Node(Terminal Node) : 자식노드가 하나도 없는 노드.

Sibling : 동일한 부모노드를 가진 노드

Depth : 트리에서 노드가 가질 수 있는 최대 레벨

 

 

 

 

 

그리고 아래는 지난주에 하고 싶었지만 못했던 정리 일부. 오늘의 과제도 있기 때문에 간단하게 정리하기.

 

1. 배열 (흔히 array라고 하는데 이건 c언어의 경우고 파이썬에선 list가 이 역할을 한다)

- index로 임의의 원소를 접근.

- 빈 배열 []도 연산자로 취급한다.

- 삽입 연산자 (append, insert)

- 삭제 연산자 (pop, remove)

 

2. 스택 stack

- 제한된 접근(삽입 push, 삭제 pop)만 허용한다. 어느 자료구조든 기본적으로 삽입과 제거, 경우에 따라선 탐색이 제공되어야 하는데, 스택은 이 기본적인 연산들만 가능하다.

- 후입후출 LIFO(Last In First Out) 방식

- 리스트를 옆으로 눕힌 모양을 생각하면 된다. 다만 리스트와 다르게 중간에 삭제, 삽입 등 중간을 수정할 수는 없다.

- 연산이 제한되기 때문에 중간에 있는 값들이 실수로 지워지거나, 다른 값으로 바뀔 위험이 적다.

- 값들을 저장하는 용도로 간접적으로 리스트를 사용한다.

class Stack:
	def __init__(self): # 생성함수
    	self.items = []
    
    def push(self, value):
    	self.items.append(value)
        
    def pop(self):
    	try: # try/except 구문을 이용해 에러를 우아하게 처리할 수 있다
        	return self.items.pop()
        except IndexError:
        	print ("Stack is empty.")
    
    def top(self): # pop과 달리 마지막에 push 한 값을 삭제하지 않고 확인만 한다
    	try:
        	return self.items[-1]
        except IndexError:
        	print ("Stack is empty.")
        
    def __len__(self):
    	return len(self.items)

 

 

 

 

 

여기서부터는 생각 정리하기

 

팀이 바뀌었다. 이번 팀은 적응하는데 시간이 조금 걸릴 듯 하다. 사람들은 좋은 사람들인데, 다들 굉장히 조용하시다. 최소한의 필요한 의사소통만 하고 할일에 좀 더 집중하고 싶어하시는 스타일인 것 같아서 그건 정말 너무너무 좋고 존중해드리고 싶은데... 저 최소한의 필요한 의사소통을 어떻게 이끌어내야 하는건지 조금 난감하긴 하다.

 

다음주엔 팀원분들과 조금 더 친해졌으면 좋겠다. 말은 많이 안해도 좋지만 어색한 분위기는 좀 없애고 싶다;

 

아. 그리고 조만간 깃허브로 이사가야겠다. 이런 사담섞인 TIL은 깃허브에 올리고, 티스토리엔 남들과 나누면 좋을, 공부하다 알아낸 정보들이나 에러들을 올리는 것이 좋다는 조언을 받았다. 깃허브에 코드가 아닌 이런 일반 글은 어떻게 올리는건지 사용법을 조금 찾아봐야겠다.