IT 방랑기

그래프가 주어졌을 때 시작 노드에서부터 종료 시점까지 최단 경로를 구할때 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘은 반드시 음수 사이클이 존재하지 않아야 한다. 만약 음수 사이클이 발생할 수 있다만 벨만 포드 알고리즘을 이용해야 한다. 다익스트라는 시작점으로부터 cost에 대한 min heap을 이용하여 가장 cost가 적은 순서대로 계속해서 길을 찾아보며 만약 도착 노드를 발견하는 순간 종료된다. 코드를 보자. 이 소스코드는 백준 최단 경로를 기반으로 하고 있다. #include #include #include #include using namespace std; typedef pair pii; #define ff first #define ss second #define mp(x, y) ma..

알고리즘에서 가장 기본이 되는 탐색 알고리즘인 DFS와 BFS에 대하여 정리한다. DFS는 깊이 우선 탐색으로 그래프가 주어졌을 때 함수 스택을 이용하여 현재 노드와 연결된 노드로 탐색하며, BFS는 너비 우선 탐색으로 큐를 이용하여 현재 노드와 연결된 노드들을 탐색한 다음 연결된 노드들에 연결된 노드들을 차례로 탐색한다. 그래프 V와 E가 주어졌을 때 배열으로 노드를 방문하였는 여부를 저장하여, 다시금 방문하지 않도록 강제한다. 그래프가 아래와 같이 주어졌다고 하자. A - B1 - C1 - B2 - C2 - B3 - C3 DFS는 A에 연결된 B1노드, 그리고 B1노드에 연결된 C1노드를 바로 탐색하기 때문에 트리의 순회에 자주 이용된다. 반면 BFS는 A노드에 연결된 모든 노드 B1, B2, B3를..

구간합을 반복적으로 빠르게 계산하기 위해서 세그먼트 트리와 펜윅 트리를 이용한다. 세그먼트 트리와 펜윅 트리는 원래의 데이터 값을 저장하는 방법이 아니라, 이름에서 알 수 있듯 데이터를 구간별로 저장하는 형식을 가진다. 간단하게 말하여 부분합을 위하여 i번째까지의 데이터를 모두 합한 값을 유지하고 있다고 보면 된다. 세그먼트 트리는 리프노드에는 원래의 데이터를 그리고 그 부모 노드는 아래의 리프 노드들의 합을 저장하고 있다고 보면된다. 이러한 특징을 바탕으로 특정 구간의 값을 찾는 행위는 O(logN) 그리고 값을 변경 하는 행위 또한 O(lgN)만에 수행할 수 있다. 세그먼트 트리의 경우 필요 메모리량이 복잡하게 계산된다. Full binary tree의 경우 N이 2의 제곱꼴이면 2*N-1개의 노드가..

최소 신장 트리(MST, Minimum Spanning Tree)란? - 가중치가 있는 무향 그래프가 주어졌을 때 모든 노드를 연결하면서 간선의 가중치 합이 최소인 신장 트리를 뜻한다. 최소 신장 트리의 특징 1) 가중치의 합이 최소 2) N개의 노드에 대하여 N-1개의 간선으로 구성 3) 사이클이 존재하지 않아야 함 최소 신장 트리를 구하는 방법 그래프가 주어졌을 때 우리는 어떻게 최소 신장 트리를 찾을 수 있을까? 간단한 방법으로 가중치가 작은 간선을 선택할 수 있는지 확인하여 포함하는 Greedy 방식으로 MST를 구할 수 있다. * 가중치가 작은 순서대로 간선을 탐색하면서 Spanning Tree의 조건에 부합하는 간선만 선택 * 간선을 선택시에 사이클이 있는지 여부를 판단해서 해당 간선을 연결할..

트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다. 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다. 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다. 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 ..

정렬과 더블어 따라오는 탐색 중 바이너리 서치에 대하여 설명하고, 이를 구현한 코드를 포스팅한다. 탐색은 요구에 맞는 데이터를 찾는 과정으로, 실무나 프로젝트 또는 알고리즘 문제를 풀어본 사람들은 잘 알겠지만 가장 빈번하게 일어난다. 따라서 이러한 탐색에 필요한 시간 복잡도를 줄이므로써, 더욱 효율적인 프로그램을 작성할 수 있게 한다. 일반적으로 전체 탐색을 통하여 검색을 하는 경우 N개의 데이터에 대하여 O(N)의 시간 복잡도를 가진다. 하지만 정렬된 데이터에 대하여 키에 대한 값을 탐색하는 경우, 이를 O(lgN)으로 줄일 수 있으며, 사실상 lgN은 상수에 근접하므로 O(N) 탐색에 비하여 더욱 효율적이고 같은 시간내 다양한 작업을 할 수 있다. 바이너리 서치는 정렬된 데이터에서 탐색하는 크기를 반..

시간 복잡도 계산, Master's theorem / 마스터 정리 1. 시간 복잡도 시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의미한다. 시간 복잡도를 표현하는 방법은 총 3가지가 있다. 최선 평균 최악 간단한 정리는 아래의 포스팅을 읽어보자. [알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법 2. 시간 복잡도 계산 시간 복잡도 함수 `T(n)`은 일반적으로 재귀 형태의 수식으로 주어지는데, `n=1`까지 모든 항을 구해서 그 합을 구하면 그 값이 시간복잡도가 된다. 예를 들어 가장 간단한 시간 복잡도 함수를 보면, `T(n) = T(n-1) + n` 이 `T(n)` 함수는 1회 실행에 n번의 기본 연산을 수행하며,..

1. 시간 복잡도 시간 복잡도 (Time complexity)는 컴퓨터 공학에서 사용되는 알고리즘을 입력의 크기에 관계해서 나타내는 방법이다. 왜 절대 시간을 쓰지 않을까? 절대시간은 사실 컴퓨터 환경 의존성이 심하다. 예를 들어, A 알고리즘은 B 컴퓨터에서 1초동안 100개의 입력을 처리할 수 있지만, C 컴퓨터에서는 10개만 해결할 수 있다면, 이 알고리즘에 대한 절대적 평가가 힘들 수 있다. 따라서 절대 시간이 아닌, 입력의 크기 n에 따라서 알고리즘 동작까지 필요한 시간을 n에 대한 수식으로 나타내는 것이다. 2. Basic Operation 시간 복잡도를 나타낼 때, 측정하는 단위이다. "기본연산"이라고도 하며, 입력의 크기에 비례해서 나타내는 경향을 보인다. 예를 들어 아래의 코드를 실행한다..

1. Convex hull Convex Hull이란, 점들로 구성된 Set을 모두 포함하는 외각 점들의 집합이다. 아래의 그림을 보자. 출처 : 위키피디아 검은 점들로 구성된 집합 `S`에서 어느 점을 선택하더라도, 파란색 선안에 포함되는 것을 알 수 있다. 이 파란색 선을 어떻게 찾아야 할까? 2. How to find convex hull Convex Hull을 찾는 가장 간단한 방법은 각 점마다 모든 점들을 순회해서 가장 외각의 것을 선택하는 것이다. 하지만 이렇게 접근한다면, 결국 `O(n^2)`이 되어서 원하는 작업을 원할히 할 수 없다. 사실 모든 점을 순회한다는 것은 가장 외각의 점을 찾기 위함이다. 따라서 이 부분을 더욱 쉽게 만들어 준어야 한다. 그런 방법들 중에서도, 외적을 이용한 `C..

컴퓨터 알고리즘에서 플로이드 혹은 플로이드 와샬 알고리즘은 임의의 시작점과 종료점간의 최단 경로를 구하는 알고리즘이다. [다익스트라]와는 다르게 모든 정점에 대하여 한번에 경로를 구할 수 있는 장점이 있다. 하지만 최단 경로를 구하기 위해서는 정점의 개수 N에 대하여 O(N^3)의 시간 복잡도를 가지게 되므로, 실제 문제에 적용할 수 있는 N의 크기는 1초 1억(1e8) 대비하여 N이 100정도이다. 만약 N j 경로중 가까운 것을 최단 경로로 저장한다. 코드의 경우 아래와 같이 나타나게 된다. for(int k = 1; k