본문 바로가기
728x90

알고리즘316

[python] 백준 17386 선분 교차 1 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 문제 해결 CCW를 사용하는 문제 CCW는 외적을 이야기 한다. 우선 두 직선이 일직선 위에 있는 경우가 없으므로 평행하거나 일치, 여러점이 겹치는 것을 생각할 필요가 없다. 따라서 L2의 끝 두점 (x3,y3), (x4,y4)와 L1의 두 끝점 (x1,y1), (x2,y2)을 CCW로 계산해서 양수가 하나라도 나오면 교차를 하지 않는다. CODE import sys input = sys.stdin.readline .. 2023. 8. 25.
[python] 백준 19583 싸이버개강총회 https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 문제 해결 시간비교를 어떻게 할 것인가가 문제 시간을 string type으로 바꾼다음 :을 제외하고 이어 붙여 정수로 만들어 비고하면 편하다! 19:53 → 1953, 20:00 → 2000 로 바꾼 후 비교! 시작시간 이전에 들어오고 끝낸 시간에서 스트리밍을 끝낸 시간 사이에 나가는 것이 확인 되면 답의 개수를 추가하면 끝! CODE import sys i.. 2023. 8. 21.
[C++] 백준 17071 숨바꼭질 5 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해결 1초마다 수빈과 동생은 움직인다. 수빈은 1초마다 x-1, x+1 만큼 움직이거나 2*x만큼 순간이동 할 수 있다. 동생은 t초에 t만큼 움직인다. 수빈은 짝수 t초에 있던 지점을 그 이후 짝수 시간 때에 그 지점에 다시 올 수 있다. 홀수 t에 있던 지점은 그 이후 홀수 시간 때에 대사 올 수 있다. 따라서 visited[i][j]에 수빈이 지점 .. 2023. 8. 12.
[python] 백준 17616 등수 찾기 https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 해결 DFS로 내 앞에 최소 몇명이 있는지 구하고, 내 뒤에 최소 몇명이 있는지 쉽게 구할 수 있다. 최고 등수는 한 명도 앞에 없을 때 1등이라 하고 앞에 있는 사람의 명수가 늘어날 때마다 1씩 더해준다. 최저 등수는 꼴등이라 가정하고 뒤에 한 명씩 단서가 생길 때마다 1씩 빼주며 등수를 구한다. 함께 구하는 방법은 생각하지 .. 2023. 8. 11.
728x90