[실버 3] 백준 28353 - 고양이 카페 (파이썬)
[실버 3] 백준 28353 - 고양이 카페 (파이썬)
2025.04.29https://www.acmicpc.net/problem/28353풀이고양이들의 체중 리스트가 주어지고,두 마리 고양이를 묶을 때, 체중 합이 K 이하이면 1쌍으로 만든다.최대 몇 쌍을 만들 수 있는지를 구하는 문제.A.sort()체중을 오름차순으로 정렬한다. 가장 가벼운 고양이와 가장 무거운 고양이를 매칭해서 최대한 많이 쌍을 만들려고 하기 때문이다.투 포인터는 다음과 같이 준비한다.start, end = 0, N - 1count = 0start는 제일 가벼운 고양이를 가리키며 왼쪽 포인터를 의미한다.end는 제일 무거운 고양이를 가리키며 오른쪽 포인터를 의미한다.count는 만든 쌍의 수를 나타낸다.while start 두 고양이의 체중 합 A[start] + A[end]를 확인하여, 합이 K 이하이..
[골드 3] 백준 3673 - 나눌 수 있는 부분 수열 (파이썬)
[골드 3] 백준 3673 - 나눌 수 있는 부분 수열 (파이썬)
2025.04.29https://www.acmicpc.net/problem/3673풀이길이 N인 수열이 있을 떄,부분 수열의 합이 D로 나누어 떨어지는 경우의 수를 구해라누접합 배열을 만들어서, 누적합을 D로 나눈 나머지를 활용하면 풀이가 가능하다.T = int(input())for _ in range(T): D, N = map(int, input().split()) A = list(map(int, input().split())) psum = [0] * N psum[0] = A[0] for i in range(1, N): psum[i] = psum[i-1] + A[i]누적 합 계산을 진행한다.테스트 케이스 T개 만큼 반복하면서, 각 테스트 케이스마다 나누는 수 D와 배열 크기 N을 ..
[골드 2] 백준 2637 - 장난감 조립 (파이썬)
[골드 2] 백준 2637 - 장난감 조립 (파이썬)
2025.04.28https://www.acmicpc.net/problem/2637풀이어떤 완제품을 만들기 위해 여러 부품이 필요하고, 그 부품들 또한 다른 부품들로 조립되는 구조완제품 번호는 항상 N번이고, 기본 부품은 다른 부품으로 구성되지 않는 것기본 부품마다 완제품을 1개 조립할 때 필요한 개수를 구하는 문제입력 처리 및 그래프 구성은 아래와 같이 구현한다.adj = [[] for _ in range(N)] # 인접 리스트 (X -> (Y, K): X는 Y를 K개 사용함)count = [0] * N # 진입 차수 저장for i in range(M): X, Y, K = map(int, input().split()) X -= 1 Y -= 1 adj[X].append(..
[골드 5] 백준 12865 - 평범한 배낭 (파이썬)
[골드 5] 백준 12865 - 평범한 배낭 (파이썬)
2025.04.28https://www.acmicpc.net/problem/12865풀이물건 개수 : N배낭의 최대 무게 : K각 물건은 W, V : 무게, 가치각 물건은 한 번만 쓸 수 있다.무게 ≤ K 조건을 만족하면서 가치의 합을 구하는게 목표기본적인 다이나믹 프로그래밍인데 나는 왜이렇게 어렵게 느껴지는걸까.먼저 dp[j]는 무게 j일때, 만들 수 있는 최대 가치를 나타낸다.그래서 dp = [0] * (K+1)로 무게 0부터 K까지 모든 무게에 대해, 처음엔 가치를 0으로 초기화 한다.dp = [0] * (K + 1)점화식을 다음과 같이 구성한다.for w, v in items : for j in range(K, w - 1, -1) : dp[j] = max(dp[j], dp[j - w] + v)현재..
[골드 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..