[실버 3] 백준 6666 - Help Me with the Game (파이썬)
[실버 3] 백준 6666 - Help Me with the Game (파이썬)
2025.07.31분류 : 구현링크 : https://www.acmicpc.net/problem/6666풀이문제집에서 이거 안풀면 꿈에서 나온다는 말이 있어서 찾아보게된 문제이며, 문제 번호부터가 6666으로 예사롭지가 않다.근데 진짜 문제도 예사롭지 않다.입력을 한번 봐보자+---+---+---+---+---+---+---+---+|.r.|:::|.b.|:q:|.k.|:::|.n.|:r:|+---+---+---+---+---+---+---+---+|:p:|.p.|:p:|.p.|:p:|.p.|:::|.p.|+---+---+---+---+---+---+---+---+|...|:::|.n.|:::|...|:::|...|:p:|+---+---+---+---+---+---+---+---+|:::|...|:::|...|:::|....
[실버 2] 백준 11279 - 최대 힙 (파이썬)
[실버 2] 백준 11279 - 최대 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/11279풀이백준 1927과 비슷한 문제이다. 1927 최소 힙 문제에서는 정석대로 heap에 값을 양수로 넣었지만, 이번 문제는 최대 힙을 구하는 문제이기에, -를 붙여서 음수로 넣어주면 힙에서는 최대 힙으로 정렬되게 된다.이때 문제점은 pop 할때도 음수로 나오기에, 다시한번 -를 붙여주면, 최대 힙으로 출력 할 수 있다.코드# 백준 11729 - 최대 힙import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = []for i in range(N) : x = int(input()) if x == 0 : if len(heap) > ..
[실버 2] 백준 1927 - 최소 힙 (파이썬)
[실버 2] 백준 1927 - 최소 힙 (파이썬)
2025.07.29분류 : 자료구조링크 : https://www.acmicpc.net/problem/1927풀이힙의 기초적인 문제이다. 사실 시간초과가 나긴했는데, sys.stdin.readline을 고려하지 못했다.문제에서는 N이 최대 10만개이기 때문에 단순히 input()으로만으로는 당연히 시간 초과가 날 수 밖에 없다.문제에서 N을 입력받고, 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 X가 주어진다고 한다.X가 0이 아닌 경우에는 배열에 자연수 X를 넣고, 0이라면 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하면 된다.이에 적합한 자료구조는 heap이기에 아래와 같은 코드로 작성하였다.코드# 백준 1927 - 최소 힙import heapqimport sysinput = sys.stdin.r..
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
2025.07.17분류 : 브루트포스 + 자료구조링크 : https://www.acmicpc.net/problem/11578풀이1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.A = [list(map(int, input().split()))[1:] for _ in range(M)]A = [set(a) for a in A]각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.set(a)로 변환해서 나중에 합집한 연산을 쉽게 ..
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
2025.07.11https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..
[골드 5] 백준 2591 - 숫자카드 (파이썬)
[골드 5] 백준 2591 - 숫자카드 (파이썬)
2025.06.20https://www.acmicpc.net/problem/2591풀이34까지의 숫자 카드가 있을 때, 주어진 숫자 문자열 S를 한 자리 또는 두 자리 숫자로 쪼개어 카드 조합을 만드는 방법의 수를 구하는 문제이다. 단, 앞자리가 0이면 안 되고, 두 자리 수는 134 사이의 유효한 카드 번호여야 한다.D[i]: 문자열 S의 앞에서 i자리까지 만들 수 있는 카드 조합 수점화식한 자리 수 (S[i-1])가 '0'이 아니면 D[i] += D[i-1]두 자리 수 (S[i-2:i])가 '10' ~ '34' 범위에 속하면 D[i] += D[i-2]S = input()D = [0] * (len(S) + 1) # D[0] ~ D[len(S)]D[0] = 1 # 빈 문자열은 1가지 방법 (기저 조건)for i in ..
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
2025.04.16https://www.acmicpc.net/problem/1038풀이감소하는 수란 각 자릿수가 왼쪽부터 오른쪽으로 감소하는 수이다.예를 들어서, 321, 740, 1 , 20 이런식을 의미한다.0부터 9876543210 까지 총 1023개의 감소하는 수가 존재한 다는것을 알 수 있다.입력 N이 주어졌을때, N번째 감소하는 수를 출력하는 문제이다.만약 존재하지 않으면 -1을 출력해야 한다.for i in range(1, 11): for combination in combinations(list(range(10)), i):combinations(range(10), i)는 0~9중 i개를 뽑는 조합을 구한다예를 들어서 i 가 2라면 (0, 1), (0, 2), … , (8, 9)와 같은 모든 조합이 나온..
백준 31962 - 등교 (파이썬)
백준 31962 - 등교 (파이썬)
2025.03.26https://www.acmicpc.net/problem/31962풀이학생 N명이 학교 까지 가는데 S[i] 분이 걸리고, 등교 준비 시간으로 T[i]분이 필요하다.등교 마감 시간 X분 전에 도착해야한다.이때 등교 가능한 학생 중 등교 시간이 가장 오래 걸리는 학생의 등교 시간(S[i])를 구하는 문제이다.단, 어떤 학생도 등교할 수 없다면 -1을 출력해야한다.즉, 각 학생에 대해서 S[i] + T[i]의 값이 X 보다 작거나 같음을 만족하면, max_time을 업데이트 하는 방식으로 풀수 있다.코드# 백준 31962 - 등교# 분류 : 구현N, X = map(int, input().split())S = [0] * NT = [0] * Nfor i in range(N) : S[i], T[i] = ma..
백준 11726 - 2 x n 타일링 (파이썬)
백준 11726 - 2 x n 타일링 (파이썬)
2025.02.21분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/11726풀이점화식을 새워야 한다. 일단 An : 2 * n 타일을 1 * 2, 2 * 1 타일로 채우는 경우의 수를 생각해야한다.An = A(n - 1) + A(n - 2) 라는 점화식을 세울 수 있다.즉 이 문제를 생각해 보면, 숫자가 너무 커지기 때문에 일단 10007로 나눈다는 조건을 생각해야한다.먼저 dp 배열에 들어갈 초기 값을 생각한다.1번의 dp는 2 * 1 타일에 들어 갈수 있는 타일은 1개이다.2번의 dp는 2 * 2 타일에 들어 갈 수 있는 타일은 총 2개이다.1 * 2 타일 2개인 방법 1개2 * 1 타일 2개인 방법 1개예시를 생각해보자, 2 * 5 크기의 직사각형을 채운 한 가지 방법의 예를 확인..