BOJ79 백준(BOJ) 13418 학교 탐방하기(Python) MST 문제. 최대 스패닝 트리와 최소 스패닝 트리를 각각 구한 다음, 각각의 코스트의 제곱의 차를 출력하면 된다. 코드는 다음과 같다. # -*- 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.. 2023. 1. 29. 백준(BOJ) 2195 문자열 복사(Python) 그리디 문제. P[s:len(P)]부터 P[s:s+1]까지 끝값을 변화시키며 S에 들어있는지 확인하는데, 들어있다면 현재 끝값을 s로 수정하면서 P의 끝까지 탐색한다. 코드는 다음과 같다. # -*- 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 permutatio.. 2023. 1. 17. 백준(BOJ) 24524 아름다운 문자열(Python) 그리디 문제. 문제에서 요구하는 조건을 만족하기 위해서는 각각의 T를 골라내기 위해서는 T의 첫 번째 문자를 찾고, 그 뒤에서 두 번째 문자를 찾고, 이 과정을 마지막 문자까지 반복해야 한다. 그러기 위해서 먼저 T에 들어있는 문자의 인덱스를 해싱으로 각각 큐에 모아준다. 그 후 T에 있는 문자의 인덱스 중 가장 먼저인 인덱스를 기록해둔다. 그리고 그다음 문자의 인덱스 중에서 기록된 인덱스보다 크면서 제일 작은 인덱스로 기록된 인덱스를 변경한다. 이때 이미 체크한 인덱스는 모두 pop해준다. 이 과정을 반복해나가고, 만약 T의 문자들 중 하나라도 더 이상 큐에 인덱스가 남아있지 않으면 반복문을 종료한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from coll.. 2023. 1. 14. 백준(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. 이전 1 2 3 4 5 6 ··· 14 다음
