BOJ81 백준(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. 백준(BOJ) 10253 헨리(Python) 단순 구현 문제. a와 b를 입력받았을 때 a와 b를 수정하며 1/x 2023. 1. 11. 백준(BOJ) 3078 좋은 친구(Python) 큐로 푼 문제. 이름의 길이에 각각 큐를 만들어놓고 거기에 등수를 집어넣는다. 이때 집어넣기 전 큐가 비어있지 않으면 현재 큐에 있는 등수 중 k 이상 차이나는 등수를 모두 pop해준다. 그러고 나면 큐에 있는 등수들은 모두 현재 집어넣는 등수와 '좋은 친구'인 경우 밖에 없다. 큐의 크기를 ans에 더하고 등수를 해당 큐에 집어넣는 과정을 반복하면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product """ from itertools import combinations from itertoo.. 2023. 1. 7. 백준(BOJ) 1527 금민수의 개수(Python) 브루트포스 문제. 파이썬 itertools 라이브러리의 product 클래스를 사용하면 문자들의 조합을 모두 뽑아낼 수 있다. 10억 이하의 4와 7로 이루어진 수의 개수는 2^9+2^8+2^7+...이므로 브루트포스로 풀어도 안정권에 든다. 모든 수를 찾아보며 A와 B 사이에 있는 지를 판단해주면 되는 문제. product 클래스를 사용하지 않으려면 DFS나 BFS로 하나하나 확인해줘도 될 것이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect import math from itertools import product """ from itertools import .. 2023. 1. 7. 백준(BOJ) 25498 핸들 뭘로 하지(Python) 대표 BFS 문제. 1번 노드부터 시작해서 갈 수 있는 노드 중 가장 사전 순으로 뒤에 있는 문자로 이동하면서 ans에 그 문자를 추가해주면 된다. 만약 그 문자를 가진 노드가 2개 이상인 경우 그 문자를 가진 모든 노드에 대해 탐색을 진행해야 한다. 이를 해결하기 위해 한 노드에서 갈 수 있는 노드 중 가장 사전 순으로 뒤에 있는 문자의 노드를 모두 담은 리스트와 현재 문자 길이를 queue에 넣고 빼는 식으로 구현했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import bisect """ import math from itertools import combinations from.. 2022. 8. 23. 이전 1 2 3 4 5 6 7 8 ··· 14 다음
