트리라는 자료구조를 이용하면 계층 구조의 데이터를 쉽게 표현할 수 있고,
힙이라는 자료구조를 이용하면 최댓값과 최솟값을 쉽게 뽑을 수 있다!
BFS(Breadth First Search) 와 DFS(Depth First Search) 는
탐색의 순서를 깊이 우선으로 할 것인가, 너비 우선으로 할 것인가에 대한 방법입니다.
Dynamic Programming
동적 계획법은 부분 문제의 해를 통해 전체 문제를 해결하는 방법이다!
DP 라고 줄여 말하기도 하는 이 방법론은 알고리즘 문제를 해결하는데 많이 사용되곤 한다.
트리란?
뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조
큐(Queue), 스택(Stack) 은 자료구조에서 선형 구조라고 한다.
선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다.
트리는 비선형 구조이다.
비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있다.
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.
트리는 계층형 구조이다. 위 아래가 구분되어 있다.
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level
트리의 종류
트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 되게 다양한 트리가 존재한다.
이진 트리(Binary Tree) 의 특징은 바로 각 노드가 최대 두 개의 자식을 가진다는 것이다.
완전 이진 트리(Complete Binary Tree) 의 특징은 바로 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것
*이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다.
트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이 이다.
힙이란?
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴 수도 있다!
최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 한다.
맥스 힙의 원소 추가는 만큼의 시간 복잡도를 가진다.
맥스 힙의 원소 삭제는 만큼의 시간 복잡도를 가진다.
그래프란?
연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다.
이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다.
노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 한다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)
그래프는 유방향 그래프와 무방향 그래프 두가지가 있다.
유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.
무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다.
그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있다!
1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현
두 방식의 차이는?
<시간 VS 공간>
인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다.
그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 만큼의 공간을 사용해야 한다.
인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.
따라서 연결되었는지 여부를 알기 위해서 최대 만큼의 시간을 사용해야 한다.
대신 모든 조합의 연결 여부를 저장할 필요가 없으니 만큼의 공간을 사용하면 된다.
DFS & BFS란?
자료의 검색, 트리나 그래프를 탐색하는 하나의 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.
한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다.
왜 DFS & BFS 를 배울까요?
정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는 경우도 있다.
대표적인 예시가 알파고이다. 대국에서 발생하는 모든 수를 계산하고 예측해서 최적의 수를 계산해내기 위해 모든 수를 전부 탐색해야 합니다.
DFS 와 BFS 는 그 탐색하는 순서에서 차이가 있습니다.
DFS 는 끝까지 파고드는 것이고, BFS 는 갈라진 모든 경우의 수를 탐색해보고 오는 것이 차이점이다.
DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 따라서 공간을 적게 쓴다. 그러나 최단 경로를 탐색하기 쉽지 않다.
BFS 는 최단 경로를 쉽게 찾을 수 있다! 모든 분기되는 수를 다 보고 올 수 있어서
그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있다.
-
DFS 구현해보기 - 재귀함수
DFS는 Depth First Search
갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조다. -
DFS 구현해보기 - 스택
DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다.
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드들만 꺼내서 탐색하면 된다.
stack이 빈 순가 DFS가 끝난다.
DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다!
이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 그래서 스택을 사용!
BFS 는 현재 인접한 노드 먼저 방문해야 한다.
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.
Dynamic Programming
피보나치 수열 - 재귀함수
수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다.
동적 계획법(Dynamic Programming)이란?
동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘입니다!
문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있다!
그러나 다른 점은, 그 결과를 기록하고 이용한다는 점이다!
결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고,
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 한다!
아까 예시에서 설명 드렸던 부분에서
각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것을 겹치는 부분 문제,
이미 실험했던 내용은 기록해두고 쓰면 된다는 것을 메모이제이션 이라고 생각하면 된다!
즉, 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데,
이 때 사용하는 방법은 메모이제이션을 이용하면 된다.
