Programming
[실버 1] 백준 1446 - 지름길 (파이썬)
[실버 1] 백준 1446 - 지름길 (파이썬)
2025.05.27https://www.acmicpc.net/problem/1446풀이일반 도로는 i → i+1로 이동하면서 1km가 걸린다.지름길은 입력으로 주어지며 (a, b, c)의 의미는 a → b로 가는 지름길이 있고, 길이는 c이다.목표는 0 → D까지 가는 데 걸리는 최단 거리를 구하는 것.N, D = map(int, input().split())adj = [[] for _ in range(D + 1)]D까지의 거리이므로 정점은 0부터 D까지 총 D + 1개이다.adj[i]는 정점 i에서 갈 수 있는 목적지, 비용 리스트이다.for _ in range(N): a, b, c = map(int, input().split()) if b 지름길 정보는 b가 D보다 큰 경우 무의미하므로 무시하며, 지름길은 ..
[골드 3] 백준 1937 - 욕심쟁이 판다 (파이썬)
[골드 3] 백준 1937 - 욕심쟁이 판다 (파이썬)
2025.05.26https://www.acmicpc.net/problem/1937풀이N×N 크기의 숲이 있다.각 칸에는 대나무가 자라고 있고, 숫자는 대나무의 양이다.판다는 현재 위치보다 더 많은 양의 대나무가 있는 칸으로만 이동할 수 있다.상하좌우로 이동 가능하다.판다는 최대한 많은 날을 살아야 하므로, 이동할 수 있는 경로 중 가장 긴 경로의 길이를 구해야 한다.풀이 아이디어특정 위치 (r, c)에서 시작해 이동할 수 있는 최대 경로를 구한다.이미 계산한 값은 cache[r][c]에 저장해 중복 호출을 방지한다 (메모이제이션).결국 각 칸에서 출발했을 때의 최대 이동일수 중 최댓값이 정답이다.N = int(input())F = [list(map(int, input().split())) for _ in range(N)..
[골드 3] 백준 1613 - 역사 (파이썬)
[골드 3] 백준 1613 - 역사 (파이썬)
2025.05.25https://www.acmicpc.net/problem/1613풀이N: 사건 개수 (노드 수), K: 사건 간 전후관계의 개수 (방향 그래프 간선)각 입력 (a, b)는 a 사건이 b 사건보다 먼저 일어났음을 의미 → 단방향 간선S개의 질문: a와 b 중 누가 먼저인지 판단먼저 입력 처리 및 인접리스트를 구현한다.adj = [[] for _ in range(N)]for _ in range(K): a, b = map(int, input().split()) a -= 1 b -= 1 adj[a].append(b)방향 그래프 형태로 인접 리스트를 구성한다.모든 정점에서 BFS를 돌려 도달 가능한 노드를 기록한다.visit = [[False] * N for _ in range(N)]for ..
[실버 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..