본문 바로가기
728x90

알고리즘316

[python] 백준 4386 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 전형적인 유니온 파인드 문제 단 리스트 안에 두 별자리 간의 거리를 오름차순으로 정렬하고 연결 되어있는지 아닌지 유니온 파인드를 통해 확인하고 해결한다. CODE import sys input = sys.stdin.readline import math def find(x): if x != parents[x]: return find(parents[x]) return parents[x] de.. 2024. 3. 7.
[python] 백준 16566 카드 게임 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해결 이진 분류로 bisect_right를 사용할 수 있는가의 문제 가장 최소의 값을 구할 때 만약 사용했다면 그 다음 수를 찾아야 하는데 여기서도 union-find를 사용하는가에 따라서 시간 단축이 될 수 있다. 만약 이전에 어떤 수를 사용했으면 그 수에 접근 했을 때 다음수로 넘어가도록 union-find를 설계할 수 있기 때문이다... 2024. 3. 5.
[python] 백준 14939 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 문제 해결 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제 어디서부터 시작해야할지 많이 어렵다. 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다. 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다. 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다.. 2024. 3. 2.
[python] 백준 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 조금 고민하면 한 번 노드를 다 이은 후 가장 긴 길이를 빼면 되지 않을까? 싶은 생각을 할 수 있다. 하지만 이 때 가장 긴 길이가 짧아서 나눌 때 최소 길이가 되지 않을 수 있지 않나? 생각을 하게 되었다. 하지만 정렬(sort)를 이용하여 가장 유지비용이 짧은 두 노드부터 이어가며 모든 노드를 다 이은 다음 가장 나중에 이은 노드를 뺀다면 최소.. 2024. 3. 1.
728x90