[실버 2] 백준 1058 - 친구 (파이썬)
[실버 2] 백준 1058 - 친구 (파이썬)
2025.05.24https://www.acmicpc.net/problem/1058풀이사람 수 N명각 사람이 다른 사람과 친구인지 여부가 Y 또는 N으로 주어짐직접 친구이거나 친구의 친구(2-친구)까지를 포함해 가장 많은 친구 수를 가지는 사람을 찾아 그 수를 출력접근 방법각 사람을 기준으로 BFS 수행거리가 1 또는 2인 사람 수를 세면 된다 (자기 자신은 제외)각 사람마다 세서 그 중 최대값을 구함조금 생각해야하는 부분dist[j] visit 배열과 dist 배열을 통해 BFS 방문 여부 및 거리 체크N = int(input())F = [input() for _ in range(N)]N은 사람수 F[i]는 i번째 사람의 친구 관계 문자열을 나타낸다.visit = [False] * Ndist = [-1] * Nqueue..
[실버 2] 백준 14620 - 꽃길 (파이썬)
[실버 2] 백준 14620 - 꽃길 (파이썬)
2025.05.23https://www.acmicpc.net/problem/14620풀이모든 좌표 중 3개를 조합으로 고른다.각 조합마다 꽃이 겹치지 않는지, 범위를 벗어나지 않는지 확인한다.문제가 없다면 그 조합의 총 비용을 계산하고 최소값을 갱신한다.from itertools import combinationsN = int(input())A = [list(map(int, input().split())) for _ in range(N)]N은 격자 크기.A는 각 칸의 비용을 저장한 2차원 배열.coordinates = [(i, j) for i in range(N) for j in range(N)]모든 좌표 (i, j)를 저장.dr = [0, 0, 1, -1]dc = [1, -1, 0, 0]answer = 1e9상하좌우 방..
[실버 1] 백준 1189 - 컴백홈 (파이썬)
[실버 1] 백준 1189 - 컴백홈 (파이썬)
2025.05.22https://www.acmicpc.net/problem/1189풀이현재 위치에서 이동 횟수를 세면서 목적지 (0, C-1)에 도달하는 모든 경로의 수를 세는 문제.단, 정확히 K칸 이동한 경로만 유효함.이동은 상하좌우 가능하며, T는 막힌 칸이므로 이동 불가.시작 위치는 (R-1, 0) 여기가 ‘집’.목표 위치는 (0, C-1) 여기가 ‘학교’.DFS로 이동 경로를 탐색하면서 K-1번 이동해야 하며, 마지막 위치가 (0, C-1)일 때만 카운트한다.방문 체크는 used 리스트로 관리한다.백트래킹으로 이전 경로로 되돌아가 다른 경로 탐색을 계속used를 리스트 대신 set으로 바꾸면 in 검사 속도가 O(n) → O(1)로 줄어 성능 향상 가능def dfs(r, c, k, used): if k ==..
[브론즈 2] 백준 1233 - 주사위 (파이썬)
[브론즈 2] 백준 1233 - 주사위 (파이썬)
2025.05.21https://www.acmicpc.net/problem/1233풀이합의 개수를 저장할 리스트 생성따라서 인덱스를 0부터 S1+S2+S3까지 만들고, 각 인덱스에 해당 합이 나오는 횟수를 저장한다.count = [0] * (S1 + S2 + S3 + 1)최대 합은 S1 + S2 + S3이고, 최소 합은 3이다.모든 주사위 눈 조합의 합을 카운트for i in range(1, S1 + 1): for j in range(1, S2 + 1): for k in range(1, S3 + 1): count[i + j + k] += 13중 for문을 돌며 각 눈의 합을 구하고, 그 합의 개수를 증가시킨다.가장 자주 나온 합을 찾기max_val = -1who = -1for i in..
[실버 4] 백준 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (파이썬)
[실버 4] 백준 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (파이썬)
2025.05.20https://www.acmicpc.net/problem/2422풀이총 N가지 아이스크림 맛이 있고, 이 중 3가지를 선택해서 조합.하지만 M쌍의 조합은 같이 선택하면 안 되는 조합 (즉, 금지된 조합)이 주어짐.금지된 조합이 한 쌍이라도 포함되면 해당 3개 조합은 불가능.가능한 3가지 아이스크림 조합의 개수를 구해야 함.bad = [[False] * N for _ in range(N)]bad[i][j]는 아이스크림 i와 j를 함께 먹을 수 없는지 여부를 저장하는 2차원 리스트.인덱스는 0부터 시작하도록 처리.for _ in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 bad[a][b] = True bad[b][a] = ..
[골드 4] 백준 1987 - 알파벳 (파이썬)
[골드 4] 백준 1987 - 알파벳 (파이썬)
2025.05.19https://www.acmicpc.net/problem/1987풀이R행 C열의 보드가 주어짐.보드의 각 칸에는 알파벳 대문자가 하나씩 있음.(0, 0)부터 시작하여 상하좌우로 이동.같은 알파벳을 두 번 지나갈 수 없음.최대로 이동할 수 있는 칸 수 출력.R, C = map(int, input().split())B = [input() for _ in range(R)]R * C 크기의 보드를 입력받는다.answer = 0check = [False] * 26check 배열은 A ~ Z 26개의 알파벳 사용 여부를 기록한다.def dfs(r, c, count) : global answer answer = max(answer, count)현재 위치까지 이동한 칸 수 count를 이용해 answer를 ..
[브론즈 1] 백준 1924 - 2007년 (파이썬)
[브론즈 1] 백준 1924 - 2007년 (파이썬)
2025.05.19https://www.acmicpc.net/problem/1924풀이2007년 1월 1일은 월요일 (MON).입력: x y (월, 일)출력: 2007년 x월 y일의 요일months = { 1 : 31, 2 : 28, ... 12 : 31}2007년은 평년이므로 2월은 28일.각 월의 일수를 딕셔너리로 저장.days = ["MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"]2007년 1월 1일이 월요일이므로, 인덱스 0 = “MON”으로 배열 정의.current = sum(months[i] for i in range(1, x))1월부터 (x - 1)월까지 총 일수를 더함.예: x = 3 (3월) → 1월 + 2월 = 31 + 28 = 59current..
[실버 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삽입 연산의 경우 우선순위 큐에 ..