Programming/백준
[골드 5] 백준 15681 - 트리와 쿼리 (파이썬)
[골드 5] 백준 15681 - 트리와 쿼리 (파이썬)
2025.04.28https://www.acmicpc.net/problem/15681풀이루트가 R인 트리가 주어짐각 쿼리는 정점 U를 루트로 하는 서브트리의 정점 개수를 묻는다여러 쿼리에 대해 빠르게 답변해야 하므로 DFS를 활용한 서브트리 크기 미리 계산이 핵심adj = [[] for _ in range(N)]adj[u]에 연결된 정점들 v를 저장하여 무방향 트리를 구성한다.D = [0] * ND[u]는 u를 루트로 하는 서브트리의 정점 수를 나타낸다.def dfs(u): visit[u] = True D[u] = 1 # 자기 자신 포함 for v in adj[u]: if not visit[v]: dfs(v) D[u] += D[v]DFS를 통한 서브트리..
[실버 2] 백준 11060 - 점프 점프 (파이썬)
[실버 2] 백준 11060 - 점프 점프 (파이썬)
2025.04.27https://www.acmicpc.net/problem/11060풀이각 칸마다 점프할 수 있는 최대 칸 수가 주어짐0번 인덱스부터 시작해서 N-1번 인덱스로 가야 함최소 몇 번의 점프로 도달할 수 있는지 구함못 가면 -1 출력N = int(input()) # 칸의 수A = list(map(int ,input().split())) # 각 칸에서 점프 가능한 최대 거리A[i]는 i번 칸에서 최대 A[i]칸 까지 점프가 가능하다는 뜻을 의미한다.D = [1e9] * N # DP 배열, 최소 점프 횟수를 저장 (초기값은 매우 큰 값)D[N - 1] = 0 # 마지막 칸은 도달했으므로 점프 횟수 0for i in range(N - 2, -1, -1): # 뒤에서부터 탐색 for j in rang..
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)
2025.04.27https://www.acmicpc.net/problem/9657풀이돌이 N개 있을 때, SK와 CY가 번갈아 가면서 돌을 가져간다.한번에 1, 3, 4개의 돌만 가져갈 수 있다.마지막 돌을 가져가는 사람이 이긴다.SK가 먼저 시작할 때, 누가 이기는지 판단하는 문제이다.D[i]를 i개의 돌이 있을 때 SK가 이길수 있는가를 나타내는 Boolean 배열로 설정한다.True → SK가 이기는 경우Fasle → CY가 이기는 경우핵심은 현재 상태에서 내가 이길 수 있는 수를 선택하면 이긴다는 점이다.즉, D[i] = not D[i - 1] or not D[i - 3] or not D[i - 4] 이다.초기 조건은 다음과 같이 설정한다.D[1] = True # SK가 1개 가져가서 승D[2] = False..
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
2025.04.26https://www.acmicpc.net/problem/1655풀이매번 새로운 수를 입력받으면, 지금까지의 수 중에서 중간값을 출력해야 한다.수의 개수가 홀수이면, 정렬했을 때 가운데 수가 중간값이고수의 개수가 짝수이면, 가운데 두 수 중에서 작은 수가 중간값이다.왼쪽 힙 (left): 최대 힙. 중간값보다 작거나 같은 값 저장 (최댓값이 top)오른쪽 힙 (right): 최소 힙. 중간값보다 큰 값 저장 (최솟값이 top)중간값 위치항상 left가 right보다 같거나 1개 많도록 유지하면,중간값은 left의 루트에 위치함 (-left[0])heapq.heappush(left, -X)우선 left (최대 힙)에 넣음 (-부호로 최대 힙을 구성)if right and -left[0] > right[0]..
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
2025.04.26https://www.acmicpc.net/problem/3197풀이백조의 호수 문제는 BFS를 통해서 풀이가 가능하다.문제에서 요구하는 조건은 호수에 얼음이 덮여있다.얼음으로 뒤덮인 호수에 백조 두 마리가 있음물은 백조가 지나갈 수 있지만 얼음은 못 감매일 얼음이 물과 접촉한 부분부터 녹음두 백조가 만날 수 있는 최소 날짜를 구하는 문제입력 처리 및 초기 세팅을 진행R, C = map(int, input().split())A = [list(input()) for _ in range(R)]R, C와 맵을 2차원 리스트로 저장한다.백조 위치 탐색swans = []for i in range(R): for j in range(C): if A[i][j] == "L": swa..
[골드 5] 백준 12919 - A와 B 2 (파이썬)
[골드 5] 백준 12919 - A와 B 2 (파이썬)
2025.04.26https://www.acmicpc.net/problem/12919풀이문자열 S에서 시작하여 문자열 T를 만들 수 있는지 판단하는 문제이다.수행할 수 있는 연산은 다음과 같다,문자열 뒤에 ‘A’ 추가문자열을 뒤집고 뒤에 ‘B’ 추가하지만 이 코드에서는 역방향으로, 즉 T에서 시작해서 S로 갈 수 있는지 확인한다.def dfs(t): if len(t) == len(S): return t == S현재 문자열 t의 길이가 S와 같아졌다면 t == S 인지 비교해서 결과를 반환한다.if t[-1] == "A": if dfs(t[:-1]): return True재귀 조건으로 문자열 끝이 A라면 A를 추가한 결과였을 수 있으므로 마지막 문자를 제거하고 재귀를 호출한다.if t[0..
[골드 2] 백준 2381 - 최대 거리 (파이썬)
[골드 2] 백준 2381 - 최대 거리 (파이썬)
2025.04.25https://www.acmicpc.net/problem/2381풀이N = int(input())P = [list(map(int, input().split())) for _ in range(N)]N개의 점을 입력받고 리스트 P에 저장한다.max_plus = -1e9min_plus = 1e9for x, y in P : max_plus = max(max_plus, y + x) min_plus = min(min_plus, y + x)(x + y)의 최대값 최소값을 계산한다.max_minus = -1e9min_minus = 1e9for x, y in P : max_minus = max(max_minus, y - x) min_minus = min(min_minus, y - x)(y - x)의..
[실버 4] 백준 2980 - 도로와 신호등 (파이썬)
[실버 4] 백준 2980 - 도로와 신호등 (파이썬)
2025.04.25https://www.acmicpc.net/problem/2980풀이길이 L인 도로 위에 N개의 신호등이 있음각 신호등은 D(거리), R(빨간불 지속 시간), G(초록불 지속 시간)의 정보를 가짐차량은 초당 1m 이동빨간불이면 정지, 초록불이면 통과도로의 끝까지 도달하는 데 걸리는 시간 출력사실 이부분에서 계속 오류가 나서 봤더니 “)” 위치가 왜 뒤로 가 있던건지,, 하,,N, L = map(int, input().split())info = [list(map(int, input().split())) for _ in range(N)]N, L, info는 각각 신호등의 개수, 도로 길이, 각 신호등의 위치 D, 빨간불 R, 초록불 G를 저장한다.state = ['R'] * Nremain = [info[i]..
[골드 3] 백준 16437 - 양 구출 작전 (파이썬)
[골드 3] 백준 16437 - 양 구출 작전 (파이썬)
2025.04.24https://www.acmicpc.net/problem/16437풀이각 섬에는 양(S) 또는 늑대(W)가 있으며,한 섬에 있는 동물들은 연결된 부모 섬(루트 방향)으로 이동한다.만약 늑대 수가 양보다 많으면 그만큼 양이 잡아먹힌다.목표: 1번 섬(루트)에 도착할 수 있는 양의 최대 수 구하기입력처리는 다음과 같이 지정한다.N = int(input()) # 섬의 개수A = [0] * N # 각 노드에 있는 양 또는 늑대 수 (양은 양수, 늑대는 음수)child = [[] for _ in range(N)] # 트리 구조 저장 (부모 -> 자식)for i in range(1, N) : t, a, p = input().split() a = int(a) p = int(p) - 1 ..
[골드 1] 백준 2213 - 트리의 독립집합 (파이썬)
[골드 1] 백준 2213 - 트리의 독립집합 (파이썬)
2025.04.24https://www.acmicpc.net/problem/2213풀이정점 포함 vs 미포함 두 가지 상태로 나눠서 각각 최적값을 저장서브트리의 정보를 재귀적으로 계산하면서 합산각 노드가 포함되는 경우, 자식 노드는 반드시 제외각 노드가 포함되지 않는 경우, 자식 노드는 포함 여부 선택 가능D[u] : 정점 u를 포함하는 경우 최대 독립집합 가중치 합E[u] : 정점 u를 포함하지 않는 경우 최대 독립집합 가중치 합D_sol[u] : 정점 u를 포함하는 경우 선택된 정점 목록E_sol[u] : 정점 u를 포함하지 않는 경우 선택된 정점 목록DFS는 다음과 같이 처리한다.def dfs(u): visit[u] = True D[u] = A[u] # 자기 자신 포함 D_sol[u].append(..
[실버 4] 백준 11508 - 2+1 세일 (파이썬)
[실버 4] 백준 11508 - 2+1 세일 (파이썬)
2025.04.24https://www.acmicpc.net/problem/11508풀이N개의 물건 가격이 주어진다2 + 1세일은 물건을 세개 살때 가장 싼 한개는 무료로 적용한다.이때, 최소 비용으로 구매하는 금액을 구하라아이디어비싼 순으로 정렬후3개씩 묶어서, 그 중 가장 싼 물건은 빼기discount = 0for i in range(0, N, 3) : if i + 2 3개씩 묶어서 매 세번째 아이템을 할인 대상으로 적용한다.단, 범위를 벗어나지 않도록 if i + 2 print(sum(C) - discount)전체 가격 합에서 할인액을 뺴서 최종 결제 금액을 출력한다.코드# 백준 11508 - 2+1 세일# 분류 : 그리디N = int(input())C = []for i in range(N) : C.app..
[골드 5] 백준 15989 - 1, 2, 3 더하기 4 (파이썬)
[골드 5] 백준 15989 - 1, 2, 3 더하기 4 (파이썬)
2025.04.23https://www.acmicpc.net/problem/15989풀이정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라같은 수라도 순서가 다른 것은 같은 경우로 취급한다.예를 들어 3 = 1 + 2 와 2 + 1은 같은 경우로 처리된다.DP 배열을 아래와 같이 정의한다.D = [[0] * 10001 for _ in range(4)]D[i][j]는 1부터 i까지의 숫자만 사용해서 j를 만드는 경우의 수를 의미한다.예를 들어서 D[2][4]는 1, 2만 사용해서 4를 만드는 방법의 수를 나타낸다.점화식은 아래와 같이 구성한다.D[0][0] = 1for i in range(1, 4): # 1, 2, 3 사용 for j in range(10001): D[i][j] = D[i - ..
[골드 3] 백준 2629 - 양팔저울 (파이썬)
[골드 3] 백준 2629 - 양팔저울 (파이썬)
2025.04.23https://www.acmicpc.net/problem/2629풀이추는 영쪽 저울에 올릴 수 있다.이떄 만들 수 있는 무게 차를 추들을 사용해서 계산한다.D[i][j]는 앞에서 i개의 추를 사용해서 j - zero 만큼의 무게 차이를 만들 수 있는가?N = int(input()) # 추의 개수A = list(map(int, input().split())) # 추의 무게 리스트M = int(input()) # 구슬의 개수B = list(map(int, input().split())) # 구슬의 무게 리스트zero = 40001로 초기화 해주었다. 그 이유는 인덱스에서 음수를 표현하기 위해서 기준점 0을 40001로 설정하였다.점화식의 초기 값을 다음과 같이 설정한다.D[0][zero] = True..
[골드 2] 백준 13334 - 철로 (파이썬)
[골드 2] 백준 13334 - 철로 (파이썬)
2025.04.22https://www.acmicpc.net/problem/13334풀이N개의 사람 정보 (집과 사물실의 좌표)철로의 길이는 D로 고정됨하나의 철로로 최대 몇 명을 커버할 수 있는가?즉 철로구간[a, a + D] 내에 (start, end) 모두 포함된 사람이 최대 몇명인지?일단 코드를 잘못 짠 부분이 있다.for i in range(N) : pq.put(X[i][1])그냥 끝점 기준으로 넣고, 무조건 X[i][1] + D를 오른쪽 끝이라 생각해버렸다.시작점이 X[i][0] 보다 작은 사람도 같이 포함될 수 있다.이 뿐만 아니라 시작점보다 왼쪽인 선분을 제외하기 않았다.철로 구간 [x, x + D] 안에 들어오려면, start ≥ x and end ≤ x + D 여야한다.따라서 end를 기준으로 정렬..
[골드 4] 백준 16562 - 친구비 (파이썬)
[골드 4] 백준 16562 - 친구비 (파이썬)
2025.04.22https://www.acmicpc.net/problem/16562풀이친구끼리 돈을 모아서 대표 한 명의 친구비만 내면 된다.모든 사람들과 친구가 되려면 각 친구 그룹당 최소 친구비만 내면 된다.이때 전체 친구비가 K원 이하라면 총합을 출력, 초과하면 “Oh no”를 출력for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 adj[u].append(v) adj[v].append(u)친구 관계 입력을 받는다 이때 0-Based Index를 통해서 1씩 빼주고 무방향 그래프로 설정 한다.visit = [False] * Ntotal = 0for i in range(N): if visit[i]: cont..