Programming/백준
[골드 3] 백준 7579 - 앱 (파이썬)
[골드 3] 백준 7579 - 앱 (파이썬)
2025.07.18분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/7579풀이메모리 확보를 위해서 필요한 최소 비용을 구하는 문제다.앱 N개가 있고, 각각 메모리 m[i], 비용 c[i]를 가진다.총 확보해야 할 메모리는 M보다 크거나 같으며, 비용의 합이 최소가 되도록 하는 앱을 선택한다.DP 테이블은 다음과 같이 정의한다.D = [[0] * 10001 for _ in range(N)]D[i][j]는 i번 앱까지 고려했을 때, 비용 j 이하로 확보 가능한 최대 메모리를 나타내며, 비용 최대치가 10000이므로 열 크기를 10001로 설정한다.# D[0][i] : 첫 번째 앱만 사용할 때의 최대 메모리for i in range(c[0], 10001) : D[0][i] = ..
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
[골드 5] 백준 11578 - 팀원 모집 (파이썬)
2025.07.17분류 : 브루트포스 + 자료구조링크 : https://www.acmicpc.net/problem/11578풀이1번부터 N번까지의 문제를 모두 풀 수 있는 최소한의 팀원수를 구하는 문제이다.각 팀원은 자신이 풀 수 있는 문제 번호 리스트를 가지고 있다. 팀원은 M명이며, 문제를 모두 풀 수 있는 팀원의 최소 수를 구해야한다.A = [list(map(int, input().split()))[1:] for _ in range(M)]A = [set(a) for a in A]각 팀원이 자신이 풀 수 있는 문제 번호들을 입력받는다.list(map(int, input().split()))[1:] 에서 [1:] 부터 시작하는 이유는 첫 번째 숫자는 개수이므로 무시한다.set(a)로 변환해서 나중에 합집한 연산을 쉽게 ..
[골드 2] 백준 2450 - 모양 정돈 (파이썬)
[골드 2] 백준 2450 - 모양 정돈 (파이썬)
2025.07.16분류 : 브루트포스링크 : https://www.acmicpc.net/problem/2450풀이배열 A에는 1, 2, 3이 섞여있으면서, 각각 모양을 나타낸다.이 배열을 구간 3개로 나누어서, 각 구간에는 한 가지 모양이 있도록 정렬해야 한다.예를 들어서 [2, 2, 1, 1, 3, 3] 과 같은 형태이다.단, 숫자들을 바꾸는 횟수를 최소화 해아한다.입력 처리는 다음과 같다.N = int(input())A = list(map(int, input().split()))A = [x - 1 for x in A] # 0, 1, 2 로 바꿈입력 배열을 x - 1을 통해서 0, 1, 2로 정규화한다.그후 각 숫자의 개수를 센다.count = [0] * 3for x in A : count[x] += 1예를 들어..
[플래티넘 5] 백준 1981 - 배열에서 이동 (파이썬)
[플래티넘 5] 백준 1981 - 배열에서 이동 (파이썬)
2025.07.15분류 : 이분 탐색 + BFS링크 : https://www.acmicpc.net/problem/1981풀이N x N 크기의 정수 배열 A가 주어짐(0, 0) → (N-1, N-1)까지 상하좌우로 이동 가능단, 이동하는 칸의 숫자는 어떤 [min, max] 구간에 속해야 함이때 max - min 의 최소값을 구하는 것이 목적문제 풀이 아이디어는 다음과 같다.배열의 값은 최대 200이므로 min ~ max 범위가 0~200 사이임max - min mid 값을 이분 탐색으로 줄여나가며 최소값을 찾는 방식초기 설정은 다음과 같이 진행한다.low, high = 0, 200answer = -1mid = max_val - min_val 을 이분 탐색으로 줄여 나갈 범위이다.이분 탐색을 시작한다.while low 현재..
[골드 5] 백준 14567 - 선수과목 (Prerequisite) (파이썬)
[골드 5] 백준 14567 - 선수과목 (Prerequisite) (파이썬)
2025.07.14분류 : 다이나믹 프로그래밍링크 : https://www.acmicpc.net/problem/14567풀이총 N개의 과목이 주어지며, M개의 선수 조건이 주어진다.모든 과목에 대해 가장 빠른 이수 학기를 출력해야한다.N, M = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(M) : a, b = map(int, input().split()) a, b = a - 1, b - 1 adj[b].append(a)adj[b].append(a)는 b를 듣기 위해 a를 먼저 들어야 한다는 조건이므로, b에서 a로 역방향 간선을 저장한다.즉, b의 선수 과목들을 adj[b]에 저장한다.cache = [-1] * Ncache[i]..
[골드 3] 백준 1719 - 택배 (파이썬)
[골드 3] 백준 1719 - 택배 (파이썬)
2025.07.13https://www.acmicpc.net/problem/1719분류 : 다익스트라링크 : https://www.acmicpc.net/problem/1719풀이이 문제는 어느 경로로 가는 것이 최단 경로인지를 알아내는 문제이다.각 도시(정점) 간의 최단 경로를 찾아야하며, 단순히 최단 거리만 출력하는 것이 아니라, 어디로 먼저 가야 하는지를 출력해야한다.즉, i → j 로 갈 때 첫번째로 가야하는 도시를 출력해야하는 것ㅇ디ㅏ.from queue import PriorityQueueN, M = map(int, input().split()) # 도시 수 N, 도로 수 Madj = [[] for _ in range(N)] # 인접 리스트# 간선 정보 입력for _ in range(M): a, ..
[골드 5] 백준 14284 - 간선 이어가기 2 (파이썬)
[골드 5] 백준 14284 - 간선 이어가기 2 (파이썬)
2025.07.12https://www.acmicpc.net/problem/14284풀이이 문제는 조금 방향 없는 그래프, 즉 무방향 그래프가 주어지며, 정점수 N, 간선수 M이 주어진다.각 간선은 가중치를 가지며, 출발점 S에서 도착점 T까지의 최단 거리를 구하는 문제이다.이 문제에세의 핵심 알고리즘은, 단연코 다익스트라 알고리즘이라고 할 수 있다.먼저 가중치가 있는 그래프에서 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며, 이 문제에서는 특정 시작점에서 특정 도착점 까지의 거리만 구하면 된다.from queue import PriorityQueue우선순위 큐는 최소 거리 기준으로 정점을 꺼내기 위해서 위와 같이 사용한다.N, M = map(int, input().split())adj = [[]..
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
2025.07.11https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
2025.07.09https://www.acmicpc.net/problem/20159풀이플레이어가 번갈아 가면서 카드를 가져간다.짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.psum0 = [0] * N # 내 차례에서의 누적합psum1 = [0] * N # 상대 차례에서의 누적합psum0[0] = A[0]psum1[0] = 0for i in range(1, N): if i % 2 == 0: # 내 차례 psum0[i] = psum0[i - 1] + A[i] psum1[i] = psum1[i - 1] else: ..
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
2025.07.09https://www.acmicpc.net/problem/29767풀이길이가 N인 정수 수열 A가 주어지며, 누적합(A[0]부터 A[i]까지의 합)을 구해 전체 N개의 누적합 중 K개를 선택해서 합을 최대로 만들어야한다.N, K = map(int, input().split())A = list(map(int, input().split()))N은 원소 개수, K는 선택할 누적합 개수를 입력 받는다.psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 A[0] + A[1] + … + A[i]를 의미하며, 즉, 누적합 배열을 만든다.psum.sort(reverse=True)print(sum(psum[:K]..
[플래티넘 5] 백준 1050 - 물약 (파이썬)
[플래티넘 5] 백준 1050 - 물약 (파이썬)
2025.07.08https://www.acmicpc.net/problem/1050풀이여러개의 기초 물약은 가격이 주어지고, 일부 물약은 다른 물약들로 조합하여 만들 있다.조합은 "LOVE=A+2B" 같은 형태로 주어진다.목표: 물약 “LOVE”를 만드는데 필요한 최소 비용 계산하는 것이다.N, M = map(int, input().split())stuff = {}N은 가격이 주어진 물약 수를 나타내며, M은 조합식 수를 나타낸다.for _ in range(N) : name, cost = input().split() cost = int(cost) stuff[name] = cost가격이 주어진 물약은 딕셔너리 stuff에 저장한다.formulas = [input() for _ in range(M)]LOVE ..
[골드 5] 백준 23843 - 콘센트 (파이썬)
[골드 5] 백준 23843 - 콘센트 (파이썬)
2025.07.06https://www.acmicpc.net/problem/23843풀이총 N개의 기기를 충전해야 한다.충전기는 M개의 콘센트가 있다.각 기기를 충전하는 데 걸리는 시간이 배열 A로 주어진다.한 번에 M개까지 충전 가능하며, 각 콘센트는 병렬로 작동한다.모든 기기를 충전 완료하는 데 걸리는 최소 시간을 구하라.A.sort(reverse=True) # 시간이 긴 기기부터 우선 배정가장 긴 기기부터 먼저 처리해야 전체 시간이 줄어든다.그리디 전략: 긴 작업을 먼저 분산시켜야 부하가 치우치지 않음.pq = [0] * Mheapq.heapify(pq)pq: 각 콘센트의 누적 충전 시간을 관리처음엔 모두 0초 (아무것도 안 꽂힌 상태)heapq를 사용해서 가장 빨리 끝나는 콘센트를 찾기 용이하게 함 (최소 힙)f..
[실버 1] 백준 1629 - 곱셈 (파이썬)
[실버 1] 백준 1629 - 곱셈 (파이썬)
2025.07.05https://www.acmicpc.net/problem/1629풀이A^B % C를 직접 계산하면 시간 복잡도 O(B), 너무 크다.A^B = A^(B//2) * A^(B//2) (짝수일 경우)A^B = A^(B//2) * A^(B//2) * A (홀수일 경우)이를 이용해서 재귀적으로 절반씩 계산하면서 나머지를 구하는 방식을 사용한다. → 시간복잡도 O(log B)def power(a, b, c): if b == 0: return 1 # a^0 = 1 if b == 1: return a % c # a^1 % c = a % c x = power(a, b // 2, c) # A^(B//2) 값을 재귀 호출로 구함 if b % 2 == 0: ..
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
2025.07.04https://www.acmicpc.net/problem/12784풀이인하니카 공화국의 수도는 1번 정점(문제에서는 0번으로 인덱싱)이다.나머지 모든 정점은 루팡에 의해 공격받을 수 있고, 이들을 방어하기 위해 일부 간선에 폭탄을 설치해야 한다.폭탄은 정점에 도달하는 가장 짧은 경로에 설치되고, 그 간선의 최소 비용이 사용된다.최소한의 비용으로 모든 리프 노드를 보호하려고 할 때, 그 비용을 구하는 문제다.입력 및 그래프를 구성한다.N, M = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(M) : a, b, c = map(int, input().split()) a -= 1 b -= 1 adj[a].appen..
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
2025.07.04https://www.acmicpc.net/problem/2749풀이이미지 출처 : https://velog.io/@cha-suyeon/python-피보나치-수열-만들기-점프투파이썬-종합문제-5번피보나치 수열은 위 그림 처럼 제일 초기 1에서 1을 더한 값이 2, 2와 1을 더한 값이 3, …, n - 1번째 값과 n을 더한값.. 이런식으로 계속해서 늘어나는 수열이다.결국 식을 작성하면 다음과 같다.Fn = Fn-1 + Fn-2 (n >= 2)이런식으로 n 이 17일때의 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.여기서 한가지 고려해..