📑 문제 문제링크 : 친구 네트워크 🤔 생각의 흐름 Disjoint Set 자료구조가 필요한 문제입니다. 귀찮은 부분은 이름이 숫자로 주어진 것이 아니라 문자열로 이루어진 점과 사람이 총 몇 명인지 모르는 점입니다. 문자열 이름은 딕셔너리를 이용해서 처리해주면 될 것 같네요. 처리해주는 방법은 디테일하게 2가지가 있습니다. ...
[백준 18809] Gaaaaaaaaaarden (파이썬 / Python)
📑 문제 문제링크 : Gaaaaaaaaaarden 🤔 생각의 흐름 풀기 위해 아이디어적 어려움을 느낄만한 부분은 크게 없는 것 같습니다. 배양액을 뿌릴 수 있는 위치들 중에서 서로다른 R 개와 G 개를 뽑아 BFS 를 수행해야합니다. 다만 좀 귀찮은 부분은 빨간색과 초록색 배양액의 BFS 를 병렬적으로 수행해야하는 부분입니다. 처음에는 ...
[백준 17435] 합성함수와 쿼리 (파이썬 / Python)
📑 문제 문제링크 : 합성함수와 쿼리 🤔 생각의 흐름 얼마 전에 알게된 희소 배열 알고리즘을 써야겠다고 생각했습니다. ‘희소 배열이 뭐지?’ 하시는 분들은 이 글을 보고 와주세요. 🎯 풀이방법 희소 배열 문제이며, 시간복잡도는 $O((m + Q) \log N)$ 입니다. move[i][j] : j 번 노드가 $2^i$ 번 이...
[알고리즘] 희소 배열(Sparse Table) 알고리즘
🤔 희소 배열이 뭐야? 희소 배열의 정의는 배열 원소의 갯수가 배열의 길이보다 작은 배열이라고 합니다. 그런데 제가 설명할 알고리즘에서는 배열의 원소 갯수가 배열의 길이와 같은데 어째서 희소 배열인지는 잘 모르겠네요… 이 알고리즘은 노드당 out-degree(나가는 간선의 갯수)가 1인 단방향 그래프에서, i 번 노드로부터 N 번 이동했을 때 어떤...
[백준 2213] 트리의 독립집합 (파이썬 / Python)
📑 문제 문제링크 : 트리의 독립집합 🤔 생각의 흐름 처음에는 각 노드마다 선택했을 때와 선택하지 않았을 때, 두 경우의 해당 노드부터 leaf 노드까지의 가중치 합을 저장하는 dp 리스트에 저장하여 해결했습니다. 하지만 다른 분의 풀이를 보니 굳이 dp 리스트를 사용하지 않고, 노드에 방문할 때마다 선택했을 때와 선택하지 않았을 때를 ...