본문 바로가기

BOJ79

백준(BOJ) 17386 선분 교차 1(Python) 먼저 L1에서 L2의 두 점에 대해 CCW를 해본다. 그 때 두 점의 회전 방향이 같으면 두 선분은 교차하지 않지만, 두 점의 회전 방향이 다르면 두 선분이 교차하는 것이 아니라 CCW를 L2에서 L1의 두 점에 대해 해줘야한다. 그 때 두 점의 회전 방향이 같으면 두 선분은 교차하지 않는다. 코드는 다음과 같다. x1,y1,x2,y2=map(int,input().split()) x3,y3,x4,y4=map(int,input().split()) a=(x3-x2)*(y2-y1) b=(y3-y2)*(x2-x1) c=(x4-x2)*(y2-y1) d=(y4-y2)*(x2-x1) k1=0 k2=0 if a>b: k1=-1 elif ad: k2=-1 elif cf: k3=-1 elif eh: k4=-1 elif g 2022. 7. 9.
백준(BOJ) 11758 CCW(Python) 그냥 수학 문제다. P1, P2, P3에 대해 직선 P1P2의 방정식을 구하고, 거기에 x3를 대입해 구한 y값과 y3을 비교하면 끝이다. P3에서 P2를 중심으로 회전하되, 반직선 P2P1에 도달할 수 있는 가장 가까운 방식으로 회전해야 하기 때문이다. y값이 y3보다 크면 시계 방향, 작으면 반시계 방향, 같으면 일직선이다. 그림을 그려 표현하면 쉽지만, 귀찮기 때문에 생략하도록 하겠다. 코드는 다음과 같다. x1,y1=map(int,input().split()) x2,y2=map(int,input().split()) x3,y3=map(int,input().split()) a=(x3-x2)*(y2-y1) b=(y3-y2)*(x2-x1) if a>b: print(-1) elif a 2022. 7. 9.
백준(BOJ) 11003 최솟값 찾기(Python) 덱으로 바로 풀 수 있는 문제. 최소 힙으로 최솟값을 뽑아낼 생각이었는데, O(nlogn)이라 그런지 python이랑 pypy 둘 다 시간 초과가 터졌다. 그래서 생각한 게, 덱을 써서 항상 최솟값이 덱 맨 앞에 있도록 하는 것이다. 탐색 범위에 있지 않은 값을 덱에서 빼고, 현재 덱에 삽입될 값보다 큰 값을 가졌으면 덱에서 빼는 식으로 덱을 수정해나갔다. 결국 O(n)으로 해결할 수 있었다. ​ 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,l=map(int,.. 2022. 7. 9.
백준(BOJ) 18170 두 동전 언리미티드(Python) BFS 문제였다. 두 개의 동전을 체크해야하기 때문에 visited 리스트를 2개 만들어 사용했고, 두 동전의 위치가 모두 visited에 걸리면 queue에 append하지 않는 식으로 구현했다. 그 외에도 두 동전이 모두 떨어진 경우 append하지 않았고, 한 동전이 다른 동전의 위치로 움직이는데 다른 동전이 움직이지 않는 경우 append하지 않았다. queue에는 현재 움직인 횟수와 첫번째 동전의 x,y좌표값, 두번째 동전의 x,y좌표값을 집어넣었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setre.. 2022. 7. 8.
백준(BOJ) 2180 소방서의 고민(Python) 그리디 문제였다. at+b 꼴의 일차 함수에서 단순히 a와 b값만으로 정렬해서 문제를 풀 수 없다고 생각했고, 느낌상 b/a로 정렬하면 될 것이라고 생각했다. 그러나 확신이 없어서 결국 검색해보니 내 감이 맞았다. 당연히 b/a 값이 같다면 a값이 더 큰 순으로 정렬해야 더 효율적이기 때문에 key는 b/a, -a 순으로 오름차순 정렬했다. 그러나 여기서 문제는 a가 0인 경우 어떻게 할 것인가인데, a가 0인 경우에는 t에 상관없이 진화 시간이 똑같으므로 b의 크기에 관계 없이 우선 순위의 맨 뒤에 위치해야한다. 따라서 b/a 자리에 INF를 넣어주면서 알고리즘을 완성시켰다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import .. 2022. 7. 8.
백준(BOJ) 1027 고층 건물(Python) 간단한 브루트포스 문제이다. n의 크기가 그리 크지 않기 때문에 따로 시간복잡도 계산을 하지 않고도 브루트포스 문제임을 쉽게 알 수 있었다. 현재 서있는 빌딩에서 보고 싶은 빌딩을 고르고, 그 빌딩과의 선분을 연결한 뒤 기울기와 y절편을 이용해 두 빌딩 사이에 있는 빌딩 중 선분보다 높은 빌딩이 없다면 ans에 1을 더하고, 그렇지 않으면 continue하는 방식으로 알고리즘을 구현했다. ​ 코드는 다음과 같다. n=int(input()) L=list(map(int,input().split())) ans=0 for i in range(n): c=0 for j in range(n): if i==j: continue a=(L[j]-L[i])/(j-i) b=L[j]-a*j if i=a*k+b: flag=1 b.. 2022. 7. 8.

티스토리툴바