Union&Find6 [BOJ/PYTHON] 13904. 과제 백준 문제 링크: https://www.acmicpc.net/problem/13904 문제 요약 과제 마감일 지켜야 점수 받을 수 있음. 얻을 수 있는 점수 최대값 핵심 아이디어 과제는 원래 발등에 불 떨어질 때 해야 하는 것 과제를 하루에 하나씩 처리한다. 기한 당일에 해당 과제를 한다고 간주하면 되는데, 그래야 앞에 기한 더 짧은 다른 과제를 할 수가 있다. 기한(마감일) 기준으로 정렬 후 for문을 돌아가며 점수를 하나씩 append해주면 된다. 점수 리스트에 들어간 점수의 개수는 처리해야 할 과제의 개수이다. 리스트의 점수의 개수가 마감일보다 크면 기한 안에 모든 것을 처리할 수 없기에 점수가 제일 작은 것을 버려주면 된다. heapq로 풀었는데, heapq에서 pop을 하면 점수가 제일 작은 것.. 2023. 5. 24. [BOJ/PYTHON] 16562. 친구비 백준 문제 링크: https://www.acmicpc.net/problem/16562 문제 요약 친구비를 주면 한 달간 친구가 생긴다! '친구의 친구는 친구다'를 이용해 모든 사람과 친구가 되는 최소 비용 출력, 안 되면 Oh no 출력 핵심 아이디어 ‘친구의 친구는 친구’이기에 트리 계층 관계를 떠올릴 수 있고, ‘모든 사람과 친구’가 되어야 하기에 모든 노드를 연결한다고 생각하면 된다. union & find를 통해 친구 관계를 합쳐주는데, 비용 적은 애를 부모 노드로 해서 합쳐주고, 그 비용을 더하면 된다. 풀이 # gold4-16562. 친구비 import sys input = sys.stdin.readline n, m, k = map(int, input().split()) # 학생 수, 친구관계.. 2023. 5. 24. [BOJ/PYTHON] 10423. 전기가 부족해 문제 링크: https://www.acmicpc.net/problem/10423 문제 요약 모든 도시에 전기가 공급될 수 있도록 하는 케이블 설치 최소 비용 구하기 케이블이 연결돼있는 도시에는 발전소가 하나만 존재해야 핵심 아이디어 문제를 읽으며 도시가 정점, 도시를 연결하는 케이블이 간선, 케이블 설치 비용이 비용이라는 것을 파악하고, 연결(케이블 설치)을 최소로 한다는 점에서 최소 신장 트리를 떠올리면 된다. 이미 발전소랑 연결된 도시는 연결해줄 필요가 없는데, 처음부터 발전소끼리 연결해 발전소의 최상위 부모를 만들고 시작하면 추가적으로 연결할 필요가 없다. 이후 발전소의 부모가 다를 경우에만 연결해주고, 비용을 더하면 된다. 풀이 #gold2-10423. 전기가 부족해 import sys input.. 2023. 5. 24. [BOJ/PYTHON] 6497. 전력난 백준 문제 링크: https://www.acmicpc.net/problem/6497 문제 요약 두 집 쌍에 대해 불이 켜질 수 있도록 하면서 최대로 불 꺼야 함 - 절약할 수 있는 최대 액수 구하기 핵심 아이디어 그래프 간선에 가중치가 있는 무방향 그래프가 주어지는데, 길에 불이 켜져야 하고, ‘모든’ 집을 연결하면서도 최소 비용으로 하려면 비효율적인 사이클이 발생하면 안 된다. 사이클이 없는데 최소 비용을 구하는 거라 최소 신장 트리 알고리즘을 사용하면 된다. (그 중에서 크루스칼 알고리즘을 사용함) 부모 노드가 다르면 연결해주는데, x번 집과 y번 집의 부모 노드가 같으면 이미 불이 들어온 것이기에 불을 꺼주면 된다. 불을 꺼주는 케이스에 대한 비용을 더하면 끝 풀이 #gold4-6497. 전력난 i.. 2023. 5. 24. [BOJ/PYTHON] 4803. 트리 백준 문제 링크: https://www.acmicpc.net/problem/4803 문제 요약 트리는 사이클이 없는 연결 요소. 그래프 주어졌을 때 트리 개수 세기 핵심 아이디어 트리의 개수는 서로소 집합을 찾는 union-find로 풀 수 있다. 입력받은 간선의 각 부모 노드가 다르면 트리를 합쳐주고, 부모 노드가 같으면 사이클이 발생하는 그래프이기 때문에 사이클 리스트에 해당 노드를 추가해준다. 그 다음 모든 노드의 부모 노드를 갱신해주는 과정이 필요하다. 중복 제거한 부모 노드 리스트에서 해당 부모 노드가 사이클이 발생하지 않는다면 트리 개수를 추가해준다. 풀이 # gold4-4803. 트리 import sys input = sys.stdin.readline def find_parent(parent.. 2023. 5. 24. [BOJ/PYTHON] 1717. 집합의 표현 백준 문제 링크: https://www.acmicpc.net/problem/1717 문제 요약 입력 시작이 0이면 합집합 연산 수행, 입력 시작이 1이면 두 원소가 같은 집합에 포함돼있는지 확인하는 연산 수행 1로 시작하는 입력에 대해 둘이 같은 집합에 포함됐는지 여부 출력 - 맞으면 yes, 아니면 no 핵심 아이디어 기본적인 union&find 문제이다. 문제에서 주어지는 ‘합집합 연산 수행’, ‘두 원소가 같은 집합에 포함돼있는지 확인하는 연산 수행’을 보고 각각이 union, find라는 것을 파악하면 된다. 풀이 # gold5-1717. 집합의 표현 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int,.. 2023. 5. 24. 이전 1 다음