본문 바로가기

백준80

백준(BOJ) 25393 교집합 만들기(Python) 이분 탐색 문제. 교집합은 반드시 1개 또는 2개의 구간에 의해서만 만들어지고, 이는 자명하다. 이때 교집합이 발생할 수 있는 경우는 l, r이 정확하게 일치하는 구간이 있는 경우 1개, l이 같고 r이 더 큰 구간과 r이 같고 l이 더 작은 구간이 동시에 존재하는 경우 2개. 위 두 가지의 경우에만 존재한다. 따라서 해시를 k를 l로 가지는 구간의 r의 집합과 k를 r로 가지는 구간의 l의 집합, 총 2개를 만들었다. 그 후에는 구간을 모두 해시에 저장하고, 두 해시 모두 k에 대한 값들을 정렬한다. 그 후에는 쿼리가 들어올 때마다 위 경우를 판단해주면 되는데, 이때 구간이 2개인 경우에는 크게 문제가 없지만, 구간이 1개인 경우에는 문제가 발생한다. 정확하게 l과 r이 일치하는 구간이 존재하는지를 확.. 2023. 1. 13.
백준(BOJ) 1007 벡터 매칭(Python) 그냥 하면 되는 문제. 벡터의 합의 길이를 구해야 하는데, 벡터 매칭의 모든 벡터의 합은 전체 점의 x, y값의 합에 랜덤하게 뽑은 10개 점의 x, y값의 합을 두 번 빼주면 된다. 두 점을 잇는 벡터는 한 점에서 다른 점을 뺀 값이기 때문이다. 이 때 itertools의 combinations를 이용해 20C10으로 전체 집합에서 뺄 점을 뽑아준 뒤 각각 비교하면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product from itertools import combinations """ fr.. 2023. 1. 12.
백준(BOJ) 14950 정복자(Python) MST 문제. 간단하게 MST의 크기를 구한 후 (n-2)*(n-1)*t/2를 더해주면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product from itertools import combinations """ from itertools import combinations from itertools import combinations_with_replacement from itertools import permutations import copy """ #input=sys.stdin.readl.. 2023. 1. 12.
백준(BOJ) 25194 결전의 금요일(Python) DP 문제. 처음에는 set으로 다 넣으면서 풀어보려 했는데 시간 초과가 나서 뭐가 잘못된 것 같았다. 처음에는 DP를 생각했지만 일단 그냥 풀어보자는 식이었는데, 결국 DP로 돌아왔다. DP로 풀려고 하니 리스트 크기를 잡는게 안 돼서 뭐지 했는데, 어짜피 문제에서 요구하는 건 특정한 합을 7로 나눈 나머지가 4가 되는 경우를 찾는 거라 입력받은 모든 A를 7로 나눈 나머지를 가지고 연산을 해도 상관이 없었다. 그렇게 하면 DP 리스트 크기를 6001로 잡을 수 있어 편했다. 그 후에는 그냥 각각 일을 마친 날을 1로 바꾸면서 모든 값을 탐색했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import hea.. 2023. 1. 11.
백준(BOJ) 1963 소수 경로(Python) BFS 문제. 에라토스테네스의 체로 4자리 소수를 모두 담아두고, 입력받은 수에서부터 한 자리씩 바꾸면서 BFS를 진행한다. 한 수에서 체크해야하는 다음 경우는 모두 39가지이고, 그 중에서도 소수인 경우만 포함되므로 스택이 터지는 것에도 안전하다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product """ from itertools import combinations from itertools import combinations_with_replacement from itertools import.. 2023. 1. 11.
백준(BOJ) 25187 고인물이 싫어요(Python) 유니온 파인드 문제. 각 물탱크 집합에 들어있는 청정수 개수와 고인물 개수를 모두 세어두고, 두 물탱크를 연결할 때 해당 물탱크가 서로 다른 집합에 있다면 두 물탱크 집합의 청정수 개수와 고인물 개수를 각각 합친다. 그 후에는 쿼리가 들어올 때마다 물탱크 집합을 찾아준 뒤 청정수 개수와 고인물 개수를 비교해 출력하면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product """ from itertools import combinations from itertools import combinati.. 2023. 1. 11.

티스토리툴바