[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
2025.06.26https://www.acmicpc.net/problem/1113풀이높은 정보가 주어진 N * M 격자판이 존재한다.외곽은 절대 물을 담을 수 없고, 안쪽에 고인 물의 양을 계산해야한다.물은 본의의 높이보다 낮은 곳에 채워질 수 있다.각 칸에 고일 수 있는 물의 양을 계산해서 전체 합을 출력한다.결국 BFS로 해결해야 한다고 생각된다.모든 칸을 순회하면 (i, j) 칸에 물 1단계씩 채워보며 시도한다.채웠을 때 외곽까지 닿을 수 있다면 물은 새기 때문에 그만 둔다.외곽까지 닿지 않으면 물이 고일 수 있으므로 해당 칸 높이를 올리고 answer += 1을 진행한다.이 과정을 해당 칸에서 물이 넘칠 때 까지 반복한다.BFS 탐색으로 물이 새는지 확인하기 위해서 다음과 같이 정의 했다.while True : ..
[실버 2] 백준 13423 - Three Dots
[실버 2] 백준 13423 - Three Dots
2025.06.25https://www.acmicpc.net/problem/13423풀이다음 조건을 만족하는 수열 내 세 수 a, b, c의 개수를 찾는것이다.a b - a = c - b, 즉 등차수열 (공차 일정한 수열)정렬된 수열 A에서 두 수 A[i], A[j]를 선택하고, 공차를 구해서 등차수열의 세 번째 수 c = 2 * A[j] - A[i]가 A에 존재하는지를 판단한다.A는 정렬되어 있지만, 존재 여부를 빠르게 체크하기 위해 set으로도 관리한다.a 코드# 백준 13423 - Three Dots# 분류 : 자료구조T = int(input())for _ in range(T) : N = int(input()) A = list(map(int, input().split())) S = set(A) ..
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
2025.06.25https://www.acmicpc.net/problem/2878풀이총 M개의 캔디를 N명의 학생에게 나눠줘야 한다.각 학생은 자신이 원하는 캔디 수가 있고, 그보다 적게 받으면 “화남 지수”가 받은 개수^2로 증가한다.M개를 어떻게 배분해야 전체 화남 지수의 합이 최소가 되도록 하는지가 문제이다.사용한 풀이 전략은 다음과 같다.1. 이분 탐색을 이용해 평균 컷 구하기학생마다 min(A[i], mid) 만큼 주는 방식을 생각한다.이 때 mid를 조절하며, 총 줄 수 있는 캔디가 M 이상이 되는 최소 mid를 찾는다.mid 이상을 주면 안 되고, 모든 학생에게 최대한 공평하게 적게 주자는 전략.2. 이분 탐색 후 배분최적의 컷 수 p를 찾았으면,모든 학생에게 min(p - 1, A[i])만큼 먼저 배분한다..
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
2025.06.25https://www.acmicpc.net/problem/12871풀이두 문자열 S와 T가 무한히 반복된다고 할 때, 그 두 무한 문자열이 같은지 확인하는 문제이다.S = ‘abab’이고 T = ‘ababab’면 무한히 반복하면 둘 다 “abababababab…” 같은 문자열이 된다면 1을 출력하고 아니면 0을 출력한다.결국 핵심 아이디어는 문자열의 기본 단위를 구해서 비교하는 것이다.def find_basis(s): ...find_basis함수는 문자열 s의 반복되는 최소 단위를 찾아준다.예를 들어서 abab가 들어가면 ab를 반환하고, aaaa 가 들어가면 a를 반환한다.작동 방식은 다음과 같다.문자열 길이의 약수들을 기준으로 자른다.해당 길이로 자른 모든 조각이 동일한지 확인한다.동일하면 그것..
[실버 1] 백준 1141 - 접두사 (파이썬)
[실버 1] 백준 1141 - 접두사 (파이썬)
2025.06.24https://www.acmicpc.net/problem/1141풀이이 문제는 주어진 문자열들 중 다른 문자열의 접두사가 아닌 문자열의 개수를 세는 것이다.N = int(input())S = [input() for _ in range(N)]S = list(set(S)) # 중복 제거먼저 문자열 개수 N을 입력받고, 문자열 리스트 S를 구성한 뒤 set()을 이용해 중복 문자열을 제거한다.prefix = [False] * Nprefix[i]는 S[i]가 다른 문자열의 접두사인지 여부를 저장하는 배열이다.for i in range(len(S)) : for j in range(len(S)) : if i == j : continue if len(S[i]) >..
[골드 4] 백준 16120 - PPAP (파이썬)
[골드 4] 백준 16120 - PPAP (파이썬)
2025.06.23https://www.acmicpc.net/problem/16120풀이문자열이 PPAP 규칙에 따라서 만들어졌는지 판별하는 문제이다.기본적인 규칙은 PPAP는 P로 줄일 수 있다.PPPAP는 PPAP + P → PP가 되지 않으므로 올바른 형태가 아니다.줄이고 줄이다가 마지막에 P 하나만 남으면 PPAP 문자열이라고 한다.S = input()stack = []입력 문자열 S를 한글자씩 처리할 것이며, 처리 중간 결과를 저장하기 위해서 스택을 사용한다.for i in range(len(S)) : stack.append(S[i])입력 문자열의 각 문자를 stack에 순차적으로 쌓는다.while len(stack) >= 4 and "".join(stack[-4:]) == "PPAP" : for _ ..
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
2025.06.22https://www.acmicpc.net/problem/1670풀이사람 수는 짝수 N이고, 각 사람은 한 명과만 악수할 수 있으며, 악수 선이 교차하지 않아야 한다.이는 DP로 해결할 수 있으며, 다음 점화식을 따른다.이 문제는 카탈란 수(Catalan Number) 문제 유형의 대표적인 예다.핵심은 다음과 같다N명의 정상 중 한 명을 기준으로 짝을 지었을 때, 남은 좌우 인원들도 각각 교차 없이 짝을 지어야 한다.이를 이용하면 DP 점화식을 다음과 같이 세울 수 있다.D[0] = 1 # 아무도 없을 때는 1가지 (아무것도 안 하는 경우)D[2] = 1 # 두 명이 있을 때는 1가지D[n] = D[0]*D[n-2] + D[2]*D[n-4] + D[4]*D[n-6] + ... + D[n-2]*D[0]..
[실버 1] 백준 12849 - 본대 산책 (파이썬)
[실버 1] 백준 12849 - 본대 산책 (파이썬)
2025.06.21https://www.acmicpc.net/problem/12849풀이총 8개의 장소(0~7번 정점)로 구성된 캠퍼스가 있고, 하루에 1분씩 이동할 수 있음.이동 가능한 경로는 문제에서 고정되어 있음 (총 12개 간선)0번에서 시작해 정확히 D분 뒤 다시 0번에 도착할 수 있는 모든 경로의 수를 구하는 문제.단, 결과는 10^9 + 7로 나눈 나머지를 출력.adj = [[] for _ in range(8)]edge = [ ... ] # 문제에서 주어진 12개 간선for a, b in edge: adj[a].append(b) adj[b].append(a)먼저 인접 리스트를 정의하고, adj[i]는 i번 정점에서 갈 수 있는 이웃 정점을 리스트로 담고 있다.양방향 그래프이므로 adj[a].app..
[골드 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 ..
[실버 1] 백준 1446 - 지름길 (파이썬)
[실버 1] 백준 1446 - 지름길 (파이썬)
2025.05.27https://www.acmicpc.net/problem/1446풀이일반 도로는 i → i+1로 이동하면서 1km가 걸린다.지름길은 입력으로 주어지며 (a, b, c)의 의미는 a → b로 가는 지름길이 있고, 길이는 c이다.목표는 0 → D까지 가는 데 걸리는 최단 거리를 구하는 것.N, D = map(int, input().split())adj = [[] for _ in range(D + 1)]D까지의 거리이므로 정점은 0부터 D까지 총 D + 1개이다.adj[i]는 정점 i에서 갈 수 있는 목적지, 비용 리스트이다.for _ in range(N): a, b, c = map(int, input().split()) if b 지름길 정보는 b가 D보다 큰 경우 무의미하므로 무시하며, 지름길은 ..
[골드 3] 백준 1937 - 욕심쟁이 판다 (파이썬)
[골드 3] 백준 1937 - 욕심쟁이 판다 (파이썬)
2025.05.26https://www.acmicpc.net/problem/1937풀이N×N 크기의 숲이 있다.각 칸에는 대나무가 자라고 있고, 숫자는 대나무의 양이다.판다는 현재 위치보다 더 많은 양의 대나무가 있는 칸으로만 이동할 수 있다.상하좌우로 이동 가능하다.판다는 최대한 많은 날을 살아야 하므로, 이동할 수 있는 경로 중 가장 긴 경로의 길이를 구해야 한다.풀이 아이디어특정 위치 (r, c)에서 시작해 이동할 수 있는 최대 경로를 구한다.이미 계산한 값은 cache[r][c]에 저장해 중복 호출을 방지한다 (메모이제이션).결국 각 칸에서 출발했을 때의 최대 이동일수 중 최댓값이 정답이다.N = int(input())F = [list(map(int, input().split())) for _ in range(N)..
[골드 3] 백준 1613 - 역사 (파이썬)
[골드 3] 백준 1613 - 역사 (파이썬)
2025.05.25https://www.acmicpc.net/problem/1613풀이N: 사건 개수 (노드 수), K: 사건 간 전후관계의 개수 (방향 그래프 간선)각 입력 (a, b)는 a 사건이 b 사건보다 먼저 일어났음을 의미 → 단방향 간선S개의 질문: a와 b 중 누가 먼저인지 판단먼저 입력 처리 및 인접리스트를 구현한다.adj = [[] for _ in range(N)]for _ in range(K): a, b = map(int, input().split()) a -= 1 b -= 1 adj[a].append(b)방향 그래프 형태로 인접 리스트를 구성한다.모든 정점에서 BFS를 돌려 도달 가능한 노드를 기록한다.visit = [[False] * N for _ in range(N)]for ..
[실버 2] 백준 1058 - 친구 (파이썬)
[실버 2] 백준 1058 - 친구 (파이썬)
2025.05.24https://www.acmicpc.net/problem/1058풀이사람 수 N명각 사람이 다른 사람과 친구인지 여부가 Y 또는 N으로 주어짐직접 친구이거나 친구의 친구(2-친구)까지를 포함해 가장 많은 친구 수를 가지는 사람을 찾아 그 수를 출력접근 방법각 사람을 기준으로 BFS 수행거리가 1 또는 2인 사람 수를 세면 된다 (자기 자신은 제외)각 사람마다 세서 그 중 최대값을 구함조금 생각해야하는 부분dist[j] visit 배열과 dist 배열을 통해 BFS 방문 여부 및 거리 체크N = int(input())F = [input() for _ in range(N)]N은 사람수 F[i]는 i번째 사람의 친구 관계 문자열을 나타낸다.visit = [False] * Ndist = [-1] * Nqueue..
[실버 2] 백준 14620 - 꽃길 (파이썬)
[실버 2] 백준 14620 - 꽃길 (파이썬)
2025.05.23https://www.acmicpc.net/problem/14620풀이모든 좌표 중 3개를 조합으로 고른다.각 조합마다 꽃이 겹치지 않는지, 범위를 벗어나지 않는지 확인한다.문제가 없다면 그 조합의 총 비용을 계산하고 최소값을 갱신한다.from itertools import combinationsN = int(input())A = [list(map(int, input().split())) for _ in range(N)]N은 격자 크기.A는 각 칸의 비용을 저장한 2차원 배열.coordinates = [(i, j) for i in range(N) for j in range(N)]모든 좌표 (i, j)를 저장.dr = [0, 0, 1, -1]dc = [1, -1, 0, 0]answer = 1e9상하좌우 방..
[실버 1] 백준 1189 - 컴백홈 (파이썬)
[실버 1] 백준 1189 - 컴백홈 (파이썬)
2025.05.22https://www.acmicpc.net/problem/1189풀이현재 위치에서 이동 횟수를 세면서 목적지 (0, C-1)에 도달하는 모든 경로의 수를 세는 문제.단, 정확히 K칸 이동한 경로만 유효함.이동은 상하좌우 가능하며, T는 막힌 칸이므로 이동 불가.시작 위치는 (R-1, 0) 여기가 ‘집’.목표 위치는 (0, C-1) 여기가 ‘학교’.DFS로 이동 경로를 탐색하면서 K-1번 이동해야 하며, 마지막 위치가 (0, C-1)일 때만 카운트한다.방문 체크는 used 리스트로 관리한다.백트래킹으로 이전 경로로 되돌아가 다른 경로 탐색을 계속used를 리스트 대신 set으로 바꾸면 in 검사 속도가 O(n) → O(1)로 줄어 성능 향상 가능def dfs(r, c, k, used): if k ==..