Programming
[실버 2] 백준 1500 - 최대 곱 (파이썬)
[실버 2] 백준 1500 - 최대 곱 (파이썬)
2025.05.18https://www.acmicpc.net/problem/1500풀이곱의 최댓값을 구하려면, 수들을 가능한 한 고르게 나누는 것이 유리하다.예: S = 10, K = 3일 때 → 3, 3, 4 (곱: 36)2, 2, 6은 합은 같지만 곱이 작다 (24)정수 S를 K로 나눈 몫(q)과 나머지(r) 를 활용하면 된다.q, r = divmod(S, K)S = q * K + rnums = [q + 1] * r + [q] * (K - r)r개의 항에는 (q+1), 나머지는 qr개의 수는 (q + 1)나머지 (K - r)개의 수는 q이 수들을 곱하면 최댓값result = 1for num in nums: result *= numprint(result)코드# 백준 1500 - 최대 곱# 분류 : 수학S, K = ..
[실버 3] 백준 1012 - 유기농 배추 (파이썬)
[실버 3] 백준 1012 - 유기농 배추 (파이썬)
2025.05.17https://www.acmicpc.net/problem/1012풀이M x N 밭에 K개의 배추가 심어져 있다.상하좌우로 인접한 배추는 하나의 그룹으로 간주한다.이 그룹 수 = 필요한 지렁이 수목표: 테스트 케이스마다 그룹 수 출력field = [[0] * M for _ in range(N)]visited = [[False] * M for _ in range(N)]field[y][x] 는 배추가 있는 위치를 표시하고, visited 이미 방문한 곳은 다시 탐색하지 않도록 체크한다.dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]상, 하, 좌, 우로 이동 할 수 있는 트릭을 작성한다.def bfs(x, y): queue = deque() queue.append((x, y)) ..
[브론즈 1] 백준 10448 - 유레카 이론 (파이썬)
[브론즈 1] 백준 10448 - 유레카 이론 (파이썬)
2025.05.16https://www.acmicpc.net/problem/10448풀이D = [0] * 50D[0] = 1D[1] = 3for i in range(1, 50): D[i] = D[i - 1] + i + 1삼각수를 생성한다.for combination in combinations(D, 3): if sum(combination) == N: found = True breakcombinations(D, 3)는 중복 없이 3개를 뽑아 더한 것이 N과 같은지 확인중복이 안되기 때문에 예를 들어 (3, 3, 3) 같은 케이스는 이 조건에 안 걸림for combination in combinations(D, 2): if combination[0] * 2 + combination[..
[실버 3] 백준 23351 - 물 주기 (파이썬)
[실버 3] 백준 23351 - 물 주기 (파이썬)
2025.05.15https://www.acmicpc.net/problem/23351풀이총 N개의 화분이 있다.하루에 A개만큼의 화분에 물을 줄 수 있다.물을 주면, 해당 화분의 수분량이 B만큼 회복된다.수분량이 0이 되면 화분이 죽는다.처음 모든 화분은 수분량 K로 시작한다.모든 화분을 죽이지 않고 버틸 수 있는 최대 일수를 구하라.코드# 백준 23351 - 물 주기# 분류 : 우선순위 큐from queue import PriorityQueueN, K, A, B = map(int, input().split())N //= Apq = PriorityQueue()for _ in range(N) : pq.put(K)count = 0zero = 0while True : x = pq.get() if x == zer..
[실버 5] 백준 27111 - 출입 기록 (파이썬)
[실버 5] 백준 27111 - 출입 기록 (파이썬)
2025.05.14https://www.acmicpc.net/problem/27111풀이어떤 사람들이 출입기록을 남긴다.입력: 사람 번호 a, 출입 여부 b (1 = 입장, 0 = 퇴장)정상적인 경우:입장 기록 없이 퇴장 ❌이미 입장한 상태에서 또 입장 ❌비정상적인 경우의 수를 출력하라.bude = set()count = 0bude는 현재 안에 있는 사람들의 번호를 저장하는 setcount는 비정상적인 출입 횟수를 저장하는 변수이다.for _ in range(N): a, b = map(int, input().split())a는 사람번호, b는 출입 여부if b == 1: if a in bude: count += 1 # 이미 안에 있는데 또 입장 → 비정상 else: bude.ad..
[실버 1] 백준 15903 - 카드 합체 놀이 (파이썬)
[실버 1] 백준 15903 - 카드 합체 놀이 (파이썬)
2025.05.13https://www.acmicpc.net/problem/15903풀이숫자 카드 N장이 주어짐M번에 걸쳐 가장 작은 두 장을 골라 합친 뒤, 그 값을 두 장 모두에 덮어 씌움최종 카드들의 합을 구하라from queue import PriorityQueueN, M = map(int, input().split())A = list(map(int, input().split()))N: 카드 개수M: 합체 횟수A: 카드에 적힌 숫자들pq = PriorityQueue()for x in A : pq.put(x)최소 힙을 활용하기 위해서 PrioirtyQueue에 모든 값을 넣는다. (기본적으로 오름차순 우선순위로 동작한다.)for _ in range(M) : x = pq.get() y = pq.get(..
[골드 4] 백준 4803 - 트리 (파이썬)
[골드 4] 백준 4803 - 트리 (파이썬)
2025.05.12https://www.acmicpc.net/problem/4803풀이정점 N개와 간선 M개로 구성된 무방향 그래프가 주어진다.그래프 내에 트리가 몇 개 존재하는지 출력해야 한다.트리의 정의: 사이클이 없는 연결 그래프간선 수 = 정점 수 - 1 이면 트리다.adj = [[] for _ in range(N)]인접 리스트를 생성한다. 단 정점번호는 0부터 N - 1이다.for _ in range(M) : a, b = map(int, input().split()) a -= 1 b -= 1 adj[a].append(b) adj[b].append(a)무방향 간선이므로 양쪽에 모두 추가한다.입력은 1-based이지만 내부는 0-based로 처리한다.visit = [False] * Nque..
[골드 4] 백준 7662 - 이중 우선순위 큐 (파이썬)
[골드 4] 백준 7662 - 이중 우선순위 큐 (파이썬)
2025.05.11https://www.acmicpc.net/problem/7662풀이I x : x를 삽입D 1 : 최댓값 삭제D -1 : 최솟값 삭제최종적으로 큐에 남아 있는 값 중 최댓값과 최솟값 출력비어 있으면 "EMPTY" 출력min_pq = PriorityQueue() # 최소 힙max_pq = PriorityQueue() # 최대 힙 (음수로 삽입)count = {} # 실제 유효한 값 카운트이중 우선순위 큐를 min_pq, max_pq로 나눠서 관리한다동기화가 되지 않기 때문에, 실제 삭제 여부는 count 딕셔너리로 관리한다.if t == 'I' : min_pq.put(v) max_pq.put(-v) count[v] = count.get(v, 0) + 1삽입 연산의 경우 우선순위 큐에 ..
[골드 5] 백준 2166 - 다각형의 면적 (파이썬)
[골드 5] 백준 2166 - 다각형의 면적 (파이썬)
2025.05.10https://www.acmicpc.net/problem/2166 풀이평면 위의 N개의 꼭짓점이 주어지는 다각형의 면적을 구하라정점 N개면적을 소수점 첫째 자리까지 반올림다각형의 꼭짓점 (x1, y1), (x2, y2), … , (xn, yn) 순서로 주어졌을때 면적은 신발끈 공식으로 해결 할 수 있다.area = 0for i in range(N): x1, y1 = points[i] x2, y2 = points[(i + 1) % N] area += (x1 * y2) - (x2 * y1)x1 * y2 - x2 * y1 항을 순서대로 모두 더해서 신발끈 공식의 분자 부분을 구한다.(i + 1) % N 으로 마지막 점과 첫 점을 연결한다.print(round(abs(area) / 2, 1))절..
[골드 3] 백준 1005 - ACM Craft (파이썬)
[골드 3] 백준 1005 - ACM Craft (파이썬)
2025.05.10https://www.acmicpc.net/problem/1005풀이각 건물은 건설 완료에 특정 시간이 걸림.어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수도 있음.목표 건물 W를 짓기까지의 최소 시간을 구해야 함.진입 차수 계산 및 그래프 구성count[y] += 1은 y번 건물을 짓기 전 지어야 할 건물 개수를 누적함.adj[x].append(y)는 x 건물 후에 y 건물을 지을 수 있다는 의미.초기 시작 노드 설정 (진입 차수가 0인 노드)진입 차수가 0인 건물은 바로 지을 수 있으므로 queue에 삽입.finish[i] = D[i]로 초기화.위상 정렬 + DPu를 짓고 나면 그 다음 건물 v는 finish[v] = max(finish[v], finish[u] + D[v])로 업데이트함.즉,..
[골드 3] 백준 16947 - 서울 지하철 2호선 (파이썬)
[골드 3] 백준 16947 - 서울 지하철 2호선 (파이썬)
2025.05.10https://www.acmicpc.net/problem/16947풀이서울 지하철 2호선은 하나의 순환선과 그 순환선에 연결된 가지 노선들로 구성되어 있음.각 역은 노드, 연결된 선로는 간선으로 보았을 때입력으로 역들과 연결 정보를 주고,각 역이 순환선으로부터 얼마나 떨어져 있는지(거리)를 출력하는 문제이다.그래프 만들기: 인접 리스트로 저장순환선 찾기: 리프 노드(leaf, degree==1)들을 반복적으로 제거 → 순환에 속한 노드만 남김BFS로 거리 계산: 순환선 노드들을 시작점으로 BFS 수행 → 거리 계산N = int(input())adj = [[] for _ in range(N)]for _ in range(N) : u, v = map(int, input().split()) u -= ..
[골드 1] 백준 2263 - 트리의 순회 (파이썬)
[골드 1] 백준 2263 - 트리의 순회 (파이썬)
2025.05.09https://www.acmicpc.net/problem/2263풀이트리 재구성 및 전위 순회 출력을 하는 문제이다.문제는 중위 순회와 후위 순회 결과를 통해 전위 순회 결과를 구하는 것이다.입력첫 줄 : 노드 개수 N둘째 줄 : 중위 순회 결과 INORDER셋째 줄 : 후위 순회 결과 POSTORDER출력전위 순회 결과순회 정의전위(preorder)Root → Left → Right중위(inorder)Left → Root → Right후위(postorder)Left → Right → Root후위 순회의 마지막 원소는 항상 현재 서브트리의 루트 노드이다.루트 값을 중위 순회에서 찾아 좌/우 서브트리의 범위를 나눈다.나뉜 범위를 이용해 재귀적으로 좌/우 서브트리를 계속 분할한다.루트를 먼저 출력하므로 전위..
[실버 2] 백준 25186 - INFP 두람 (파이썬)
[실버 2] 백준 25186 - INFP 두람 (파이썬)
2025.05.09https://www.acmicpc.net/problem/25186풀이총 N명의 사람이 있고, 각 사람이 입은 옷의 종류는 리스트 A로 주어집니다.사람들은 원형으로 서 있으며, 인접한 두 사람의 옷 종류가 같지 않아야 합니다.이러한 배치가 가능하면 “Happy”, 불가능하면 “Unhappy”를 출력합니다.핵심 조건배치가 가능하기 위한 조건은 다음과 같다.어떤 옷의 종류도 전체 옷의 개수의 절반을 초과해서는 안된다.즉, 어떤 옷의 개수가 전체 옷의 개수의 절반보다 크면, 해당 옷을 입은 사람들이 인접하지 않도록 배치하는 것이 불가능하다.예외적으로, N = 1이고 해당 옷의 개수가 1개인 경우는 “Happy”로 처리해야 한다.total은 전체 옷의 개수를 계산한다.max(A)는 가장 많은 개수를 가진 옷의 ..
[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)
[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)
2025.05.08https://www.acmicpc.net/problem/5639풀이전위 순회를 후위 순회로 변환하는 구현을 진행해야한다.즉, 전위 순회 결과가 주어졌을 때, 해당 트리의 후위 순위 결과를 출력해야한다.입력은 전위 순회 결과이며, 이진 검색 트리 조건이 적용된다.왼쪽 자식 def postorder(start, end): if start >= end: return root = preorder[start] # 현재 서브트리의 루트 # 오른쪽 서브트리의 시작 인덱스를 찾기 right = start + 1 while right preorder[start]는 항상 서브트리의 루트 노드이며, 그 다음부터 preorder[right] 조건이 깨지는 최초의 right는 ..
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
2025.05.08https://www.acmicpc.net/problem/1916풀이방향성이 있는 그래프에서 start 도시에서 end 도시로 가는 최소 비용을 구하는 문제이다. 즉 다익스트라를 이용해야한다.가중치가 있는 간선들이 주어지며, 음의 간선이 없다.인접리스트와 최단거리 테이블을 초기화 하기 위해서 다음과 같이 초기화 한다.adj = [[] for _ in range(N + 1)] # 인접 리스트distance = [INF] * (N + 1) # 최단거리 테이블 초기화도시 번호는 1부터 시작하므로 N + 1 크기로 배열을 잡고, INF는 초기 거리를 무한대로 세팅한다.간선 정보 저장을 위해서 다음과 같이 정의 한다.for _ in range(M) : u, v, cost = map(int, input()..