4Legs_Archives

[서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘 : 4legs-study.tistory.com/21) 하지만, 다익스트라 알고리즘에는 그래프에 음의 가중치가 없어야 한다는 조건이 있었다. 왜일까? 음의 가중치를 가진 간선이 존재한다면, 힙에서 한 정점을 꺼냈을 때 그 가중치 합이 해당 정점에 대한 최소 가중치 합임을 보장할 수 없기 때문이다. 다익스트라 알고리즘은 힙에서 꺼낸 정점에 대해 꺼낸 순간의 가중치 합을 최소로 고정한 후 (음의 가중치가 없다면 다른 어떤 간선을 추가로 지나오더라도 현재 가중치 합보다 작아질 수 없으므로) 다른 정점에 대해 해당 과정을 반복하는데, 음의 가중치를 가진..

[서론] 그래프 최단경로 알고리즘으로, 꽤 자주 보이는 유형이다. 다익스트라 알고리즘은 음수가 아닌 가중치가 있는 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. [동작 원리] 다음과 같은 그래프에서, 1번 노드와 나머지 각 노드 간의 최단거리를 다익스트라 알고리즘을 통해 구해보자. 다익스트라 알고리즘은 위와 같은 상태에서 시작한다. 테이블의 값은 출발 노드로부터 해당 노드까지의 최소 가중치 합을 의미하며, 테이블의 값이 INF(무한대)라면 해당 노드와 연결되어 있지 않다는 의미이다. 아직은 1번 노드만 확인했으므로, 다른 모든 노드에 대해 INF가 기록된 모습이다. 출발 노드로부터 인접한 각 노드에 대해 테이블에 거리를 기록한다. 예시 그래프에서는 출발 노드 1이 2, 3..

[서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 이용한 방법일 것이다. Sk를 Arr[0] ~ Arr[k] 까지의 모든 원소의 합이라 정의할 때, 누적합을 이용해, 구간 (i, j)의 구간합을 Sj - S(i - 1) 로 O(1)에 구할 수 있다. 이 때, Arr의 원소 중 일부가 변경된다면 어떻게 될까? 올바른 구간합을 구하기 위해서는, 누적합을 저장해 놓은 배열을 다시 갱신해야 할 것이다. 배열의 크기가 N이고, 배열값의 변경이 M회 일어날 때 Worst Case에 시간복잡도는 O(NM)이 된다. 이는 N, M의 크기가 어느 정도 커지면 시간 효율..

[서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를 탐색하는 것은 결과적으로 같기 때문이다. 기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자. BFS (Breadth-First Search, 너비 우선 탐색) ■ 개념 그래프를 탐색할 때, 다음 level의 모든 노드를 먼저 방문하여 탐색하는 기법이다. 즉, 인접한 모든 노드를 우선으로 방문하여 탐색하는 방법이라 할 수 있다. ■ 동작 원리 1번 노드에서 출발하는 다음과 같은 그래프에서 BFS가 어떻게 작동하는지 살펴보자. - 1번 노드의 인접 노드인 2, 5, 7번 노드를 순서대로 방문한다. - 2번 노드의 자식 노드..

[서론] DFS는 BFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. 기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자. DFS (Depth-First Search, 깊이 우선 탐색) ■ 개념 그래프를 탐색할 때, 더 높은 level의 노드를 먼저 방문하여 탐색하는 기법이다. Tree에서 Preorder 순회, 백트래킹과 유사한 점을 보인다. 쉽게 말하자면, 갈 수 있는 한 일단 최대로 깊게 들어가는 방법이라 할 수 있다. ■ 동작 원리 다음과 같은 그래프에서 DFS가 어떻게 작동하는지 살펴보자. 위와 같은 그래프에서 1번 노드를 시작으로 각 노드를 탐색하는 상황을 보자. (단, 같은 level의 노드가 여러 개 있다면 낮은 숫자를 먼저 방문한다) DFS는 일단 갈 수 있..

[서론] 스위치 4개가 있다고 생각해 보자. 이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 대한 bool 값을 지정해 bool의 배열 형태로 나타내면 될 것이다. 하지만 스위치가 백만 개, 천만 개라면 어떻게 스위치들의 상태를 나타낼 수 있을까? 또한, 특정 스위치가 켜져 있는지 확인하려면 어떻게 해야 할까? 이런 경우에도 앞서 말한 4개의 스위치가 있는 상황처럼 bool 배열을 이용해서 확인할 수는 있지만, 차지하는 메모리가 너무 많고 비효율적이다. [개념] 전체 원소 집합 중, 각 원소들을 on/off 형태로 구분할 수 있을 때, 특정 원소들의 포함 여부를 한 번에 나타내고 싶은 경우 사용한다. 예를 들..