[골드 4] 백준 16120 - PPAP (파이썬)
[골드 4] 백준 16120 - PPAP (파이썬)
2025.06.23https://www.acmicpc.net/problem/16120풀이문자열이 PPAP 규칙에 따라서 만들어졌는지 판별하는 문제이다.기본적인 규칙은 PPAP는 P로 줄일 수 있다.PPPAP는 PPAP + P → PP가 되지 않으므로 올바른 형태가 아니다.줄이고 줄이다가 마지막에 P 하나만 남으면 PPAP 문자열이라고 한다.S = input()stack = []입력 문자열 S를 한글자씩 처리할 것이며, 처리 중간 결과를 저장하기 위해서 스택을 사용한다.for i in range(len(S)) : stack.append(S[i])입력 문자열의 각 문자를 stack에 순차적으로 쌓는다.while len(stack) >= 4 and "".join(stack[-4:]) == "PPAP" : for _ ..
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
2025.06.22https://www.acmicpc.net/problem/1670풀이사람 수는 짝수 N이고, 각 사람은 한 명과만 악수할 수 있으며, 악수 선이 교차하지 않아야 한다.이는 DP로 해결할 수 있으며, 다음 점화식을 따른다.이 문제는 카탈란 수(Catalan Number) 문제 유형의 대표적인 예다.핵심은 다음과 같다N명의 정상 중 한 명을 기준으로 짝을 지었을 때, 남은 좌우 인원들도 각각 교차 없이 짝을 지어야 한다.이를 이용하면 DP 점화식을 다음과 같이 세울 수 있다.D[0] = 1 # 아무도 없을 때는 1가지 (아무것도 안 하는 경우)D[2] = 1 # 두 명이 있을 때는 1가지D[n] = D[0]*D[n-2] + D[2]*D[n-4] + D[4]*D[n-6] + ... + D[n-2]*D[0]..
[실버 1] 백준 12849 - 본대 산책 (파이썬)
[실버 1] 백준 12849 - 본대 산책 (파이썬)
2025.06.21https://www.acmicpc.net/problem/12849풀이총 8개의 장소(0~7번 정점)로 구성된 캠퍼스가 있고, 하루에 1분씩 이동할 수 있음.이동 가능한 경로는 문제에서 고정되어 있음 (총 12개 간선)0번에서 시작해 정확히 D분 뒤 다시 0번에 도착할 수 있는 모든 경로의 수를 구하는 문제.단, 결과는 10^9 + 7로 나눈 나머지를 출력.adj = [[] for _ in range(8)]edge = [ ... ] # 문제에서 주어진 12개 간선for a, b in edge: adj[a].append(b) adj[b].append(a)먼저 인접 리스트를 정의하고, adj[i]는 i번 정점에서 갈 수 있는 이웃 정점을 리스트로 담고 있다.양방향 그래프이므로 adj[a].app..
[골드 5] 백준 2591 - 숫자카드 (파이썬)
[골드 5] 백준 2591 - 숫자카드 (파이썬)
2025.06.20https://www.acmicpc.net/problem/2591풀이34까지의 숫자 카드가 있을 때, 주어진 숫자 문자열 S를 한 자리 또는 두 자리 숫자로 쪼개어 카드 조합을 만드는 방법의 수를 구하는 문제이다. 단, 앞자리가 0이면 안 되고, 두 자리 수는 134 사이의 유효한 카드 번호여야 한다.D[i]: 문자열 S의 앞에서 i자리까지 만들 수 있는 카드 조합 수점화식한 자리 수 (S[i-1])가 '0'이 아니면 D[i] += D[i-1]두 자리 수 (S[i-2:i])가 '10' ~ '34' 범위에 속하면 D[i] += D[i-2]S = input()D = [0] * (len(S) + 1) # D[0] ~ D[len(S)]D[0] = 1 # 빈 문자열은 1가지 방법 (기저 조건)for i in ..
[실버 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 ..
[25년 5월] 아이폰 1110 오류 / 무한 사과 / 저장공간 꽉참 데이터 복구 해결건
[25년 5월] 아이폰 1110 오류 / 무한 사과 / 저장공간 꽉참 데이터 복구 해결건
2025.05.24안녕하세요, 이번에는 1년전 저에게 맡기셨던 의뢰자분이 다시한번 연락을 주셨습니다.최근 새로운 기술 도입으로 복구률이 매우 증가하였고,이전에 의뢰하신분도 생각이 나서 바로 의뢰에 착수하였습니다.이 글은, 실제 데이터 복구 요청을 받아 작업을 진행하였습니다.해당 의뢰를 원하신다면 하단의 연락쳐로 연락주세요! 한달에는 많게는 4~5건, 여러건에 대해서 문의가 들어오고 있습니다.애플 공식 서비스센터에서는 1110 에러에 대해서는 초기화 밖에 답이 없다고 하지만,저는 의뢰자 분들의 소중한 데이터를 위해서 항상 연구 하고 있습니다.택배로 의뢰자 분의 기기를 받아보았으며, 2025년 5월 22일에 보내주셔서 5월 23일에 받아보게 되었습니다.택배가 오는 과정에서 손상이 없도록 뽁뽁이로 잘 감싸주셨습니다.외관상으로 ..
[실버 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..