ALGORITHM/백준67 [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. [BOJ/PYTHON] 18870. 좌표 압축 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/18870 문제 요약 주어지는 좌표 X1, X2, ..., Xn에 좌표 압축을 적용한 결과 출력 핵심 아이디어 주어지는 숫자들을 중복 제거한 채로 정렬하고 제일 앞에 있는 것부터 인덱스값으로 0부터 시작하면 된다. 풀이 # silver2-18870. 좌표 압축 import sys input = sys.stdin.readline # X1, X2, ..., Xn 좌표 압축을 적용한 결과 n = int(input()) nums = list(map(int, input().split())) # 중복 제거한 리스트(오름차순) 만들기 # 그 리스트 돌면서 몇 번째인지 인덱스 프린트 sorted_nums = sorted(set(nums)) # .. 2023. 5. 18. [BOJ/PYTHON] 1448. 삼각형 만들기 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/1448 문제 요약 빨대 N개 중 3개를 선택했을 때, 세 변의 길이 합의 최댓값 핵심 아이디어 길이 합의 최대값을 구해야 하기 때문에 빨대 길이 리스트를 큰 것부터 정렬하면 된다. 삼각형은 제일 큰 변의 길이가 나머지 두 변의 길이 합보다 작을 때 성립하는데, 그 정의를 이용하면 된다. 큰 것부터 정렬된 상황이기 때문에, list[i] > list[i + 1] + list[i + 2]가 성립하면 된다. 순차 3개(a b c)가 성립 안 하면 a b d, a b e... 등의 케이스도 성립 불가해 저렇게만 보면 된다. 마지막 세 개까지 봤는데도 성립 안 하면 -1을 출력하면 된다. 풀이 # silver3-1448. 삼각형 만들기 .. 2023. 5. 18. 이전 1 ··· 6 7 8 9 10 11 12 다음