본문 바로가기

백준80

백준(BOJ) 7344 나무 막대(Python) 간단한 그리디 문제. 문제를 풀기 위한 아이디어를 떠올리기 쉬웠던, 문제에 나온 대로만 하면 되는 문제였다. 입력받은 막대의 l, w 값을 l의 오름차순에 w의 오름차순으로 정렬하고, [[[0,0]]] 형태의 리스트를 만든다. 이 리스트를 L이라 하자. L은 가동되는 기계가 어떤 막대를 가공할 지를 담고 있을 것이다. L의 최종 개수는 기계의 개수이고, 이는 최소 작동 준비 시간일 것이다. 우리는 각 막대의 l, w 값을 L의 모든 원소의 마지막 원소의 0, 1번째 인덱스에 위치한 값과 비교할 것이다. 그리고 l=L3[k][-1][1]: L3[k].append(X) flag=1 break if not flag: L3.append([X]) print(len(L3)) 풀고 난 느낌은, 문제가 overrate.. 2022. 7. 9.
백준(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.

티스토리툴바