본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 11664 선분과 점 https://www.acmicpc.net/problem/11664 11664번: 선분과 점 첫째 줄에 선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz가 주어진다. 좌표는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 3차원 공간에서 선분 AB와 점 C를 가장 가까운 직선을 그릴 때 2가지 경우가 나온다. 두 가지 경우를 나눠서 측정할 수 있지만 (cosin 값을 이용해 두 분류를 구분할 수 있다.) 그래도 최소 거리를 구한다는 것이 쉽지 않다. 우리는 극한을 이용해서 구할 것이다. 점 C에서 선분 AB사이의 거리를 answer라 했을 때 answer≤ min(ac, bc) 일 것이다. 선분 AB의 중심을 점 m이라 할.. 2023. 11. 15.
[python] 백준 1039 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 숫자 안에 서로 다른 두개의 자릿수의 숫자를 바꿔가며 K번 바꾸었을 때 가장 큰 수를 만들 경우를 찾는 문제이다. 따라서 처음에 두 자릿수의 숫자를 바꿔서 가장 큰 수가 나왔다고 K번 바꾸었을 때 가장 큰 수가 만들어진다고 할 수 없다. 즉 거의 모든 경우의 수를 다 계산해야한다. 하지만 예외가 있다. 만약 한 자리의 자릿수가 가장 큰 자릿수, 즉 맨 왼쪽에 있는 수이고 나머지 하나의 자릿 수가 0일 경우 총 숫자의 자리수가 줄어들게 된다. 이런 경우는 예.. 2023. 11. 14.
[python] 백준 3584 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 해결 LCA (Low Common Ancestor)알고리즘 최소 공통 조상을 찾는 알고리즘은 트리문제에서 자주나오는 문제이다. 무조건 공통 조상은 있으므로 각 노드에서 루트로 올라가는 길을 정리하여 루트부터 다시 내려가면서 서로 갈라지는 지점을 찾으면 된다. 갈라지기 전에 가장 가까운 공통 조상이다! CODE import sys input .. 2023. 11. 13.
[python] 백준 2022 사다리 https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 문제 해결 다음과 같이 $h_{1}$, $h_{2}$, $w$, $w_{1}$, $w_{2}$를 정의하자. $w_{1} : c = w: h_{2}$와 $w_{2}:c = w: h_{1}$임을 이용해서 c의 값을 $h_{1}$과 $h_{2}$의 값으로 나타낼 수 있다. $ w = w_{1} + w_{2} = \frac{cw}{h_{2}} + \frac{cw}{h_{1}} = cw \frac {h_{1}+h_{2}} {h_{1}h_.. 2023. 11. 12.
728x90