본문 바로가기

전체 글91

백준(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.
백준(BOJ) 10253 헨리(Python) 단순 구현 문제. a와 b를 입력받았을 때 a와 b를 수정하며 1/x 2023. 1. 11.
재활의 필요성 지난 여름 이후로 PS를 쭉 쉬었다. 백준은 풀지도 않았고 코포도 9월 1번 10월 1번 친게 다였다. 개인적인 문제도 있었고 이래저래 바쁘다보니 PS를 놓게 된 것 같다. 11월 말에 있었던 SPC에서는 실수를 하나 거하게 하는 바람에 수상도 못했고 이래저래 동기부여가 안 되는 상황이었다. 그래도 여태껏 해온게 조금은 있어서 문제를 막 못 풀고 이러진 않을 거라고 생각했는데, 최근에 소마 코테 때문에 다시 PS를 잡으면서 내가 진짜 못해졌다는 걸 실감했다. 다시 잡은 뒤에 코포를 2번 쳤는데, 한 번은 2솔 한 번은 1솔에 그쳤다. 사진 올리기 귀찮은 것도 있고 아직 둘 다 레이팅 반영이 안 된 상태라 사진은 생략하고 그래도 여름에는 무조건 C까진 푼다는 마인드였는데 이렇게 C를 못 푸니까 못해진 게 .. 2023. 1. 10.
백준(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.

티스토리툴바