본문 바로가기

파이썬

 (320)
[Python] 32871번 돌 게임 nm https://www.acmicpc.net/problem/32871 24/12/03  좋은 아이디어를 가진 게임 이론 문제다. 문제 접근 방식:  문제 접근 방식의 핵심은, 행과 열의 쪼개진 부분을 붙여서 새로운 블록으로 생각해도 상관 없다는 것이다. 예를 들어, 다음과 같다.$3 \times 4$크기의 판에서 $2$번 열을 선택해서 없앴다면,이렇게 그냥 새로운 $3 \times 3$짜리 크기의 판으로 생각해도 된다는 점이다. 편의 성을 위해, $N  그러면, 일단 $N = 1$인 경우 선공이 항상 이김은 당연하다. $N = 2$이고 $M = 2$라면, 선공은 무슨 짓을 해도 $N = 1$인 경우로 되돌아가므로 선공이 진다. $N = 2$이고 $M = 3$이라면, 선공은 $N=2, M=2$인 상태를 상대..
[Python] 9612번 Maximum Word Frequency https://www.acmicpc.net/problem/9612 24/11/30  간단한 실버 문제다. 문제 접근 방식:  각 단어의 빈도 수를 나타내는 딕셔너리 $D$를 선언해준다. 이후 각 단어가 새로 나오면, 그 단어를 딕셔너리에 새롭게 넣고 값을 $1$로 설정, 이미 나왔던 단어였다면 기존 값을 $1$ Increasing하도록 설정했다. 이후 가장 자주 나오는 빈도수를 가진 단어, 그 중에서도 가장 사전순으로 뒤에 있는 단어와 그 빈도수를 출력하면 되는데, 이건 그냥 $D$에 있는 각 단어의 빈도수를 계속 비교하면서 갱신하는 형식으로 구현했다. 파이썬에서는 두 문자열이 사전 순인지를 그냥  맨 처음에는 파이썬 collections모듈의 Counter자료형을 쓸 까 생각했지만, Counter자료형..
[Python] 8094번 Canoes https://www.acmicpc.net/problem/8094 24/11/29  간단한 정렬 + 두 포인터 + 그리디 문제다. 문제 접근 방식:  간단하게 문제를 요약하면 다음과 같다. 카누 한 대에는 최대 사람을 두 명 태울 수 있다. 문제에서 카누 한 대의 최대 중량 제한 $W$를 주고, $N$명의 사람들의 몸무게를 준다. 모든 사람을 카누에 태우려고 할 때, 필요한 카누의 최소 대수를 구하는 것이다. 가장 무거운 사람과 가장 가벼운 사람을 짝지어서 태우는 방법을 먼저 생각했다. 예를 들어 무게 제한이 $100$이라면, $90$과 $10$을 짝지어서 태울 수 있을 것이다. 만약 그게 불가능 하다면, $90$만 먼저 태우고, $10$은 그 다음으로 무거운 사람과 짝지어서 태우면 될 것이다. 그래서 ..
[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] 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] 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를 띄우도록 하면 처리가 간편해진다. 예를 들어, 열린 괄호가 있는데 닫히지 않는다라던지, 맨 ..

티스토리툴바