본문 바로가기

파이썬

 (320)
[Python] 10255번 교차점 https://www.acmicpc.net/problem/10255 10255번: 교차점 이제 사각형의 경계선과 선분의 교차점에 관한 간단한 기하 문제를 풀어볼 것이다. 매우 다행히도 사각형은 항상 축에 평행한 형태로만 놓여 있다. 어떤 사각형과 어떤 선분의 교차점은 항상 0 www.acmicpc.net 22/09/22 선분 교차 알고리즘을 조금 응용한 문제로, 약간의 아이디어가 있어야하는 문제이다. 문제 접근 방식: 무작정 선분 교차 알고리즘을 4번 적용하여 문제를 풀어버리면 조금 난감하다. 왜냐하면, 모서리에만 선이 닿는다고 했을 때, 실제로는 선분과 직사각형이 한 점에서만 만나지만, 선분 교차 알고리즘이 만나는 모서리를 포함하는 두 직선에 대해서 모두 실행되기 때문에 두 점에서 만나는 것으로 오해 ..
[Python] 20149번 선분 교차 3 (추후 보강 예정) https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 22/09/22 선분 교차 2 문제를 풀었다면 거기에 교점을 구하는 코드를 추가로 집어넣음으로써 문제를 풀 수 있다. 문제 접근 방식: 이 문제를 풀기 전에 선분 교차 2 문제를 풀기를 권장한다. 먼저 CCW알고리즘과 이를 응용한 선분 교차 알고리즘을 이해하고 있다는 가정 하에서 서술하겠다. 선분 교차 알고리즘에 관한 글을 추후에 작성한다면 여기에 글을 덧붙일 예정이다. 어떤 선분이 교차하는지 교차하지 않는지 판단을 했다면, 그 교점을 구해야 한다. 그러면..
[Python] 3108번 로고 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 22/09/22 유니온-파인드(분리 집합)와 두 직사각형이 만나는 함수를 섞으면 쉽게 풀 수 있는 문제이다. 유니온-파인드의 기본 난이도가 골드 5인데, 이 문제에서 유니온-파인드를 사용해야 된다는 점을 캐치하는 것, 그리고 두 직사각형이 만나는 함수를 구현하는 난이도, 그리고 약간의 예외처리를 고려하자면 저 난이도는 굉장히 적절한 난이도라고 생각한다. 문제 접근 방식: PU명령은 펜을 떼라는 명령이다. 이 ..
[Python] 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/09/22 전형적인 2차원 DP문제로, 그렇게 어렵진 않다. 푸는 유형만 알고 있다면 굉장히 쉽게 풀 수 있다. 문제 접근 방식: 비슷한 유형의 문제 중에서 오르막 수라는 문제가 있다. 이와 비슷하게 접근하면 되는데, 여기서 DP의 정의를 다음과 같이 정의하자. DP[i][j] = 자리가 i자리 숫자일 때, 숫자가 j로 끝나는 계단 수의 개수 그러면 계단수의 정의 상, 바로 이전의 숫자가 1만큼만 차이가 나야 하므로, DP[i][0] = DP[i-1][1] DP[i][1] = DP[i-1][0] + DP[..
[Python] 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 22/09/21 전형적인 유명한 DP문제. 그리고 그렇게 어렵지도 않은 DP문제이다. 문제 접근 방식: DP[i] = A[i]를 마지막 값으로 가지는 가장 긴 부분 수열의 길이라고 정의하자. 그러면 O(n^2)의 시간 복잡도로 우리는 이 문제를 해결할 수 있다. DP[i] = A[i] > A[j] (i > j)가 성립되..
[Python] 1629번 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 22/09/21 파이썬의 강력함. 그 한 줄이면 충분하다. 문제 접근 방식: 파이썬의 기본 내장 함수 중 pow함수는 어떤 숫자를 거듭제곱한 것을 특정 숫자로 나누는 연산을 지원한다. 또한, 기본적으로 pow함수의 거듭제곱의 원리가 분할 정복을 이용한 거듭제곱이라 매우 빠르다. 제일 그 풀이가 간단해서 그 풀이로 문제를 풀었다. 이후에 만약 행렬 거듭제곱문제를 풀게 된다면 새롭게 함수를 구현해야 하긴 한다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드..
[Python] 25576번 찾았다 악질 https://www.acmicpc.net/problem/25576 25576번: 찾았다 악질 구수한 욕설과 귀여운 동남권 사투리가 매력인 인기 스트리머 랄파는 오늘도 열심히 게임 방송을 한다. 랄파는 과거 게임 최상위 랭커를 달성했던 빛나는 시절이 있었으나, 현재는 실력이 많이 www.acmicpc.net 22/09/21 전형적인 문제 잘 읽고 구현하면 되는 문제로, 그렇게 어렵지는 않다. 문제 접근 방식: 문제 요약하자면, 어떤 시청자가 악질인지 악질이 아닌지 판단하는 문제이다. 첫 번째 줄에는 어떤 시청자가 구독한 스트리머의 명수와 그 스트리머들의 시청자 수 변화 리스트의 길이가 주어진다. 이후 두 번째 줄에서는 랄파의 시청자 수의 변화가 주어지고, 나머지 줄에서는 각 스트리머의 시청자 수의 변화가..
[Python] 10216번 Count Circle Groups https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 22/09/20 전형적인 분리 집합 문제로, 분리 집합에 대한 내용만 잘 알고 있다면 쉽게 풀 수 있는 문제이다. 만약 분리집합을 모른다면 조금 푸는데 힘들 것이다. 문제 접근 방식: 문제에서는 통신영역이 서로 닿거나 겹치면 통신이 가능하다고 보는데, 여러 다리를 거쳐서 통신이 되는 것도 통신이 가능하다고 간주하였다. 때문에 이 정보를 보고 바로 분리 집합에 관련된 문제이겠구나..

티스토리툴바