4Legs_Archives

[선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment Tree) [서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 4legs-study.tistory.com 이전에 살펴본 세그먼트 트리에서는 트리 값의 갱신을 하나의 인덱스에 대해서만 진행했다. 예를 들어, 인덱스 5에 해당하는 노드의 값을 변경하기 위해 (1-10) -> (1-5) -> (4-5) -> (5) 구간을 거쳐오는 식이다. 하지만 우리는 한 번에 여러 개의 리프 노드에 대한 갱신이 필요할 수도 있다. 그림과 같이 4-10에 대한 구간을 한 번에 갱신하고 싶거나 할 때 말이다. 하지만 ..

최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 위와 같은 예시 트리 구조에서, 13, 15번 정점의 최소 공통 조상은 5번 정점이 된다. 마찬가지로, 13, 11번 정점의 최소 공통 조상은 1번 정점(Root)이 된다. LCA를 선형 탐색으로 구하기 : O(Depth) 트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까? 가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이다. 즉 Parent[x]를 정점 x의 부모 노드라 할 때, x = Parent[x] 연산을 반복하면 될 것이다. 하지만 구하고자 하는 두 정점의 ..

최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘은 아래 포스팅에서 확인할 수 있다. 최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm) 최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽 4legs-study.tistory.com 프림 알고리즘 (Prim Algorithm) 프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로, 다음과 같이 동작한다. ① 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다. 이제 MST에는 2개의 정점이 포함되어..

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 이번 ..

최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다. 아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다. 이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자. 다이나믹 프로그래밍을 이용한 방법 : O(N^2) 이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다. 하지만 수열에 존재하는 수의 개수가 k개일 때,..

서론 다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다." 이 메신저 프로그램을 통해 내가 A라는 사람과 친구 관계를 맺었다. 다음과 같은 관계도에서, 내가 주황색으로 표시된 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 위처럼 친구 관계를 그래프로 나타낸 후 나를 시작으로 그래프 탐색(DFS, BFS)을 통해 목표 정점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 새로운 친구 관계는 언제나 생겨날 수 있다. 만약 주황색으로 표시된 친구 관계가 새로 생겼다고 할 때, 우리는 주황색 사람과 친구 관계가 될 수 있는지 알기 위해서다시 그래프 탐색을 진행해야 한다. 하지만 이 메신저 프로그램을 사용하는 사용자의..

위상 정렬 (Topological Sort) 방탈출 게임을 한다고 생각해 보자. 우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연결된 3개의 방에 각각 하나씩 숨겨져 있다. 따라서, 메인 룸에서 나가기 위해서는 방 A, B, C 에서 열쇠를 모두 찾아야만 할 것이다. 단 열쇠를 찾는 순서는 영향을 주지 않는다. 또한 열쇠를 3개 모두 찾지 못하면, 다음 단계의 탈출에는 도전할 수 없을 것이다. 따라서 다음 단계의 탈출에 도전하기 위해서는 다음과 같은 순서를 따라야 한다. (A방에서 열쇠를 찾음 - B방에서 열쇠를 찾음 - C방에서 열쇠를 찾음) - 메인 룸의 자물쇠를 모두 푼다 - 메인 룸에서 탈출 후 다음 단계에 도전 (A..

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..

정렬(Sorting)이란? 정렬은 원소(element)들을 일정한 기준을 통해 순서대로 나열하는 것이다. 정렬은 탐색(Search), 병합(Merge) 등 정렬된 상태에서 올바르게 동작하는 다른 알고리즘을 최적화하는 데 중요한 역할을 한다. 정렬 알고리즘은 이러한 정렬을 진행하는 방식을 정의한 알고리즘을 말한다. 이번 포스팅에서는 기본적인 정렬 알고리즘 5가지에 대해 알아보자. 최악의 경우 (Worst case) Worst case는 정렬 알고리즘에 대해 일반적으로 시간복잡도에 대한 최악의 경우는 그 알고리즘이 최대 실행시간으로 동작하는 경우를 말한다. 공간 복잡도에 대해서는 알고리즘이 최대 메모리를 사용하며 동작하는 경우를 의미한다. 안정성 (Stability) 정렬 알고리즘이 안전성을 가진다는 것은 ..

[최단거리 알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) [서론] 최단거리 알고리즘의 마지막, 플로이드-와샬 알고리즘(이하 플로이드 알고리즘)이다. 플로이드 알고리즘은 그래프에서 모든 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 그래서 이전까지의 최단거리 알고리즘과는 다르게 dist배열이 처음부터 2차원 배열 형태이다. 벨만-포드 알고리즘과 마찬가지로 음의 가중치가 존재하는 그래프에서도 사용 가능하며, 음의 사이클이 존재하는 경우 최단거리를 구할 수 없다. [동작 원리] 플로이드 알고리즘은 출발 노드, 도착 노드 그리고 중간 노드를 통해 DP와 유사하게 동작한다. 편의상 이들을 From, To, Mid..