목록PS/Study Note (18)

Doby's Lab

Sparse Table (희소 배열) 연구일지

LCA를 공부하다가 LCA를 더 빠르게 구현할 수 있는 것을 알아내고, 이에 필요한 테크닉이 Sparse Table임을 알아냈습니다. 공부한 곳 (https://blog.naver.com/kks227/220793361738) BOJ 17435 (https://www.acmicpc.net/problem/17435) 22.05.01 연구일지 ✔️ Sparse Table이 필요한 이유 다음과 같이 같이 K개의 간선으로 이루어진 Directed Graph가 있다고 했을 때, 1부터 K + 1번 vertex까지 가려면 O(K)가 걸립니다. vertex는 인접해있는, 즉 한 번 이동했을 때, 어떤 vertex로 가는지 알고 있습니다. K가 적당한 숫자라면 괜찮지만 엄청나게 큰 수라면 Time Complexity면에..
PS/Study Note 2022. 5. 1. 11:15
2-SAT 연구일지

2-SAT에 대하여 공부해봅시다. 2-Satisfiability의 약자로 boolean variable들의 충족 가능성을 묻는 문제입니다. BOJ 2-SAT 3(11280), 2-SAT 4(11281)를 기반으로 연구합니다. 공부하는 데에 도움이 된 블로그 링크들 1(https://blog.naver.com/kks227/220803009418) 2(https://everenew.tistory.com/140) 22.04.03 연구일지 CNF(Conjunctive Normal Form) 식을 true가 될 수 있게 boolean variable의 조합이 있는지 조합이 있다면 어떤 조합으로 이루어지는지 알아내는 알고리즘입니다. 2-SAT에서 CNF는 2-CNF로 이는 한 Clause당 boolean varia..
PS/Study Note 2022. 4. 30. 11:21
SCC, Tarjan Algorithm 연구 일지

SCC 알고리즘에는 Kosaraju Algorithm, Tarjan Algorithm이 있습니다. Kosaraju 알고리즘이 구현에는 편하지만 타잔 알고리즘이 SCC 노드끼리의 위상 정렬을 알 수 있기 때문에 공부하였습니다. 제일 최신화된 연구일지는 22.04.23 연구일지입니다. 이를 참고하여 읽어주시길 바랍니다. 22.04.22 연구일지 Time Complexity >> O(|V| + |E|) 동작 원리 +DFS와 Stack에 대한 사전 지식이 있어야 합니다. 1. 인접 배열을 이용한 DFS를 돌립니다. 2. DFS를 돌리면서 스택에 해당 노드를 담습니다. 2.1 next 노드의 sccOrder가 정해져 있지 않다면 next 노드를 가지고서 DFS를 돌리고, 제일 작은 minOrder 갱신합니다. 2..
PS/Study Note 2022. 4. 22. 23:22
Convex Hull (Monotone Chain 기법) 연구 일지

https://www.geeksforgeeks.org/convex-hull-monotone-chain-algorithm/ Convex Hull | Monotone chain algorithm - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org Monotone Chain 기법에 관해 한글로 되어있는 자료들은 이해가 가..
PS/Study Note 2022. 4. 17. 23:00
SCC 알고리즘 2가지

백준 2150: Strongly Connected Component kosaraju's Algorithm 풀이 https://www.acmicpc.net/source/40831992 로그인 www.acmicpc.net BFS와 Reverse DFS를 사용하여 BFS를 통해 스택에 담긴 노드들을 Reverse DFS를 사용하여 SCC를 찾아냅니다. Tarjan Algorithm 풀이 https://www.acmicpc.net/source/41339158 로그인 www.acmicpc.net 한 번의 DFS를 통해 SCC의 번호를 매겨 찾아냄 SCC 노드끼리 DAG를 만들어내는데 용이합니다
PS/Study Note 2022. 4. 2. 10:57
[알고리즘] Merge Sort (합병 정렬) 구현 (C++)

(공부한 곳 출처: https://velog.io/@codenmh0822/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC) Merge Sort란 분할 정복의 방법을 차용한 방식으로 어떠한 경우에도 시간 복잡도가 O(nlogn)이 나오는 정렬 알고리즘이다. 크기가 1인 배열이 될 때까지 분할한다. 왼쪽 오른쪽으로 분할된 배열을 합치면서(merge) 정렬한다. 시간 복잡도가 O(nlogn)이 나오는 이유는 원소의 개수가 n인 배열을 트리화(?)시키면 무조건 높이는 logn이 된다는 사실을 안다. +병합하는 단계에서 리커시브 콜의 길이를 생각해보면 된다. 분할하는 단계는 시간 복잡도로 치지 ..
PS/Study Note 2022. 3. 1. 23:12
[알고리즘] 최소 스패닝 트리 (C++), 크루스칼 알고리즘

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 공부한 블로그 (https://ansohxxn.github.io/algorithm/mst/) (https://yabmoons.tistory.com/186) [개요] 최소 스패닝 트리란? 방향이 없다. (양방향) 사이클이 없다. >> 트리라고 부르는 이유 모든 노드가 연결되어 있다. (간선이 없는 노드가 존재하면 안 된다.) 트리의 모든 가중치의 합이 ..
PS/Study Note 2021. 12. 16. 01:15
[자료구조] 우선순위 큐, 비교 연산자 (C++)

https://draw-code-boy.tistory.com/47 [자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL 우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 draw-code-boy.tistory.com 저번에 우선순위 큐를 다룬 적이 있다. 이번 다익스트라를 공부하면서 우선순위 큐로도 구현할 수 있는 것을 공부했는데 이번 기회에 저번에 남았던 궁금증을 해결해보려 한다. 왜 비교 연산자가 반대로 작용할까? 답은 쉽게 구할 수 있었다. (https://hydroponicglass.tistory.com/169) #include #incl..
PS/Study Note 2021. 11. 30. 13:18
이전 Prev 1 2 3 Next 다음