![]()
DP란?DP란, Dynamic Programming의 약자로, 동적 계획법이라고합니다. DP가 어떤 단어의 약자이고 그것이 어떻게 불리는지에 대해서는 알겠는데, 너무 추상적이고 뭐가 동적으로 계획된다는 건지 이해가 되지 않을 수 있습니다. DP는 큰 문제를 조그만한 문제로 나누어, 답을 구하고 계산된 결과를 기록하고 재활용하며, 문제의 답을 찾아가는 방식으로 진행됩니다. 이런 구조적인 특성상 계산에서 나온 결과를 저장하기 위해서는 중간 계산 결과를 저장하기 위한 추가적인 메모리를 필요로 하게 됩니다.최근 한국에서 코딩테스트 시험을 볼 때, 시간 복잡도에 대해서는 다소 타이트하게 주어질 수 있지만, 공간 복잡도에 대해서는 상당히 널널하게 주는 편이므로, 어떤 문제를 풀어나갈 때, 다른 방법이 존재하더라도..
![]()
개념 - BFS란?BFS란, Breadth-First Search의 약자로 너비 우선 탐색을 의미합니다.BFS는 그래프 구조에서 사용하는 탐색 알고리즘 중 하나로 루트노드부터 리프노드까지 동일한 레벨들의 노드들을 탐색을 진행하는 알고리즘이다. 루트노드에서 간선을 타고, 다음 노드로 이동하게 된다면, 동일한 거리만큼 떨어져있는 노드들을 전부 조사하고, 해당 노드들의 방문 여부를 처리하면서 탐색을 진행하는 알고리즘입니다. 순서1. 특정 노드 혹은 루트 노드에서 시작2. 해당 노드로부터 동일한 거리(레벨)에 떨어져 있는 노드 조사 후 큐에 삽입3. 반복문을 통해 해당 노드들에서 갈 수 있는 노드들이 있는지 조사4. 모든 노드들을 방문했다면 종료 이러한 순서대로 BFS를 진행한다. 하지만 이렇게만 보면 정확하..
![]()
개념 - DFS란?DFS란, Depth-First Search의 약자로 깊이 우선 탐색을 의미합니다. DFS는 그래프 구조에서 사용하는 알고리즘 중 하나로 루트노드부터 탐색하는 것이 아닌 가장 깊은 곳에 있는 리프(Leaf)노드노드부터 탐색을 진행하는 탐색 알고리즘이다. 루트노드에서 다음 브랜치로 넘어가기 전에 완전하게 탐색하는 방법이다 1. 시작 노드 혹은 루트 노드 A에서 시작합니다.2. 시작 노드 A와 인접한 노드 B를 찾는다. 이때, 방문 여부를 설정한다.3. A에 인접한 다른 노드가 아닌, 다시 B에서 인접한 노드를 찾는다.4. 마지막 노드까지 순회했다면, 해당 노드의 상위 노드로 간다5. 위의 과정을 반복하면서 모든 노드를 순회한다.특징재귀적이다스스로를 호출하는 순환 알고리즘이다.방문했던 곳..
![]()
개요 - Heap이란?Heap이란 Heap Tree 구조를 가지며, 여러 개의 값중에서, 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진트리 구조이다. heap이라는 영단어 자체가 '어떤 것을 차곡차곡 쌓아올린 더미'라는 뜻이다. 이러한 이유로, 힙은 항상 완전 이진 트리 ..
