다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 다익스트라 알고리즘을 구현하는 과정은 다음과 같다. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음에는 시작 정점을 방문한다.) 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 프로그래머스의 배달 문제의 그래프를 예시로 다익스트라 알고리즘을 설명해보겠다. 1번 정점을 시작 정점으로 잡고 1번 정점에서 방문할 수 있는 각 정점까지의 거리를 표시한다. 1번 정점에서 방문할 수 없는 정점은 INF(무한대)로 표시해둔다. 방문하지 않은 정점 중 가장 거리가 짧은 2번 정점을 방문한다. 1번 정점에서 2번 정..

힙(heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙은 다음과 같은 힙 속성을 만족한다. A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있는데, 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 한다. 키 값의 대소관계는 오직 부모노드와 자신노드 사이에만 성립하며 형제 노드간에는 대소관계가 정해지지 않는다. 각 노드의 자식노드 최대 개수는 힙의 종류에 따라 다르나 일반적으로 자식노드의 개수가 최대 2개인 이진 힙을 사용한다. 힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는..

BFS (너비 우선 탐색) BFS는 탐색을 할 때 너비를 우선으로 수행하는 그래프 탐색 알고리즘이다. 너비 우선 탐색은 최단 경로를 찾아야 할 때 많이 사용한다. 재귀 함수로 구현하지 않고 큐(Queue)로 주로 구현한다. BFS를 그래프를 저장 할 때는 인접 행렬과 인접 리스트로 구현하는 방법이 있는데 인접 행렬은 시간 복잡도가 O(V^2) (V는 정점의 수), 인접 리스트는 O(V + E) (V는 정점, E는 간선) 이라 인접 리스트가 더 빠르기 때문에 주로 인접 리스트로 저장한다. C++ BFS 구현 bool visited[101] = {}; void bfs(vector graph[], int start) { queue q; q.push(start); visited[start] = true; whi..

이진 탐색 Lower Bound, Upper Bound 이진 탐색은 찾는 값이 존재하는지 탐색하여 하나의 값을 찾는 것이라면 lower bound와 upper bound는 이진 탐색에서 살짝 변형시킨 방식으로 중복된 값이나 상한, 하한선을 찾는 경우 등의 다양한 방식으로 활용할 수 있다. 이진탐색 포스팅 Lower Bound Lower Bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾는다. [1, 2, 3, 3, 3, 4, 5] 라는 리스트에서 3을 타겟으로 Lower Bound를 찾으면 결과로 나오는 인덱스는 3이 처음 등장하는 2가 된다. Upper Bound Upper Bound는 타겟보다 큰 값이 나오는 처음 위치를 찾는다. 위와 같은 [1, 2, 3, 3, 3, 4, 5] 의 리스트에..

분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다. 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다. 분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다. DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다. 공통점 문제를 가장 작은 단위가 될 때까지 나눠서 분할함 차이점 동적 계획법 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법) 분할 정복 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함) 분할 정복을 설계하는 방법 1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문..

그래프 탐색 그래프 탐색 알고리즘 중 대표적으로 사용되는 DFS에 대해 알아보자. 그래프 탐색이란 그래프 내 임의의 한 정점에서 시작해서 모든 정점들을 탐색하는 것을 말한다. DFS는 현재 정점에서 갈 수 있는 정점까지 들어가면서 탐색하는 것이고, 또 다른 대표적인 그래프 탐색 기법인 BFS는 현재 정점에 연결되어 있는 가까운 정점들부터 차례대로 탐색한다. DFS (Depth-First Search) DFS는 깊이 우선 탐색 이라고도 부르는 방법으로 선택한 정점에서 가장 깊게 들어갈 수 있는 부분까지 들어가며 탐색하는 방법이다. DFS 구현 방법 스택 재귀함수 DFS의 장점과 단점 장점 현 경로상의 노드들만을 기억하므로 저장공간을 적게 사용한다. 목표노드가 깊은 단계에 있는 경우 해를 빠르게 구할 수 있..

bool binarySearch(vector &list, int findNum) { int start = 0; int end = list.size() - 1; while (start