본문 바로가기
728x90

알고리즘141

[BOJ/Python] 1717. 집합의 표현 📌 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 📌 문제 접근 방법 상호배타 집합의 find_set연산과 union연산을 구현해서 풀이하였다. 시간초과가 났는데, 해결을 위해서 재귀 깊이를 설정해주고 input을 sys.stdin.readline으로 바꿔줬다. 최대 재귀 깊이는 어떻게 계산해야 하는지 궁금해졌다! 지금까지는 아무거나 큰 값으로 넣어줬는데 어떻게 계산해야하지? 📌 코드 # 백준 1.. 2021. 10. 21.
[Algorithm] 서로소(상호배타) 집합 (Disjoint-sets) 서로소(상호배타) 집합 서로 중복 포함된 원소가 없는 집합 교집합이 없음 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 → 대표자(representative) 상호배타 집합 표현 - 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 nodes = [1, 2, 3, 4, 5, 6] parents = [0] * (len(nodes) + 1) # 각 노드의 부모를 저장할 배열 Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성 def make_set(x): parents[x] = x for node in nodes: make_set(node) Find-Set(x) : x를 포함하는 집합을 찾는 연산, 대표자를 반환.. 2021. 10. 20.
[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
[BOJ/Python] 17144. 미세먼지 안녕! 📌 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📌 문제 접근 방법 단순 구현 문제! 문제가 시키는 대로 따라서 구현하면 된다. spread 함수를 만들어서 미세먼지가 퍼지도록 한다. dust라는 배열을 따로 만들어서 각 위치의 먼지 변화량을 저장하고 원래 배열과 더해준다. clean 함수를 만들어서 공기청정기를 가동시킨다. 공기청정기의 위치와 방향을 매개변수로 받아서 해당하는 방향대로 값을 swap해준다. 2, 3의 과정을 T번만큼.. 2021. 10. 20.
728x90

티스토리툴바