Algorithm (24) 썸네일형 리스트형 DFS 심화 (1) - Bipartite (이분 그래프) 이분그래프 (Bipartite) 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 설계: Two-colorability i. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다. ii. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다. iii. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다. 시간복잡도: $ O(V + E) $ 코드 #include #include #include using namespace std; int V, E; vector adj_list[100]; int colored[1000],.. [STL] hash_map, unordered_map [STL] Hash map, Unordered_map hash_map의 자료구조 hash_map의 자료구조는 해시 테이블입니다. 해시 테이블에 자료를 저장할 떄는 key 값을 해시 함수에 대입하여 버킷번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장합니다. 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정합니다. 하지만 이 헤더파일은 STL 표준이 아니므로 사용이 불가한 환경이 있다. 내 맥북에선 컴파일이 안된다.. 대안은 비슷한 unordered_map을 써주면 된다. hash_map을 사용하는 경우 많은 자료를 저장하고, 검색 속도가 빨라야 한다. 빈번하게 자료를 삽입, 삭제 하지 않는다. Unordered_map 사용방법 #include using namespace std; unordered.. Binary Search (이분 탐색) Binary Search (이분 탐색) 설계 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 동작 정렬된 배열에서 이진 탐색(Binary Search) 알고리즘을 사용해 보자 13을 찾는다고 경우를 보자 i. 데이터 집합의 중앙값를 선택한다. ii. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 찾으려는 값(13) < 중앙값(9) 이면, 중앙값(9)의 왼편에서 중.. 나머지 연산 (Modulo Operation) Expression n | a: a는 n의 배수이다. a mod n: a를 n으로 나누었을 때 나머지 값 $ a \equiv b\ mod\ n $ : a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다, 모듈로 합동) $a \equiv b\ mod\ n $ 이면, a - b는 n의 배수이다. -> $ (a - b)\ mod\ n = 0 $ 나머지 연산 법칙 I. 덧셈 (A+B) % M = ((A % M) + (B % M)) % M II. 뺄셈 (A-B) % M = ((A % M) - (B % M) + M) % M 증명 $ 0 \leq A\%M < M $ $ 0 \leq B\%M < M $ 이므로, $ -M < (A\%M - B\%M) < 2M $ 이다. 따라서 양쪽에 M을 곱해줘야 0.. Segment Tree Segment Tree 세그먼트 트리(Segment Tree)란 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법에 관한 것입니다. 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조입니다. Ex) 3번 인덱스에서 8번 인덱스까지의 합을 구하는 방법은? 설계 방법 1. 배열을 이용해 무식하게 구하기 단순히 선형적으로 구하는 방법을 생각해봅시다. 인덱스 3부터 8까지 데이터의 범위를 하나씩 다 더하는 방법. 이러한 방식을 고려했을 때 앞에서 하나씩 더해가므로 데이터의 개수가 N이면 시간 복잡도는 $ O(N) $이 나옵니다. 따라서 구간 합을 N번 구해야한다면 시간복잡도는 $ O(N^2) $ 가 걸리고 이는 매우 불편한 복잡도이기 때문에 더 좋은 알고리즘이 필요합니다... Union-Find 알고리즘 Union Find 상호 배타적 집합, Disjoint-set. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. Find: 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union: 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 구현 초기화 // parent[i] : i 노드의 부모 노드, parent[i] = i 인 경우 i는 루트 노드 int parent[100]; for (int i = 0; i < 100; i++) parent[i] = i; find int find(int x){ if (x == parent[x]) return x; else return find[parent[x]]; } x .. 최단경로 문제 (2) - ASP (플로이드-와샬) 2. All Pairs Shortest Path 모든 정점에 대해 최단경로를 찾으려면 앞서 살펴본 다익스트라, 벨만포드 알고리즘을 정점의 갯수만큼 반복하면 될 것이다. 그렇다면 시간복잡도는 아래와 같다. Dijkstra: $ O (V \log V + E) \to O (V^2 \log V + VE) \because V \to V^2 \ on \ dense \ graph, \ O(V^3) \because E = V^2 $ Bellman-Ford: $ O (V*E) \to O (V^2 *E) \because V \to V^2 \ on \ dense \ graph, \ O(V^4) \because E = V^2 $ 너무 느린것 같다. 그래서 플로이드와 와샬이란 사람이 새로운 알고리즘을 제시했다. Floyd-Wa.. 최단경로 문제 (1) - SSP (다익스트라, 벨만포드) Shortest Path 최단거리 문제 입력으로 그래프의 정보(간선과 정점의 갯수)와 각 간선의 가중치가 주어질 때, 출발점에서 도착점까지의 가는데 드는 최소비용을 구하는 문제 최단경로의 특성 i. Optimal Substructure를 가지고 있다. (Dynamic Programming) distance(n, m): n에서 m까지의 최단거리이라고 정의한다면 distance(1, 4) = distance(1, 2) + distance(2, 3) + distance(3, 4)로 정의할 수 있다. 증명 만약 각 구간 중 하나라도 구해진 최단경로보다 더 짧은 경로가 존재한다고 가정하자. 그러면 전체 최단경로는 더 짧아질 것이고, 기존에 구했던 최단경로는 더이상 최단경로가 아니게 된다. 이에 모순이 발생하므로 .. 이전 1 2 3 다음