Programming
[브론즈 2] 백준 1173 - 운동 (파이썬)
[브론즈 2] 백준 1173 - 운동 (파이썬)
2025.05.01https://www.acmicpc.net/problem/1173풀이현재 맥박 : m, 최대 맥박 : M운동 할 때마다 맥박 T만큼 증가쉬면 맥박 R만큼 감소운동을 N번 해야한다.현재 맥박이 M을 초과하면 운동을 못한다.운동을 못할 때는 쉬어야한다.운동 N번을 완료하는 데 걸리는 시간을 출력하고,만약 아예 운동을 못 시작하는 상황이면 -1을 출력한다.if m + T > M : print(-1)현재 맥박 m에 운동 후 증가량 T를 더했을 때, M을 넘으면,아예 한 번도 운동할 수 없기에 -1을 출력하고 종료한다.else : timer = 0 X = m while N > 0 : timer += 1타이머를 0으로 초기화 하고, 현재 맥박 X를 m으로 초기화한다.운동을 N번 해..
[골드 5] 백준 13398 - 연속합 2 (파이썬)
[골드 5] 백준 13398 - 연속합 2 (파이썬)
2025.04.30https://www.acmicpc.net/problem/13398풀이주어진 수열에서 연속된 몇 개의 수를 선택해 가장 큰 합을 만든다.단, 원하는 경우 수열에서 수 하나를 ‘제거’할 수 있다.제거를 한 경우든 안 한 경우든 가장 큰 연속합을 구하는 문제D, E 배열을 초기화 한다.D = [-1e9] * NE = [-1e9] * ND[i] : A[0] ~ A[i] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합E[i] : A[i] ~ A[N-1] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합D배열을 채운다. (왼쪽 → 오른쪽)D[0] = A[0]for i in range(1, N): D[i] = max(A[i], A[i] + D[i - 1])D[0]은 시작점이니까 그냥..
[실버 4] 백준 10211 - Maximun Subarray (파이썬)
[실버 4] 백준 10211 - Maximun Subarray (파이썬)
2025.04.30https://www.acmicpc.net/problem/10211풀이여러 테스트 케이스가 주어진다.각 케스트 케이스마다, 연속된 구간의 합 중 최대값을 구하는 문제누적합 배열 psum을 생성한다.psum = [0] * Npsum[0] = X[0]psum[i] = X[0] + X[1] + … + X[i]for i in range(1, N) : psum[i] = psum[i - 1] + X[i]구간 합을 빠르게 계산하려고 누적합 배열을 사용한다.for i in range(N) : for j in range(i, N) : range_sum = psum[j] if i > 0 : range_sum -= psum[i - 1] if max_sum 모든 구간을 탐색하며,..
[실버 1] 백준 16198 - 에너지 모으기 (파이썬)
[실버 1] 백준 16198 - 에너지 모으기 (파이썬)
2025.04.30https://www.acmicpc.net/problem/16198풀이구슬이 일렬로 놓여 있고, 양끝 구슬을 제외하고 하나를 고를 수 있다.고른 구슬을 제거하면서 얻는 에너지는 (왼쪽 구슬 번호) * (오른쪽 구슬 번호)구슬이 2개 남을때까지 반복얻을 수 있는 에너지의 최대값을 구하라if len(a) == 2: return w구슬이 2개만 남으면 더이상 고를 수 없으니, 지금까지 모은 에너지를 반환한다.재귀 호출은 다음과 같이 진행한다.for i in range(1, len(a) - 1):맨 앞과 맨 뒤 구슬을 제외한 가운데 구슬만 고를 수 있다.na = a[:i] + a[i+1:]i번째 구슬을 제거해서 새로운 리스트를 만든다.tmp = dfs(na, w + a[i-1] * a[i+1])i번째 구슬..
[골드 4] 백준 12886 - 돌 그룹 (파이썬)
[골드 4] 백준 12886 - 돌 그룹 (파이썬)
2025.04.29https://www.acmicpc.net/problem/12886풀이돌이 A, B, C 그룹에 있다.한번의 연산이 진행된다.돌 수가 다른 두 그룹을 골라서, 돌 수가 적은 쪽을 2배로 만들고많은 쪽에서는 그 차이만큼 뺀다.세 그룹의 돌 수를 모두 같게 만들수 있는가?if S % 3 != 0: print(0)총합이 3의 배수가 아니라면 절대 세 그룹을 같은 수로 만들 수 없다.visit = [[False] * S for _ in range(S)]visit[a][b]가 True이면 (a, b, c = S - a - b)상태를 이미 방문 했다는 의미,a와 b만 알면 c는 S - a - b로 자동 결정되기 때문에 2차원 배열만 사용한다.queue = deque()queue.append((A, B))vis..
[실버 1] 백준 3184 - 양 (파이썬)
[실버 1] 백준 3184 - 양 (파이썬)
2025.04.29https://www.acmicpc.net/problem/3184풀이울타리로 막혀 있는 공간 안에 양과 늑대가 있다.한 영역에서 양의 수가 늑대보다 많으면 양이 살아남고, 늑대가 더 많거나 같으면 늑대가 살아남음최종적으로 살아남은 양과 늑대의 수를 구하는 문제R, C = map(int, input().split())B = [input() for _ in range(R)]R, C는 행, 열 크기를 나타내며, B는 농장의 상태를 저장한 2차원 리스트이다.대표적인 BFS 문제이다. 해당 문제는 visit 배열을 사용해서 풀이가 가능하다.visit = [[False] * C for _ in range(R)]queue = deque()dr = [1, -1, 0, 0]dc = [0, 0, 1, -1]final_o,..
[실버 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..