본문 바로가기

알고리즘

 (364)
[Python] 32823번 채굴권 분할 https://www.acmicpc.net/problem/32823 24/11/27  이전에 ICPC예선에서 해결했던 문제 중 하나이다. 태그에 선분 교차 판정이 들어있는데, 사실 그렇게 거창하게 할 필요는 없고, CCW를 여러 번 사용하여 홀짝성만 판단하면 충분히 해결할 수 있는 문제다. 문제 접근 방식:  먼저, 선분들의 좌표들이 모두 극좌표의 형식으로 주어져 있음에 유의해야한다. 극좌표에서 일반적인 직교좌표계로 변환하는 방법은 다음과 같다. 반지름이 $r$이라고 하고, 각도가 $\theta$라고 한다면(이때의 각도는 라디안으로 주어진다) 다음과 같다. $$(x, y) = (r\cos \theta, r \sin \theta)$$ 문제에서는 선분의 끝 점이 모두 원주 위에 놓여있으므로 반지름 $r$은 ..
[Python] 32840번 Triangle https://www.acmicpc.net/problem/32840 24/11/26  ICPC본선 당시에 파이썬으로 구현해서 맞은 문제다. 약간의 많은 조건 분기가 들어가는데, 이건 사람마다 갈릴 수 있는 부분이라서 구현이 어렵다고 하기에는 조금 힘들 것 같다. 문제 접근 방식:  결론적으로 이야기 하면 변 위에 있는 정수 격자점 중 꼭짓점과 가장 가까운 두 점만 보면 된다. 즉, 봐야하는 점이 변에 대해서 2개 이므로, 총 8가지 경우의 수에 대하여 브루트포스를 돌리면 된다. 이 이유는 아핀변환을 곰곰히 생각해보면 된다. 이전에 아핀변환에 관련된 문제를 내서 그런지, 이에 대한 아이디어는 금방 떠올랐다. 점 2개를 고정하고 하나를 움직이는건 아핀변환에 해당한다. 기존 삼각형의 넓이에서 변화가 가장 적어..
[Python] 32773번 회전 관성 모멘트 https://www.acmicpc.net/problem/32773 24/11/26  오랜만에 일반 물리학의 내용을 한 번 복습할 수 있게 했던 문제다. 문제 접근 방식:  문제의 목표는 $xy$평면 위에 정의된 다각형 판이 있을 때, 이 다각형 판을 $z$축에 대해서 회전시킬 때의 회전 관성 모멘트를 구하는 것이다. 이때의 회전 관성 모멘트는 다음과 같이 정의된다. $$\int r^{2} \, dm$$ 이때 $r$은 회전 축으로부터의 거리를 나타내며, $dm$은 그 질점의 미소 질량을 뜻한다. $x$좌표와 $y$좌표가 주어지므로, 거리를 다음과 같이 찢어서 표현할 수 있다. $$\int x^{2} \, dm + \int y^{2} \, dm$$ 근데 이건 $x$축으로 다각형 판을 돌릴 때의 회전 관성 ..
[Python] 11728번 배열 합치기 https://www.acmicpc.net/problem/11728 24/11/25  단순히 배열 두 개를 합쳐서 정렬하는 문제다. 문제 접근 방식:  파이썬에서 그냥 나이브하게 합쳐서 정렬하면 된다. 근데, 그러면 너무 재미 없으니까, 두 포인터로 푸는 방법도 알아보자. 이미 정렬된 상태로 주므로, 배열 A와 배열 B를 가리키는 포인터 두 개($i$와 $j$)를 선언하고, $A[i]  시복도는 $\mathcal{O}(N+M)$이 된다. 반면, 두 리스트를 나이브하게 합치고 정렬하는 방법은 $\mathcal{O}(N+M \log(N+M))$의 시복도가 든다. 근데 실제로 실행해보면 두 리스트를 나이브하게 합치고 정렬하는 방법이 시간이 더 적게 소요가 되는데, 이는 정답 배열에 append를 하는 연산의 ..
[Python] 9246번 다트판 https://www.acmicpc.net/problem/9246 24/11/23  정규 분포의 기댓값을 구하는 문제다. 문제 접근 방식:  확률 밀도 함수(Probability density function)이 다음과 같이 정규분포 모양으로 주어진다. $$f(r) = \frac{1}{2\pi\sigma^{2}} e^{-\frac{r^{2}}{2\sigma^{2}}}$$ 이때, $r$은 다트판의 중심으로부터 떨어진 거리를 의미하며, 표준편차 $\sigma$의 값은 문제에서 주어진다. 다트판의 중심으로부터 떨어진 거리 $r$만큼의 위치에 다트가 꽃힐 확률은, 저 확률 밀도 함수에 $2\pi r$을 곱한 값이 된다. 직관적으로, 다트판의 중심으로부터 떨어진 거리 $r$만큼의 위치의 미소 면적들을 모두 모으면..
[Python] 21870번 시철이가 사랑한 GCD https://www.acmicpc.net/problem/21870 24/11/04  단순한 분할정복 문제다. 문제 접근 방식:  얼핏 보면 시간제한이 1초고, 나이브하게 돌리면 빡빡할 것이라고 생각이 들 것이다. 우리는 왼쪽과 오른쪽으로 항상 배열이 나뉨을 관찰할 수 있다. 왼쪽 배열의 값들의 gcd + 오른쪽 배열의 최대 혹은 오른쪽 배열의 값들의 gcd + 왼쪽 배열의 최대 중 가장 큰 값이 우리가 원하는 값임을 확인할 수 있다. 오른쪽 배열의 최대 혹은 왼쪽 배열의 최대 또한 분할 정복을 통해 계속 재귀적으로 구할 수 있으므로, $\mathcal{O}(N \log N)$만에 문제를 해결할 수 있다. DP로 값을 저장하지 않아도 충분히 돌아감을 확인할 수 있다.(오히려 값을 저장하면 저장하는 시간때..
[Python] 30855번 Fraction https://www.acmicpc.net/problem/30855 24/11/22  ICPC문제 중 흔치 않은 파이썬 친화적인 문제다. 문제 접근 방식:  파이썬에서는 fractions 모듈이 존재한다. 이 모듈은 유리수를 정확하게 저장해준다. 분모와 분자는 자동적으로 약분을 해서 저장된다. 문제는 굉장히 간단하다. $(a, b, c)$의 형태로 주어질 때, $a + b/c$의 값을 기약 분수로 출력하는 것이 목적이다. $a, b, c$는 숫자 혹은 또 다른 $(a, b, c)$형태의 괄호 문자열이 될 수 있다. 스택을 통해 해결할 수 있다. 예외를 처리하는 부분이 많은데, 그냥 raise문을 통해 Error를 띄우도록 하면 처리가 간편해진다. 예를 들어, 열린 괄호가 있는데 닫히지 않는다라던지, 맨 ..
[Python] 4185번 Colliding Traffic https://www.acmicpc.net/problem/4185 24/11/21  이전에 북마크 해두었던 문제 중 하나로, 약간의 케이스 분류를 동반한 수학적 방법으로 해결했다. 문제 접근 방식:  문제의 입력은 다음과 같다. 테스트 케이스가 $C$개 주어진다. 각 테스트 케이스 마다 보트의 개수인 $N$개와, 두 보트가 서로 $r$ 미터 안에 있으면 충돌한다고 판정하는 실수 $r$이 주어진다. 이후에는 $N$개의 보트에 대한 정보가 다음과 같이 주어진다.$x, y, d, s$. 여기서 $x, y$는 보트의 초기 위치이고, $d$는 보트의 각도, $s$는 보트의 속력을 나타낸다. $d=0$이라면 북쪽을, $d=90$이라면 동쪽을, 그런 식으로 시계 방향과 60분법으로 각도가 표현된다. 문제에서 요구하는..

티스토리툴바