[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
2025.06.26https://www.acmicpc.net/problem/1113풀이높은 정보가 주어진 N * M 격자판이 존재한다.외곽은 절대 물을 담을 수 없고, 안쪽에 고인 물의 양을 계산해야한다.물은 본의의 높이보다 낮은 곳에 채워질 수 있다.각 칸에 고일 수 있는 물의 양을 계산해서 전체 합을 출력한다.결국 BFS로 해결해야 한다고 생각된다.모든 칸을 순회하면 (i, j) 칸에 물 1단계씩 채워보며 시도한다.채웠을 때 외곽까지 닿을 수 있다면 물은 새기 때문에 그만 둔다.외곽까지 닿지 않으면 물이 고일 수 있으므로 해당 칸 높이를 올리고 answer += 1을 진행한다.이 과정을 해당 칸에서 물이 넘칠 때 까지 반복한다.BFS 탐색으로 물이 새는지 확인하기 위해서 다음과 같이 정의 했다.while True : ..
[실버 2] 백준 13423 - Three Dots
[실버 2] 백준 13423 - Three Dots
2025.06.25https://www.acmicpc.net/problem/13423풀이다음 조건을 만족하는 수열 내 세 수 a, b, c의 개수를 찾는것이다.a b - a = c - b, 즉 등차수열 (공차 일정한 수열)정렬된 수열 A에서 두 수 A[i], A[j]를 선택하고, 공차를 구해서 등차수열의 세 번째 수 c = 2 * A[j] - A[i]가 A에 존재하는지를 판단한다.A는 정렬되어 있지만, 존재 여부를 빠르게 체크하기 위해 set으로도 관리한다.a 코드# 백준 13423 - Three Dots# 분류 : 자료구조T = int(input())for _ in range(T) : N = int(input()) A = list(map(int, input().split())) S = set(A) ..
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
2025.06.25https://www.acmicpc.net/problem/2878풀이총 M개의 캔디를 N명의 학생에게 나눠줘야 한다.각 학생은 자신이 원하는 캔디 수가 있고, 그보다 적게 받으면 “화남 지수”가 받은 개수^2로 증가한다.M개를 어떻게 배분해야 전체 화남 지수의 합이 최소가 되도록 하는지가 문제이다.사용한 풀이 전략은 다음과 같다.1. 이분 탐색을 이용해 평균 컷 구하기학생마다 min(A[i], mid) 만큼 주는 방식을 생각한다.이 때 mid를 조절하며, 총 줄 수 있는 캔디가 M 이상이 되는 최소 mid를 찾는다.mid 이상을 주면 안 되고, 모든 학생에게 최대한 공평하게 적게 주자는 전략.2. 이분 탐색 후 배분최적의 컷 수 p를 찾았으면,모든 학생에게 min(p - 1, A[i])만큼 먼저 배분한다..
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
2025.06.25https://www.acmicpc.net/problem/12871풀이두 문자열 S와 T가 무한히 반복된다고 할 때, 그 두 무한 문자열이 같은지 확인하는 문제이다.S = ‘abab’이고 T = ‘ababab’면 무한히 반복하면 둘 다 “abababababab…” 같은 문자열이 된다면 1을 출력하고 아니면 0을 출력한다.결국 핵심 아이디어는 문자열의 기본 단위를 구해서 비교하는 것이다.def find_basis(s): ...find_basis함수는 문자열 s의 반복되는 최소 단위를 찾아준다.예를 들어서 abab가 들어가면 ab를 반환하고, aaaa 가 들어가면 a를 반환한다.작동 방식은 다음과 같다.문자열 길이의 약수들을 기준으로 자른다.해당 길이로 자른 모든 조각이 동일한지 확인한다.동일하면 그것..
[실버 1] 백준 1141 - 접두사 (파이썬)
[실버 1] 백준 1141 - 접두사 (파이썬)
2025.06.24https://www.acmicpc.net/problem/1141풀이이 문제는 주어진 문자열들 중 다른 문자열의 접두사가 아닌 문자열의 개수를 세는 것이다.N = int(input())S = [input() for _ in range(N)]S = list(set(S)) # 중복 제거먼저 문자열 개수 N을 입력받고, 문자열 리스트 S를 구성한 뒤 set()을 이용해 중복 문자열을 제거한다.prefix = [False] * Nprefix[i]는 S[i]가 다른 문자열의 접두사인지 여부를 저장하는 배열이다.for i in range(len(S)) : for j in range(len(S)) : if i == j : continue if len(S[i]) >..
[골드 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상하좌우 방..