Programming
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
2025.07.03https://www.acmicpc.net/problem/20188풀이트리 DP 또는 서브트리 크기 기반의 조합 계산을 사용한 문제이다.무방향 트리이며, 등상 마니아들은 경로 (a, b, c)를 선택할 때 항상 a → b → c 순으로 이동한다.단, b는 a와 c의 LCA(최소 공통 조상)이어야 한다.모든 (a, b, c) 쌍에서의 경우의 수를 계산해야한다.사용한 아이디어어떤 간선을 제거하면 트리가 두 개의 서브트리로 나뉘게 된다.해당 간선을 통해 만들어지는 (a, b, c)의 경우의 수는 다음 두개로 나뉜다.서브 트리 내부에서 a, c를 고르고 b가 그 루트인 경우 → sizes[i] * (sizes[i] - 1) / 2서브트리와 바깥에서 a, c를 하나씩 고르고 b가 그 경계인 경우 → sizes[i..
[실버 2] 백준 17213 - 과일 서리 (파이썬)
[실버 2] 백준 17213 - 과일 서리 (파이썬)
2025.07.03https://www.acmicpc.net/problem/17213풀이서로 다른 N개의 과일 중에서 M개를 훔쳐올 때, 적어도 1개씩은 훔치는 경우의 수를 구하는 문제이다.적어도 1개씩 N종료의 과일을 가져온다는 조건은 곧 M개의 과일을 N개의 상자에 각각 적어도 1개씩 넣는 방법의 수를 묻는 것과 같다.이는 중복 조합의 문제로 환원되며, 중복 조합의 식은 다음과 같다.answer = 1for i in range(1, M - N + 1) : answer *= (M - i) answer //= i위 코드는 nCr의 계산 중에서 n = M - 1, r = M - N을 계산하는 것이다.파이썬 내장 함수 없이 직접 계산이 가능하다. (Collection 모듈)코드# 백준 17213 - 과일 서리# 분..
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
2025.07.02https://www.acmicpc.net/problem/1655풀이max_pq는 왼쪽 절반, 즉 중간값 이하를 담고 최대 힙으로 운용한다. (파이썬에서는 -값을 넣어 사용)min_pq는 오른쪽 절반, 즉 중간값 초과를 담고 최소 힙으로 운용한다.입력값과 max_pq, min_pq에서 하나씩 빼서 총 3개의 숫자 후보를 만들고 정렬 후 재분배한다.중간값은 항상 max_pq의 top인 -max_pq[0]이 된다.max_pq = [1e9]min_pq = [1e9]1e9를 미리 넣어둔다. 즉 힙이 비어있을때 heappop 하기 위한 임시값이다.하지만 이건 비정상적인 초기값이고, 결과적으로 정답이 이상해 질 수 도 있다.a = [A[i]]a.append(-heapq.heappop(max_pq))a.append(..
[골드 4] 백준 1327 - 소트 게임 (파이썬)
[골드 4] 백준 1327 - 소트 게임 (파이썬)
2025.07.02https://www.acmicpc.net/problem/1327풀이배열 A를 K개의 연속된 수만큼 뒤집는 연산을 통해 오름차순 [1, 2, ..., N]을 만드는 최소 횟수를 구하는 문제다.상태공간이 최대 N!이므로, 모든 경우를 다 탐색하면 안 되고, BFS로 최소 횟수를 탐색해야 한다.리스트 상태를 hash 값으로 바꿔서 방문 여부를 체크한다.def list_to_hash(a): hash = 0 for i in range(len(a)): hash += a[i] hash *= (len(a) + 1) return hash리스트를 정수형 hash 값으로 변환.(다만 완전한 유일성 보장은 안 됨 → tuple(a)을 쓰는 것이 더 안전)단순한 방식이지만, 충돌 가능..
[플래티넘 5] 백준 1102 - 발전소 (파이썬)
[플래티넘 5] 백준 1102 - 발전소 (파이썬)
2025.07.01https://www.acmicpc.net/problem/1102풀이발전소가 N개 있고, 어떤 발전소는 작동 중(y), 어떤건 꺼져 있다. (N)작동 중인 발전소가 다른 발전소를 켜는 데 드는 비용이 주어진다. (A[i][j])발전소를 P개 이상 켜기 위해 최소 비용을 구하는 문제이다.켜는 순서와 조합에 따라 총 비용이 달라진다.즉 최적의 순서를 구해야한다.주요 알고리즘은 비트마스킹 + 메모이제이션을 사용한다.입력 처리는 다음과 같이 비교적 간단하게 입력 받는다.N = int(input())A = [list(map(int, input().split())) for _ in range(N)]S = input()P = int(input())캐시 초기화를 위해서 65536개의 캐시를 생성한다.cache = [-..
[골드 5] 백준 1354 - 무한 수열 2 (파이썬)
[골드 5] 백준 1354 - 무한 수열 2 (파이썬)
2025.07.01https://www.acmicpc.net/problem/1354풀이A(0) = 1 A(n) = A(n // P - X) + A(n // Q - Y) (n > 0)주어진 N에 대해서 A(N)을 구하는 문제이다.기본 수열 정의A(n)은 자기보다 작은 인덱스들의 결과를 이용해 계산됨 → 전형적인 DP 구조문제점N이 최대 10^12이기 때문에 일반적인 리스트 기반 DP(dp = [0]*(N+1))는 메모리 초과 → 딕셔너리 기반 메모이제이션 사용점화식 재귀 정의점화식에 따라 다음과 같이 재귀함수 작성A(n) = A(n // P - X) + A(n // Q - Y)기저 조건n 메모이제이션계산된 결과는 cache[n]에 저장해서 중복 호출 방지def dp(n): if n 재귀 함수를 정의한다.시간복잡도..
[골드 4] 백준 17404 - RGB거리 2 (파이썬)
[골드 4] 백준 17404 - RGB거리 2 (파이썬)
2025.06.30https://www.acmicpc.net/problem/17404풀이이 문제는 다이나믹 프로그래밍을 사용해서 최소 비용을 계싼하는 문제이다.각 집은 R(0), G(1), B(2) 중 하나의 색으로만 칠해야 하며, 이웃한 집은 같은 색이면 안된다.첫번째 집과 마지막 집도 같은 색이면 안된다.N개의 집이 있고, 각 집의 각 색상별 비용이 주어진다.즉, 첫번째 집과 마지막 집이 같은색이면 안된다는 조건 때문에 기존 RGB 거리 문제보다 살짝 까다롭다.그래서 사용한 전략은 다음과 같다.첫번째 집의 색상을 R, G, B 하나로 고정하고 시작한다. 즉 3가지 경우로 나눠서 각각 따로 계산한다.그 다음 집부터는 기존 RGB거리처럼 dp[i][j] = i번째 집을 j색으로 칠할 때의 최소 비용을 채워나간다.마지막 집..
[실버 4] 백준 9575 - 행운의 수 (파이썬)
[실버 4] 백준 9575 - 행운의 수 (파이썬)
2025.06.30https://www.acmicpc.net/problem/9575풀이for a in A: for b in B: for c in C:세 배열 A, B, C에서 각각 하나씩 고른다 (총 경우의 수는 N × M × K).합 sum = a + b + c가 “행운의 수”인지 판별한다:10으로 나누며 각 자릿수가 5 또는 8만 있는지 확인함.조건을 만족하면 lucky 리스트에 추가.중복 제거 후 행운의 수 개수 출력.while sum > 0: if sum % 10 not in [5, 8]: good = False break sum //= 10sum의 각 자릿수를 검사함.5 또는 8이 아닌 숫자가 있으면 good = False로 탈락.코드# 백준 9575 - 행운..
[골드 4] 백준 14395 - 4연산 (파이썬)
[골드 4] 백준 14395 - 4연산 (파이썬)
2025.06.29https://www.acmicpc.net/problem/14395풀이from collections import dequeS, T = map(int, input().split())visit = set()path = {}queue = deque()queue.append(S)visit.add(S)path[S] = ""입력으로 정수 S, T를 받고 BFS용 자료구조 초기화한다.visit는 중복 연산 방지를 위한 방문 집합을 생성하고, path는 각 숫자에 도달한 연산 문자열을 저장한다.while len(queue) != 0 : u = queue.popleft()BFS 반복문을 시작한다. if u * u “*” 연산을 수행해서 새로운 값이 아직 방문하지 않았고, 10억 이하이면 큐에 넣는다.또한, 연..
[골드 2] 백준 1507 - 궁금한 민호 (파이썬)
[골드 2] 백준 1507 - 궁금한 민호 (파이썬)
2025.06.28https://www.acmicpc.net/problem/1507풀이모든 도시 쌍 사이 최단 거리가 주어졌을 때, 최소한의 도로만으로도 그 최단 거리 정보를 유지할 수 있는지를 묻고 있다.주어진 거리 행렬은 이미 모든 쌍 최단 거리 정보를 담고 있음 (플로이드 이후 결과)어떤 도로 i-j가 다른 경로 i-k-j에 포함되어 있다면, 굳이 필요하지 않음따라서 직접 연결된 간선 중, 다른 경로로 대체 가능한 간선은 제거주요 변수dist[i][j]: 도시 i에서 j까지의 최단 거리need[i][j]: i에서 j까지 직접 연결된 간선이 필요한가 여부impossible: 삼각 부등식이 깨지는 경우 (즉, 입력이 잘못된 경우)N = int(input())dist = [list(map(int, input().split..
[골드 2] 백준 3109 - 빵집 (파이썬)
[골드 2] 백준 3109 - 빵집 (파이썬)
2025.06.28https://www.acmicpc.net/problem/3109풀이가스관이 있는 빵집의 왼쪽 열에서 시작해 오른쪽 열까지 파이프를 설치할 수 있는 최대 개수를 구하는 것이다.'.'은 빈 칸, 'x'는 설치 불가능한 건물파이프는 오른쪽 위 / 오른쪽 / 오른쪽 아래로만 이동 가능파이프는 겹치면 안 됨출발은 각 행의 첫 번째 열 (즉, (i, 0))def dfs(r, c): visit[r][c] = True if c == C - 1: # 오른쪽 끝 도착 return TrueDFS는 3방향 우선순위로 탐색을 진행한다.오른쪽 위 (r - 1, c + 1)오른쪽 (r, c + 1)오른쪽 아래 (r + 1, c + 1)방문한 적 없고 빈 칸이면 DFS 재귀 호출, 도착 성공하면 True ..
[실버 2] 백준 2790 - F7 (파이썬)
[실버 2] 백준 2790 - F7 (파이썬)
2025.06.28https://www.acmicpc.net/problem/2790풀이N명의 학생이 있고 각 학생은 자신이 좋아하는 친구 수 B[i]를 갖고 있을 때, 가능한 한 많은 학생이 자신의 친구 수 조건을 만족하도록 친구를 맺도록 하는 것이다.i번 학생은 정확히 B[i]명의 친구를 갖고 싶어한다결국 이 문제는 B[i]명을 만족시키는 친구 매칭이 가능한 최대 학생 수를 구하는 것이다.이를 해결하기 위해, 학생들을 좋아하는 친구 수 기준으로 정렬하고, 뒤에서부터 만족시킬 수 있는지 확인한다.N = int(input())B = [int(input()) for _ in range(N)]B.sort()학생수와 각 학생이 원하는 친구 수 B[i]를 리스트에 저장한 뒤 오름차순 정렬한다.answer = 0max_val = 0..
[골드 3] 백준 25381 - ABBC (파이썬)
[골드 3] 백준 25381 - ABBC (파이썬)
2025.06.27https://www.acmicpc.net/problem/25381풀이문자열 S가 주어지며, S에서 문자 B는 한번씩만 사용할 수 있다.B앞에 A가 있으면 AB짝을 만든다.B뒤에 C가 있으면, BC 짝을 만든다.AB 또는 BC 쌍을 최대한 많이 만들어야하며, 단 하나의 B는 한번만 사용할 수 있다.B의 위치를 저장하기 위해서 다음과 같이 정의한다.queue = deque()for i in range(len(S)) : if S[i] == 'B' : queue.append(i)문자열에서 B의 인덱스 위치를 모두 deque에 저장하고, 앞뒤에서 모두 사용할 수 있게 deque를 사용한다.다음은 BC를 매칭한다. (왼쪽 → 오른쪽)for i in range(len(S)) : if S[i]..
[골드 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) ..