python3
-
[백준] 4386번 별자리 만들기(파이썬, MST)Coding Test/Algorithm 2021. 10. 31. 19:06
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 이번 문제는 최소 스패닝 트리 문제였다. kuruskal mst 알고리즘을 사용했다. 핵심은 간선간의 비용은 좌표 간의 거리이며 2차 평면에서 두 좌표의 거리는 직각삼각형을 그려서 빗변의 길이를 구하면 두 좌표간의 거리가 된다. x1, y1 과 x2, y2 두 좌표가 있다면 |x1 - x2|^2 + |y1 - y2|^2 의 루트 값이 바로 두 좌표간의 거리가 된다. import sys import ..
-
[백준] 2467번 용액 (파이썬)Coding Test/Algorithm 2021. 8. 8. 00:32
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이번에는 이진탐색 문제를 풀었다. 2019.06.17 - [Knowledge/Algorithm] - 알고리즘 - 이진탐색 알고리즘 개념 알고리즘 - 이진탐색 알고리즘 개념 안녕하세요. 오늘은 이진탐색 알고리즘 개념에 대해서 정리하려 합니다. 이진탐색이란 이진법, 이분법에서 파생된 말로 아메바를 예로 들 수가 있겠네요. 아메바는 번식을 할 때 자신의 몸을 반 shineild-security.t..