나의 개발일지 TIL(Today I learned) - 자료구조와 알고리즘(트리, 힙, 그래프, BFS, DFS, 타임어택 문제풀기)

Today I learned

• 트리 (Tree)
• 힙 (Heap)
• 그래프(Graph)
• DFS
• BFS
• 타입어택 문제풀기

 

트리 (Tree)

트리는 비선형 구조이다

비선형 구조는 선형 구조와 다르게 데이터가 계층적 혹은 망으로 구성되어있다

선형 구조와 비선형 구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다

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

 

아래의 폴더 구조가 대표적인 비선형 구조인 트리 형태의 구조!!

 

트리는 계층형 구조이다 위아래가 구분이 되어 있다

트리에서 나오는 용어들을 정리해보자

Node: 데이터를 저장하는 기본 요소

Root Node: 트리의 맨 위에 있는 Node

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

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

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

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

트리의 종류는 엄청 다양하지만 이진 트리(Binary Tree)와 완전 이진 트리(Complete Binary Tree) 2가지를 학습해보자

이진 트리(Binary Tree)의 특징은 각 Node가 최대 두 개의 Child Node를 가진다

Parent Node의 Child Node가 0개, 1개, 2개만 가지고 있어야 한다

 

완전 이진 트리(Complete Binary Tree)의 특징은 Node를 삽입할 때 최하단 왼쪽 Node부터 차례대로 삽입해야 한다.

트리의 구조를 표현하는 방법은 직접 클래스를 구현하는 방법과 배열로 표현하는 방법이 있다

완전 이진 트리(Complete Binary Tree)를 쓰는 경우는 배열로 표현할 수 있다

최하단 외쪽 Node부터 순서대로 삽입을 하기 때문에 순서대로 배열에 넣으면 완전 이진 트리(Complete Binary Tree)를 배열로 표현할 수 있다

      8      Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다!

현재 인덱스 * 2 --> 왼쪽 자식의 인덱스

현재 인덱스 * 2 + 1 --> 오른쪽 자식의 인덱스

현재 인덱스 // 2 --> 부모의 인덱스

 

이진 트리(Binary Tree)의 높이는 최대로 해봤자 O(log(N))이라고 생각하고 있자!

 

힙 (Heap)

힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조다

힙은 다음과 같이 최댓값을 맨 위로 올릴 수 있고 최솟값도 맨 위로 올릴 수 있다

 

맥스 힙에 원소를 추가하는 코드를 보자

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        # 새노드를 추가한다
        self.items.append(value)

        cur_index = len(self.items) - 1

        # Root Node까지 반복한다
        while cur_index > 1:

            # 새노드를 부모 노드와 비교한다
            parent_index = cur_index // 2
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index

            else:
                break

        return


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!

완전 이진 트리의 최대 높이의 시간 복잡도는 O(log(N))이다 힙의 원소 추가 시간 복잡도도 O(log(N))이다!

 

맥스 힙에 원소를 제거하는 코드를 보자

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        # 새노드를 추가한다
        self.items.append(value)

        cur_index = len(self.items) - 1

        # Root Node까지 반복한다
        while cur_index > 1:

            # 새노드를 부모 노드와 비교한다
            parent_index = cur_index // 2
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index

            else:
                break

    def delete(self):
        # Root Node와 제일 맨 끝 Node와 교체한다
        self.items[1], self.items[-1] = self.items[-1], self.items[1]

        # 맨 끝으로 이동한 Root Node였던 Node를 반환 해야하기 때문에 따로 저장해두고 삭제한다
        answer = self.items.pop()


        cur_index = 1


        # Child Node가 Parent Node보다 크거나 맨 끝에 도달할 때 까지 반복한다
        while cur_index <= len(self.items) - 1:

            # 힙의 형태를 유지하기 위해 맨 끝 Node였던 Root Node를 Child Node들과 비교해서 자리를 바꾼다
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 - 1
            max_index = cur_index

            if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
                max_index = left_child_index

            if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
                max_index = right_child_index

            if max_index == cur_index:
                break

            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index

        return answer


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

힙의 원소 제거 시간 복잡도도 O(log(N))이다!

 

고안된 완전 이진 트리(Complete Binary Tree)라서 완전 이진 트리의 시간 복잡도와 같다

최댓값이나 최솟값을 추가하거나 제거 또는 찾는 알고리즘이 필요하다면 힙을 사용하는 것을 생각하자!

 

그래프(Graph)

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

학습을 했던 비선형 구조는 표현에 초점을 맞추고 선형 구조는 저장과 출력에 초점을 맞췄다

이번 그래프(Graph) 자료구조는 연결 관계에 초점이 맞춰져 있다

 

그래프(Graph)에서 사용되는 용어를 정리해보자

Node(노드): 연결 관계를 가진 각 데이터, 정점(Vertex)이라고도 한다

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

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

            로제 - 사나
             ⎜       
      제니 - 르탄

르탄이는 연결 관계를 가진 데이터, 노드입니다!
르탄과 제니는 간선으로 연결되어 있습니다.
르탄과 로제는 인접 노드 입니다!

그래프는 유방향 그래프와 무방향 그래프 두 가지가 있다

우리는 무방향 그래프에 대해서만 배워보자

 

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

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

 

그래프(Graph)를 표현하는 방법은 두 가지 방법이 있다

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

인접 리스트(Adjacency List): 연결 리스트로 그래프의 연결 관계를 표현한다

 

이 두 방식의 차이는 무엇일까?

시간 VS 공간이다

인접 행렬은 모든 조합의 연결 여부를 저장해야 되기 때문에 O(N^2)만큼의 공간을 사용한다

하지만 배열의 특성으로 연결 여부를 바로 알 수 있다

 

인접 리스트는 연결 여부를 알려면 O(N)만큼의 시간이 걸리지만

모든 조합의 연결 여부를 저장할 필요가 없어서 O(N+M)만큼의 공간을 사용한다

 

DFS(Depth First Search)

자료의 검색, 트리나 그래프를 탐색하는 방법 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해 끝까지 탐색하면

다시 위로 와서 다음을 탐색한다

 

DFS는 왜 필요한가? 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면 모든 경우의 수를 전부 탐색해야 하는 경우도 있다 대표적으로 바둑에서 모든 경우의 수를 찾아서 최적의 수를 출력하기 위해 모든 수를 탐색해야 한다

 

DFS는 깊이를 끝까지 파고드는 것이라 그래프의 최대 깊이만큼의 공간만 요구한다

공간은 적게 쓰지만 최단 경로를 탐색하기는 어렵다

 

재귀함수를 이용해서 DFS를 구현해보자!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


def dfs_recursion(adjacent_graph, cur_node, visited_array):
    # 시작 노드 Root Node 1부터 탐색
    # 현재 방문한 Node를 visited_array에 추가한다
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:

    # 현재 방문한 Node와 인접한 Node 중 방문하지 않은 Node에 방문한다
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)


    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

재귀함수로 구현한 DFS에는 문제가 하나 있다 무한정 깊어지는 노드가 있는 경우 에러가 생길 수 있다

그래서 스택을 이용해 인접한 노드 중 방문하지 않은 노드들을 저장해두고 가장 마지막에 넣은 노드들만 꺼내서 탐색하면 된다 스택을 이용해서 DFS를 구현해보자!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    # 시작 노드를 스택에 넣는다
    stack = [start_node]
    visited = []

    while stack:
        # 현재 스택의 노드를 빼서 visited에 추간한다
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)

    # 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 넣는다

    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

 

BFS(Breadth First Search)

한 노드를 시작으로 인접한 모든 정점들을 우선 방분하는 방법이다 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다

 

BFS는 왜 필요한가? 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면 모든 경우의 수를 전부 탐색해야 하는 경우도 있다 대표적으로 바둑에서 모든 경우의 수를 찾아서 최적의 수를 출력하기 위해 모든 수를 탐색해야 한다

 

BFS 는 최단 경로를 쉽게 찾을 수 있다! 모든 분기되는 수를 다 보고 올 수 있기 때문이다 그러나 모든 분기되는 수를 저장하기 때문에 공간을 많이 써야하고 모든 걸 보고 오다 보니까 시간이 더 오래걸린다

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    # 시작 노드를 큐에 넣는다
    queue = [start_node]
    visited = []
    while queue:
        # 현재 큐의 노드를 뺴서 visited에 추가한다
        current_node = queue.pop(0)
        visited.append(current_node)
        for adj_node in adj_graph[current_node]:
            # 현재 방문한 노드의 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다
            if adj_node not in visited:
                queue.append(adj_node)

    return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

 

타임어택 문제

내일배움캠프에서 타임어택으로 주어진 문제를 푸는 시간을 가졌다

파이썬이나 자바스크립트로 풀면 된다고 해서 자바스크립트로 풀어봤다

프로그래머스

function solution(angle) {
    let answer = 0;
    
    if (angle > 0 && angle < 90) {
        answer = 1;
    } else if (angle === 90) {
        answer = 2;
    } else if (angle > 90 && angle < 180) {
        answer = 3;
    } else if (angle === 180) {
        answer = 4;
    }
    return answer;
}

 

 

프로그래머스

function solution(price) {
    let answer = 0;
    
    if (price >= 500000) {
        price *= 0.8;

    } else if (price >= 300000) {
        price *= 0.9;
        
    } else if (price >= 100000) {
        price *= 0.95;
        
    }
    return Math.floor(price);
}

Math.round와 Math.floor을 고민했다 제한 사항을 읽어보니까 "소수점 이하를 버린 정수를 return합니다."를 보고

소수점을 버리는 floor을 사용했다

 

프로그래머스

function solution(order) {
    let arr = new Array(3).fill(0)
    let answer = 0

    while (order > 0) {
        console.log((order % 10) % 3 === 0);

        if ((order % 10) % 3 === 0) {
            arr[(order % 10) / 3 - 1] += 1;
        }
        order = Math.floor(order / 10);
    }

    for(const a of arr) {
        answer += a;
    }
    return answer;
}

이 문제는 학습했던 배열로 풀어보려고 생각하고 풀었다

Array 메서드의 fill을 이용해서 크기가 3이고 시작부터 끝이 0인 배열을 만들고 3, 6, 9의 숫자들이 나오면

3으로 나눈 값에 -1을 해서 해당 인덱스에 +1 해준다

그리고 3, 6, 9의 나온 개수를 가지고 있는 배열을 전부 합치고 반환해준다

 

프로그래머스

function solution(id_pw, db) {
    const user_db = Object.fromEntries(db);
    let answer = "";

    if (id_pw[0] in user_db) {
        if (id_pw[1] === user_db[id_pw[0]]) {
            answer = "login";
        } else {
            answer = "wrong pw";
        }
    } else {
        answer = "fail";
    }

    return answer;
}

이 문제는 key와 value가 떠올라서 객체로 풀고 싶다는 생각을 하고 객체로 문제를 풀었다

Object.fromEntries() 메서드를 이용해서 key와 value를 쌍으로 가지고 있는 목록을 객체로 반환시킨다
그 후 id_pw[0] 아이디 key가 객체 안에 없으면 fail 있으면 id_pw[1] 비밀번호와 key를 넣어 value를 가져와
비교해서 틀리면 wrong pw 맞으면 login을 반환해준다