BlogWhatever

Dijkstra's Algorithm 네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra의 이름을 딴 Dijkstra의 알고리즘은 그래프 순회 알고리즘으로 음이 아닌 간선 가중치를 갖는 그래프에서 노드들 사이의 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 방문한 노드들의 집합과 소스 노드로부터 다른 모든 노드들에 대한 잠정적인 거리를 계속 업데이트 하면서 최단 거리를 찾는 과정이 필요합니다.처음에는 소스 노드까지의 거리를 0으로 설정하고, 다른 모든 노드까지의 거리를 무한대로 설정한다.각 단계에서 알고리즘은 아직 방문하지 않은 소스 노드로부터 잠정 거리가 가장 작은 노드를 선택한다.그 다음 선택된 노드의 모든 이웃 노드를 검사하고 더 짧은 경로가 발견되면 그들의 잠정 거리를 업데이트한다.이 프..

BFS : Breadth-First Search 너비 우선 탐색(Depth First Search) 에 대해서 알아보겠습니다. 위 그래프와 노드 번호는 너비 우선 검색을 Root 로 부터 시작하는 경우의 방문 순서를 보여주고 있습니다. 각 노드에서 다음 단계(하위)의 노드로 이동하기 전에 노드의 모든 이웃을 방문하여 그래프를 탐색합니다.(Level-order) 방문하는 도중에 만나는 새로운 Node 가 있더라도 먼저 확인한 모든 이웃 Node를 먼저 방문하기 위해서는 선입선출(FIFO) 처리가 필요하게 되고, 이것은 BFS 는 Queue 와 같은 FIFO 를 처리할 수 있는 자료 구조를 사용하게 됨을 의미합니다. Implementation 위에서 언급했듯이 BFS 에서는 Queue 를 사용하게 됩니다. ..

DFS : Depth-First Search 깊이 우선 탐색(Depth First Search) 에 대해서 알아보겠습니다. 위 그래프와 노드 번호는 깊이 우선 검색을 Root 로 부터 시작하는 경우의 방문 순서를 보여주고 있습니다. Leaf 노드(방문하지 않은 이웃이 없는 노드)를 만나거나 목표 상태에 도달하면 이전 노드로 역추적하여 다른 방문하지 않은 분기를 탐색합니다.(Preorder) 방문하는 도중에 만나는 새로운 Node 의 하위 후손을 먼저 방문하기 위해서는 후입선출(LIFO) 처리가 필요하게 되고, 이것은 DFS 는 재귀적인 호출 또는 Stack 을 사용해서 탐색하게 됨을 의미합니다. 즉, 각 Node 를 만나서 하위 자식 Node 정보를 추가하고, 추가한 하위 자식 Node 부터 검색하는 것..

Backtracking (되추적) 미로와 같이 알 수 없는 곳에서 빠져나오는 가장 단순한 방법은 한쪽 방향으로 계속 탐색하면서 모든 길과 방향을 찾아보는 것입니다. 백트래킹(Backtracking) 은 그래프 또는 트리 등의 자료 구조에서 순서대로 방문해보고 원하는 결과가 나오는지 확인하고 원래 위치로 다시 돌아오는 방법을 의미합니다. 단순하게 모든 데이터를 검색하는 것을 맹목적 탐색(blind search)이라고 부를 수도 있겠지만, 특정 선택이 타당하지 않거나 결실이 없는 것으로 판명될 때 취소후 원래 위치로 복귀하여 다음 순서를 검색하는 방법으로, 다양한 경로(또는 경우의 수)에서 찾고자 하는 문제를 해결하는 데 사용되는 일반적인 알고리즘 기법입니다. BFS(Breadth-First Search),..

Update 세그먼트 트리 이번에는 세그먼트 트리에 대한 응용편입니다. 이미 구성된 세그먼트 트리에서 특정 Node 의 값을 업데이트 하는 방법과 이 방법에서 반복되는 부분을 제거하여 빠르게 업데이트 하는 방법까지 살펴보겠습니다. Data Sample 다음과 같은 Data를 정의하고 Segment Tree 를 구성한 후, 특정 Node 값을 변경해보겠습니다. const int MAX = 1000; const int N = 10; // Segment Tree : Leaf is update with _data[] int tree[MAX]; int _data[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 }; Algorithm 1. 특정 Node 의 값을 업데이트 하기 위해서는 해..

여기에서는 세그먼트 트리에 대한 구현에 대한 설명을 하겠습니다. 재귀적인 방법으로 구간 연산과 함께 트리를 구성(build tree) 하고 원하는 구간의 값을 쿼리(get data) 하는 구현 방법을 설명합니다. Data Sample 다음과 같은 Data를 정의하고 Segment Tree 를 구성한 후, 일부 구간의 값을 가져오는 예입니다. const int MAX = 1000; const int N = 10; // Segment Tree : Leaf is update with _data[] int tree[MAX]; int _data[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 }; #1 : build_tree : 트리 구성 leaf node 까지 도달한 경우 데이터를 할..

이전의 포스팅에서 분할 정복(Divide & Conquer)과 이진 검색(Binary Search)에 대한 내용을 소개했는데, 이 개념을 응용하여 구간 연산을 효율적으로 할 수 있도록 해주는 세그먼트 트리를 소개합니다. 세그먼트 트리 ( Segment Tree ) Segment Tree는 효율적으로 구간 쿼리 연산을 수행하기 위한 자료 구조이며, 다양한 알고리즘 문제나 데이터 구조에 유용하게 사용될 수 있는 강력한 도구입니다. 주로 배열이나 리스트와 같은 선형 구조에서 구간에 대한 쿼리를 빠르게 처리할 때 사용됩니다. 예를 들면, 배열의 특정 구간의 합을 구하거나 최솟값, 최댓값을 찾는 등의 연산을 빠르게 수행할 수 있습니다. 연산을 빠르게 수행할 수 있는 이유는 구간별 필요한 연산을 미리 해두고 결과만..

이진 검색(Binary Search) 분할 정복(Divide and Conquer)식 문제 해결방법의 대표적인 알고리즘의 하나 분할(Divide) : 문제를 작은 부분으로 나눈다. 정복(Conquer) : 나누어진 작은 문제를 해결한다. 그리고 해결된 문제들을 모아 최종 해답을 모은다. 정렬된 데이터를 중간값을 기준으로 2개의 영역으로 나누고 값의 범위에 따라 검색할 영역만 선택하여 검색한다. 선택적이므로 불필요한 검색이 줄어들며, 한번 영역을 선택할 때 마다 확인해야할 데이터가 2^n 만큼 줄어든다. 이로 인해 𝑂(log n) 로 표현할 수 있는 로그 시간의 시간 복잡도로 정의될 수 있고, 데이터의 양이 많아져도 성능의 큰 변화가 없는 장점을 가지게 됩니다. 장점 : 성능과 단순한 구현 단점 : 데이터..

시간 복잡도 Time Complexity (시간 복잡도) 는 알고리즘의 시간적인 성능을 비교하기 위한 표현 방법입니다. Time complexity - Wikipedia From Wikipedia, the free encyclopedia Estimate of time taken for running an algorithm Graphs of functions commonly used in the analysis of algorithms, showing the number of operations N as the result of input size n for each function In computer science, t en.wikipedia.org 시간 복잡도를 표현하기 위한 방법은 다양하지만 대표적..

순차 검색(Sequential Search)은 가장 기본적인 검색 방법으로 주어진 데이터에서 순차적으로 찾고자 하는 값이 나올때까지 루프를 반복하는 방식입니다. 이 알고리즘으로 키(특정값)를 찾기 위한 검색 횟수는 항목의 위치에 따라 다르지만 최악의 경우에는 data 의 크기(n) 만큼 검색해야 합니다. 장점 : 구현이 단순하다. 단점 : 찾아야 할 Data 범위가 크고, 키에 대한 위치정보가 없다면 모두 확인해야 한다.(비효율적) Algorithm 1. 입력 인수 n : 입력 Data Array 의 Size Data[ ] : Key 값을 검색할 Data x : 검색해야 하는 Key 값 2. 출력 Key 값이 존재하는 위치 index 3. 수행 절차 반복 loop (for문 또는 while) 를 사용하여..