전체 글91 백준(BOJ) 14171 Cities and States(Python) 해싱 문제. 도시의 앞 2글자와 주 코드가 서로 교차 매칭되는 2개의 도시를 Special Pair라 한다. 이때 주의할 점은 두 도시가 서로 다른 주에 속해 있어야 한다는 것이다. 두 도시가 서로 Special Pair이면서 같은 주에 속해 있는 경우 두 도시의 앞 2글자는 서로 같다. 즉, 해당 도시의 앞 2글자와 주 코드가 모두 같은 경우이다. 따라서 도시와 주 코드를 해싱한 뒤 체크할 때 도시의 앞 2글자와 주 코드가 같은 경우는 빼고 체크하면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import p.. 2023. 1. 14. 백준(BOJ) 10942 팰린드롬?(Python) DP 문제. 먼저 2차원 DP를 생성한다. palindrome[i][j]는 i부터 j까지가 팰린드롬이면 1, 그렇지 않으면 0을 저장한다. j-i가 0이면 1, 1이면 i번째 문자와 j번째 문자가 같은 경우 1, 그렇지 않으면 0을 저장한다. 만약 j-i가 2 이상인 경우에는 k를 변화시키며 양 끝 각각 k개가 서로 같고, 그 중앙에 있는 문자열이 팰린드롬인지를 확인한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product from itertools import combinations """ fro.. 2023. 1. 14. 백준(BOJ) 11497 통나무 건너뛰기(Python) 그리디 문제. 모든 통나무를 그냥 정렬하면 당연히 인접한 모든 통나무의 높이 차이가 최소가 되겠지만, 이 문제에서는 양 끝 통나무의 높이 차이도 고려해 줘야 한다. 즉, 양 끝 통나무의 높이 차이만 어떻게 해결하면 된다는 것이다. 모든 통나무가 순차적인 높이로 배열되어야 높이 차이를 최소로 할 수 있을 것임은 쉽게 생각할 수 있다. 그렇다면 n 개의 통나무가 있을 때 n/2개의 통나무는 오름차순으로, 나머지는 내림차순으로 정렬하고, 두 배열을 붙이면 될 것이다. 그리고 오름차순 배열과 내림차순 배열은 각각, 전체 n 개를 정렬했을 때 홀수 번째와 짝수 번째 수들을 담고 있으면 문제에서 요구하는 조건을 만족시킬 수 있을 것이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import .. 2023. 1. 13. 백준(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. 이전 1 2 3 4 5 6 7 ··· 16 다음
