BlogWhatever

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),..

전략 패턴(Strategy Pattern) 패턴 요약 전략 패턴은 알고리즘을 별도의 전략 클래스에 캡슐화하고 알고리즘 간의 동적 전환을 허용함으로써 보다 적응 가능하고 유지 관리 가능하며 재사용 가능한 코드를 만들 수 있습니다. 전략 패턴을 이해하고 적용하면 소프트웨어 시스템의 품질과 확장성을 크게 향상시킬 수 있습니다. 사용 시점 같은 기능이지만, 상황에 따라 서로 다른 전략을 가지고 실행되어야 하는 경우에 사용되는 패턴입니다. 객체들이 할 수 있는 동작을 각각의 전략으로 만들어 놓고 동작을 변경해야 한다면 동적으로 전략을 변경하여 동작을 바꾸게 됩니다. 장점 재사용성, OCP 에 위배되지 않고 시스템이 거대해졌을 때 메소드가 중복되는 것을 해결해줄 수 있다. 단점 각각의 알고리즘을 사용하기 위한 전략..

GoF : Gang of Four GoF 는 Gang of Four 라는 의미로 소프트웨어 디자인 패턴의 중요성을 강조하고 알려준 4명의 개발자를 의미합니다. 이 들은 1994년에 출간된 "Design Patterns: Elements of Reusable Object-Oriented Software"라는 책을 통해 많은 기여를 하였습니다. 이 책은 Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides라는 네 명의 개발자들에 의해 쓰여졌으며, 이들은 "GoF"로 알려지게 되었습니다. ※ 직역하면 4인방의 디자인 패턴이라고 할 수 있겠습니다. GoF의 목표는 객체 지향 소프트웨어 개발에서 발생하는 공통적인 문제를 해결하기 위한 디자인 패턴을 정리하고 제시하는..

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 시간 복잡도를 표현하기 위한 방법은 다양하지만 대표적..