728x90 반응형 백준 알고리즘/기타7 [백준 17386][파이썬] 선분 교차 1 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 이전 포스팅에서 CCW 알고리즘을 활용하여 선분 교차하는 방법에 대해서 배웠다. https://growth-coder.tistory.com/163 이 방식을 그대로 사용하면 된다. 우선 세 점이 일직선 상에 존재하는 경우가 없다고 했으므로 ccw의 값이 0인 경우는 신경쓰지 않아도 된다. 그럼 예외 사항은 아래 그림과 같은 경우만 신경쓰면 된다. 이 경우는 선분 AC를 기준으로 한 번, 선분 BD를 기준으로 두 번 .. 2023. 4. 25. [백준 1927][파이썬] 최소 힙. 파이썬 heapq 모듈 사용법 (우선순위 큐) https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 사용하여 푸는 문제이다. 우선순위 큐의 삽입, 삭제 시간 복잡도는 O(log N)이다. 파이썬에서 우선순위큐인 heapq 모듈을 제공한다. heapq의 경우 사용방법이 특이한데 따로 리스트를 만들고 이 리스트를 heapq 메소드의 인자로 사용해야 한다. 1. 삽입 : heapq.heappush( list, value ) import heapq li=[] heapq.. 2023. 3. 13. [백준 1629][파이썬] 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 이 문제를 해결하기 위해선 알아야하는 수학적 지식이 있다. (a*b)%c=((a%c)*(b%c))%c 위 공식을 사용하면 이 문제를 분할 정복 방식으로 해결할 수 있다. 예를 들어 3을 12번 곱한 값을 7으로 나눈 나머지를 구한다면 3을 6번 곱한 값을 7로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 3을 6번 곱한 값을 7로 나눈 나머지는 3을 3번 곱한 값을 7으로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 이렇게 하향식.. 2023. 2. 28. [백준 1541][파이썬] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식은 +와 -로만 이루어져있고 괄호를 적절히 쳐서 최소값을 구하는 문제이다. 즉 식을 뺄 때는 괄호를 적절히 쳐서 최대한 큰 값을 빼야한다. 50 + 40 - 30 + 40 +20 - 10 + 20 위와 같은 식이 있다고하자. 식에서 -가 나오면 그 값부터 다시 - 가 나오거나 식의 끝까지 괄호를 치면 된다. 50 + 40 - (30 + 40 +20) - (10 + 20) 파이썬의 경우 문자.. 2023. 2. 27. 이전 1 2 다음 728x90 반응형
