Programming
[실버 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()..
[실버 1] 백준 27970 - OX (파이썬)
[실버 1] 백준 27970 - OX (파이썬)
2025.05.08https://www.acmicpc.net/problem/27970풀이문자열 S가 주어집니다. S는 'O'와 'X'로만 구성되어 있다.우리는 문자열 내 'O'들이 가지는 “가중치 합”을 구해야 한다.'O'가 있는 위치의 2의 거듭제곱 값을 더한다.결과는 1,000,000,007 (10^9 + 7) 로 나눈 나머지를 출력한다.✅ 풀이 로직power는 현재 인덱스의 2의 거듭제곱 값을 의미한다.예를 들어, 인덱스 0: 2^0, 인덱스 1: 2^1, …, 인덱스 i: 2^i문자열을 왼쪽부터 오른쪽으로 순회하면서만약 해당 문자가 'O'라면, answer에 현재의 power 값을 더한다.그 후 power *= 2 로 2의 거듭제곱을 갱신한다.중간중간 mod 연산으로 값을 줄여준다.코드# 백준 27970 - OX#..
[실버 1] 백준 1697 - 숨바꼭질 (파이썬)
[실버 1] 백준 1697 - 숨바꼭질 (파이썬)
2025.05.08https://www.acmicpc.net/problem/1697풀이수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이는 1초에 다음 세 가지 행동 중 하나를 선택할 수 있다:X - 1로 이동 (1초 소요)X + 1로 이동 (1초 소요)2 * X로 순간이동 (1초 소요)목표는 수빈이가 동생에게 도달하는 데 걸리는 최소 시간을 구하는 것이다.이 문제는 각 위치를 정점으로 보고, 가능한 이동을 간선으로 간주하여 최단 거리를 구하는 그래프 탐색 문제로 볼 수 있다.특정 위치에서 세 방향으로 이동 가능하므로, 그래프 탐색을 통해 가장 먼저 도착하는 경우가 최소 시간이 된다.BFS는 그래프에서 최단 거리를 구할 때 매우 적절한 알고리즘이다. BFS는 먼저 도달한 경로가 최단 경로임을 보장하므로, 동생..
[실버 2] 백준 15666 - N과 M (12) (파이썬)
[실버 2] 백준 15666 - N과 M (12) (파이썬)
2025.05.07https://www.acmicpc.net/problem/15666풀이자연수 N개 중에서 M개를 중복 선택 가능하게 고르되,고른 수열은 비내림차순이어야 하고,중복되는 수열은 한 번만 출력해야 합니다.N, M = map(int, input().split())nums = list(map(int, input().split()))nums = sorted(list(set(nums)))nums에서 중복 제거 후 정렬한다. 왜냐하면 중복 수열 출력을 방지하기 위해서이다.def back(start, depth): if depth == M: print(' '.join(map(str, result))) return for i in range(start, len(nums)): ..
[실버 2] 백준 16953 - A → B (파이썬)
[실버 2] 백준 16953 - A → B (파이썬)
2025.05.07https://www.acmicpc.net/problem/16953풀이정수 A를 B로 만들기 위해 사용할 수 있는 연산은A → A * 2A → A * 10 + 1최소한의 연산 횟수로 A를 B로 만들고 싶다. 만들 수 없다면 -1을 출력.이 코드는 B에서 A로 거꾸로 줄여나가는 방식왜냐하면 A에서 B로 모든 경우를 시도하면 탐색 공간이 매우 커질 수 있기 때문주요 아이디어B를 줄여가면서 A가 될 수 있는지 확인한다.가능한 줄이는 방법B % 10 == 1 → 끝자리가 1이면 B // 10B % 2 == 0 → 짝수면 B // 2그 외에는 더 이상 줄일 수 없으므로 중단코드# 백준 16953 - A -> B# 분류 : 그래프A, B = map(int, input().split())count = 1while B..
[골드 1] 백준 2933 - 미네랄 (파이썬)
[골드 1] 백준 2933 - 미네랄 (파이썬)
2025.05.07https://www.acmicpc.net/problem/2933풀이막대기를 던져 미네랄(‘x’)을 부수면, 공중에 뜬 미네랄 클러스터는 중력 방향으로 낙하해야 한다.미네랄은 바닥 또는 다른 미네랄과 맞닿아 있어야 멈춘다.막대기는 번갈아 가며 왼쪽/오른쪽에서 날아오며, 부딪힌 첫 번째 미네랄을 부순다.1. 막대기 던지기입력받은 높이에 따라 해당 줄에서 가장 먼저 만나는 미네랄(‘x’)을 제거한다.던지는 방향은 짝수 턴에는 왼쪽에서 오른쪽, 홀수 턴에는 오른쪽에서 왼쪽이다.2. 클러스터 탐색 (BFS)미네랄 덩어리(클러스터)는 상하좌우 인접한 미네랄끼리 연결되어 있다.visited 배열을 이용해 미네랄 덩어리를 하나씩 탐색한다.3. 공중 클러스터 분리 및 낙하 처리바닥에 닿지 않은 클러스터는 중력의 영향을..