Programming
[실버 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번째 피보나치 수를 구하는 문제이다.여기서 한가지 고려해..
[플래티넘 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..