본문 바로가기
728x90

알고리즘316

[python] 백준 20955 민서의 응급 수술 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 문제 해결 먼저 분리되어 있는 그룹이 몇개인지 알아야 한다. 그것을 유니온-파인드를 통해 알 수 있다. 만약 시냅스로 연결된 두 뉴런의 번호 u,v를 받았을 때 이미 같은 그룹에 있으면 더 연결 될 필요가 없으므로 잘라내는데에 연산을 한 번 쓰게 된다. 만약 다른 그룹이면 유니온-파인드를 통해 서로 연결 시킨다. 그룹이 다른 개수 + 이미 연결되어 연결 될 필요가 없는 개수를 합친다음 하나의 중.. 2023. 9. 25.
[python] 백준 22856 트리 순회 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 해결 트리의 간선 지나간 횟수를 셀 수 있는가 문제 전체 이동하고 왕복했을 때 지나간 간선 개수 - 오른쪽으로만 이동했을 때 끝까지 간 편도 간선 개수 DFS를 이용해 간선의 개수를 세는 것이 편하다. 자식 노드는 최대 두 개이다. (1개 일 때는 오른쪽 노드를 -1로 정의) CODE import sys input = sys.stdin.readline sys.setrecursionlimit.. 2023. 9. 24.
[python] 백준 7795 먹을 것인가 먹힐 것인가 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 해결 모든 원소를 1대1로 비교해서 계산하는 것은 너무 비효율적이라는 생각이 든다. 정렬을 이용해서 A와 B를 오름차순으로 정렬하고, $i \in {0,1,2,3, . . .n-1} $ $j \in {0,1,2,3, .. m-1}$ 인 임의의 $i, j$에 대해서 A[i] > B[j]이면 A[i+1] > B[j]임을 생각을 하면 좋다. 만약.. 2023. 9. 14.
[python] 백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 해결 1~m 번호까지 차례대로 원하는 두 점을 연결한다.(중복 불가) 어 때 몇 번째 번호에서 사이클이 만들어지는지 구하는 문제이다. 처음에는 하나의 선분이 그어질 때마다 사이클이 존재하는지 직접 돌려야되나 생각했다. 하지만 유니온 파인드(union find)를 이용하면 계산양을 줄이고 쉽게 사이클이 만들어지는지 확인할 수 있음을 알 수 있었다. 그림으로 이해하면 너무 쉽다. CODE .. 2023. 9. 11.
728x90