포렌식 & 개발 이야기 - Forensics & Development
[골드 1] 백준 11401 - 이항 계수 3 (파이썬)
[골드 1] 백준 11401 - 이항 계수 3 (파이썬)
2025.05.02https://www.acmicpc.net/problem/11401풀이이게 어떻게 정답률이 40%?이 문제는 조금 어렵다. 모듈로 연산(1000000007)이 포함된 큰 수의 이항계수를 다루기 때문에, 단순한 팩토리얼 연산으로는 시간 초과가 일어난다.입력으로는 정수 N, K가 들어오소, 수가 크므로 모듈로 연산이 필요하고, 나눗셈은 페르마의 소정리를 이용해야한다.먼저 이항 계수 공식은 다음과 같다.하지만 단순한 팩토리얼 계싼은 값이 너무 커져 오버플로우가 발생하거나 시간초과가 발생한다.따라서, 문제에서 요구한 1000000007로 모듈로 연산을 적용해야 한다.왜 일반적인 나눗셈이 안되는 건가요?→ 일반적으로 모듈러 연산에서는 나눗셈이 직접 불가능하다. → 대신 모둘러 역원을 이용해야한다.페르마의 소정리는..
[브론즈 4] 백준 14470 - 전자레인지 (파이썬)
[브론즈 4] 백준 14470 - 전자레인지 (파이썬)
2025.05.02https://www.acmicpc.net/problem/14470풀이음식의 초기 온도 A에서 목표 온도 B까지 가열해야 한다.조건에 따라 걸리는 시간이 다르다.냉동 상태(0°C 미만)은 1도 올리는 데 C초 걸림.0°C에서 해동하는 데 D초 소모.해동된 후(0도 이상) 1도 올리는 데 E초 걸림.if A 초기 상태가 냉동 상태이고, 목표도 냉동 상태인 경우에는 단순히 A부터 B까지 C초로만 가열한다.elif A 0: print(-A * C + D + B * E)A를 0까지 올리는데 -A * C초가 필요로 한다.그 다음, 0도에서 해동하는데 D초가 걸리고, 해동 후 B도 까지 올리는데 B * E초가 걸린다.총시간을 수식으로 나타내면 -A * C + D + B * E 초가 소요된다.else: ..
[실버 1] 백준 1713 - 후보 추천하기 (파이썬)
[실버 1] 백준 1713 - 후보 추천하기 (파이썬)
2025.05.01https://www.acmicpc.net/problem/1713풀이사진틀이 N개 있다.총 M명의 추천이 차례로 주어진다.이미 사진틀에 있는 학생은 추천 수만 증가한다.사진틀에 자리가 없으면,추천 수가 가장 적은 사람을 사진틀에서 제거만약 추천 수가 같으면 가장 오래된 사람을 제거마지막에 사진틀에 걸려 있는 학생 번호를 오름차순 출력count = [0] * 100 # 학생별 추천 수 (인덱스 = 학생 번호 - 1)last = [-1] * 100 # 학생별 마지막 추천받은 시간 (인덱스 = 학생 번호 - 1)학생 번호는 1 ~ 100까지 가능하다.count[i] 는 i번 학생의 추천수를 나타낸다.last[i]는 i번 학생이 사진틀에 걸린 시간을 나타낸다.for i in range(M): C[i] ..
[브론즈 2] 백준 1173 - 운동 (파이썬)
[브론즈 2] 백준 1173 - 운동 (파이썬)
2025.05.01https://www.acmicpc.net/problem/1173풀이현재 맥박 : m, 최대 맥박 : M운동 할 때마다 맥박 T만큼 증가쉬면 맥박 R만큼 감소운동을 N번 해야한다.현재 맥박이 M을 초과하면 운동을 못한다.운동을 못할 때는 쉬어야한다.운동 N번을 완료하는 데 걸리는 시간을 출력하고,만약 아예 운동을 못 시작하는 상황이면 -1을 출력한다.if m + T > M : print(-1)현재 맥박 m에 운동 후 증가량 T를 더했을 때, M을 넘으면,아예 한 번도 운동할 수 없기에 -1을 출력하고 종료한다.else : timer = 0 X = m while N > 0 : timer += 1타이머를 0으로 초기화 하고, 현재 맥박 X를 m으로 초기화한다.운동을 N번 해..
[골드 5] 백준 13398 - 연속합 2 (파이썬)
[골드 5] 백준 13398 - 연속합 2 (파이썬)
2025.04.30https://www.acmicpc.net/problem/13398풀이주어진 수열에서 연속된 몇 개의 수를 선택해 가장 큰 합을 만든다.단, 원하는 경우 수열에서 수 하나를 ‘제거’할 수 있다.제거를 한 경우든 안 한 경우든 가장 큰 연속합을 구하는 문제D, E 배열을 초기화 한다.D = [-1e9] * NE = [-1e9] * ND[i] : A[0] ~ A[i] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합E[i] : A[i] ~ A[N-1] 까지 봤을 때 “수 하나도 제거 안 하고” 가능한 최대 연속합D배열을 채운다. (왼쪽 → 오른쪽)D[0] = A[0]for i in range(1, N): D[i] = max(A[i], A[i] + D[i - 1])D[0]은 시작점이니까 그냥..
[실버 4] 백준 10211 - Maximun Subarray (파이썬)
[실버 4] 백준 10211 - Maximun Subarray (파이썬)
2025.04.30https://www.acmicpc.net/problem/10211풀이여러 테스트 케이스가 주어진다.각 케스트 케이스마다, 연속된 구간의 합 중 최대값을 구하는 문제누적합 배열 psum을 생성한다.psum = [0] * Npsum[0] = X[0]psum[i] = X[0] + X[1] + … + X[i]for i in range(1, N) : psum[i] = psum[i - 1] + X[i]구간 합을 빠르게 계산하려고 누적합 배열을 사용한다.for i in range(N) : for j in range(i, N) : range_sum = psum[j] if i > 0 : range_sum -= psum[i - 1] if max_sum 모든 구간을 탐색하며,..
[실버 1] 백준 16198 - 에너지 모으기 (파이썬)
[실버 1] 백준 16198 - 에너지 모으기 (파이썬)
2025.04.30https://www.acmicpc.net/problem/16198풀이구슬이 일렬로 놓여 있고, 양끝 구슬을 제외하고 하나를 고를 수 있다.고른 구슬을 제거하면서 얻는 에너지는 (왼쪽 구슬 번호) * (오른쪽 구슬 번호)구슬이 2개 남을때까지 반복얻을 수 있는 에너지의 최대값을 구하라if len(a) == 2: return w구슬이 2개만 남으면 더이상 고를 수 없으니, 지금까지 모은 에너지를 반환한다.재귀 호출은 다음과 같이 진행한다.for i in range(1, len(a) - 1):맨 앞과 맨 뒤 구슬을 제외한 가운데 구슬만 고를 수 있다.na = a[:i] + a[i+1:]i번째 구슬을 제거해서 새로운 리스트를 만든다.tmp = dfs(na, w + a[i-1] * a[i+1])i번째 구슬..
[골드 4] 백준 12886 - 돌 그룹 (파이썬)
[골드 4] 백준 12886 - 돌 그룹 (파이썬)
2025.04.29https://www.acmicpc.net/problem/12886풀이돌이 A, B, C 그룹에 있다.한번의 연산이 진행된다.돌 수가 다른 두 그룹을 골라서, 돌 수가 적은 쪽을 2배로 만들고많은 쪽에서는 그 차이만큼 뺀다.세 그룹의 돌 수를 모두 같게 만들수 있는가?if S % 3 != 0: print(0)총합이 3의 배수가 아니라면 절대 세 그룹을 같은 수로 만들 수 없다.visit = [[False] * S for _ in range(S)]visit[a][b]가 True이면 (a, b, c = S - a - b)상태를 이미 방문 했다는 의미,a와 b만 알면 c는 S - a - b로 자동 결정되기 때문에 2차원 배열만 사용한다.queue = deque()queue.append((A, B))vis..
[실버 1] 백준 3184 - 양 (파이썬)
[실버 1] 백준 3184 - 양 (파이썬)
2025.04.29https://www.acmicpc.net/problem/3184풀이울타리로 막혀 있는 공간 안에 양과 늑대가 있다.한 영역에서 양의 수가 늑대보다 많으면 양이 살아남고, 늑대가 더 많거나 같으면 늑대가 살아남음최종적으로 살아남은 양과 늑대의 수를 구하는 문제R, C = map(int, input().split())B = [input() for _ in range(R)]R, C는 행, 열 크기를 나타내며, B는 농장의 상태를 저장한 2차원 리스트이다.대표적인 BFS 문제이다. 해당 문제는 visit 배열을 사용해서 풀이가 가능하다.visit = [[False] * C for _ in range(R)]queue = deque()dr = [1, -1, 0, 0]dc = [0, 0, 1, -1]final_o,..
[실버 3] 백준 28353 - 고양이 카페 (파이썬)
[실버 3] 백준 28353 - 고양이 카페 (파이썬)
2025.04.29https://www.acmicpc.net/problem/28353풀이고양이들의 체중 리스트가 주어지고,두 마리 고양이를 묶을 때, 체중 합이 K 이하이면 1쌍으로 만든다.최대 몇 쌍을 만들 수 있는지를 구하는 문제.A.sort()체중을 오름차순으로 정렬한다. 가장 가벼운 고양이와 가장 무거운 고양이를 매칭해서 최대한 많이 쌍을 만들려고 하기 때문이다.투 포인터는 다음과 같이 준비한다.start, end = 0, N - 1count = 0start는 제일 가벼운 고양이를 가리키며 왼쪽 포인터를 의미한다.end는 제일 무거운 고양이를 가리키며 오른쪽 포인터를 의미한다.count는 만든 쌍의 수를 나타낸다.while start 두 고양이의 체중 합 A[start] + A[end]를 확인하여, 합이 K 이하이..
[골드 3] 백준 3673 - 나눌 수 있는 부분 수열 (파이썬)
[골드 3] 백준 3673 - 나눌 수 있는 부분 수열 (파이썬)
2025.04.29https://www.acmicpc.net/problem/3673풀이길이 N인 수열이 있을 떄,부분 수열의 합이 D로 나누어 떨어지는 경우의 수를 구해라누접합 배열을 만들어서, 누적합을 D로 나눈 나머지를 활용하면 풀이가 가능하다.T = int(input())for _ in range(T): D, N = map(int, input().split()) A = list(map(int, input().split())) psum = [0] * N psum[0] = A[0] for i in range(1, N): psum[i] = psum[i-1] + A[i]누적 합 계산을 진행한다.테스트 케이스 T개 만큼 반복하면서, 각 테스트 케이스마다 나누는 수 D와 배열 크기 N을 ..
[골드 2] 백준 2637 - 장난감 조립 (파이썬)
[골드 2] 백준 2637 - 장난감 조립 (파이썬)
2025.04.28https://www.acmicpc.net/problem/2637풀이어떤 완제품을 만들기 위해 여러 부품이 필요하고, 그 부품들 또한 다른 부품들로 조립되는 구조완제품 번호는 항상 N번이고, 기본 부품은 다른 부품으로 구성되지 않는 것기본 부품마다 완제품을 1개 조립할 때 필요한 개수를 구하는 문제입력 처리 및 그래프 구성은 아래와 같이 구현한다.adj = [[] for _ in range(N)] # 인접 리스트 (X -> (Y, K): X는 Y를 K개 사용함)count = [0] * N # 진입 차수 저장for i in range(M): X, Y, K = map(int, input().split()) X -= 1 Y -= 1 adj[X].append(..
[골드 5] 백준 12865 - 평범한 배낭 (파이썬)
[골드 5] 백준 12865 - 평범한 배낭 (파이썬)
2025.04.28https://www.acmicpc.net/problem/12865풀이물건 개수 : N배낭의 최대 무게 : K각 물건은 W, V : 무게, 가치각 물건은 한 번만 쓸 수 있다.무게 ≤ K 조건을 만족하면서 가치의 합을 구하는게 목표기본적인 다이나믹 프로그래밍인데 나는 왜이렇게 어렵게 느껴지는걸까.먼저 dp[j]는 무게 j일때, 만들 수 있는 최대 가치를 나타낸다.그래서 dp = [0] * (K+1)로 무게 0부터 K까지 모든 무게에 대해, 처음엔 가치를 0으로 초기화 한다.dp = [0] * (K + 1)점화식을 다음과 같이 구성한다.for w, v in items : for j in range(K, w - 1, -1) : dp[j] = max(dp[j], dp[j - w] + v)현재..
[골드 5] 백준 15681 - 트리와 쿼리 (파이썬)
[골드 5] 백준 15681 - 트리와 쿼리 (파이썬)
2025.04.28https://www.acmicpc.net/problem/15681풀이루트가 R인 트리가 주어짐각 쿼리는 정점 U를 루트로 하는 서브트리의 정점 개수를 묻는다여러 쿼리에 대해 빠르게 답변해야 하므로 DFS를 활용한 서브트리 크기 미리 계산이 핵심adj = [[] for _ in range(N)]adj[u]에 연결된 정점들 v를 저장하여 무방향 트리를 구성한다.D = [0] * ND[u]는 u를 루트로 하는 서브트리의 정점 수를 나타낸다.def dfs(u): visit[u] = True D[u] = 1 # 자기 자신 포함 for v in adj[u]: if not visit[v]: dfs(v) D[u] += D[v]DFS를 통한 서브트리..
[실버 2] 백준 11060 - 점프 점프 (파이썬)
[실버 2] 백준 11060 - 점프 점프 (파이썬)
2025.04.27https://www.acmicpc.net/problem/11060풀이각 칸마다 점프할 수 있는 최대 칸 수가 주어짐0번 인덱스부터 시작해서 N-1번 인덱스로 가야 함최소 몇 번의 점프로 도달할 수 있는지 구함못 가면 -1 출력N = int(input()) # 칸의 수A = list(map(int ,input().split())) # 각 칸에서 점프 가능한 최대 거리A[i]는 i번 칸에서 최대 A[i]칸 까지 점프가 가능하다는 뜻을 의미한다.D = [1e9] * N # DP 배열, 최소 점프 횟수를 저장 (초기값은 매우 큰 값)D[N - 1] = 0 # 마지막 칸은 도달했으므로 점프 횟수 0for i in range(N - 2, -1, -1): # 뒤에서부터 탐색 for j in rang..
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)
2025.04.27https://www.acmicpc.net/problem/9657풀이돌이 N개 있을 때, SK와 CY가 번갈아 가면서 돌을 가져간다.한번에 1, 3, 4개의 돌만 가져갈 수 있다.마지막 돌을 가져가는 사람이 이긴다.SK가 먼저 시작할 때, 누가 이기는지 판단하는 문제이다.D[i]를 i개의 돌이 있을 때 SK가 이길수 있는가를 나타내는 Boolean 배열로 설정한다.True → SK가 이기는 경우Fasle → CY가 이기는 경우핵심은 현재 상태에서 내가 이길 수 있는 수를 선택하면 이긴다는 점이다.즉, D[i] = not D[i - 1] or not D[i - 3] or not D[i - 4] 이다.초기 조건은 다음과 같이 설정한다.D[1] = True # SK가 1개 가져가서 승D[2] = False..
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
2025.04.26https://www.acmicpc.net/problem/1655풀이매번 새로운 수를 입력받으면, 지금까지의 수 중에서 중간값을 출력해야 한다.수의 개수가 홀수이면, 정렬했을 때 가운데 수가 중간값이고수의 개수가 짝수이면, 가운데 두 수 중에서 작은 수가 중간값이다.왼쪽 힙 (left): 최대 힙. 중간값보다 작거나 같은 값 저장 (최댓값이 top)오른쪽 힙 (right): 최소 힙. 중간값보다 큰 값 저장 (최솟값이 top)중간값 위치항상 left가 right보다 같거나 1개 많도록 유지하면,중간값은 left의 루트에 위치함 (-left[0])heapq.heappush(left, -X)우선 left (최대 힙)에 넣음 (-부호로 최대 힙을 구성)if right and -left[0] > right[0]..
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)
2025.04.26https://www.acmicpc.net/problem/3197풀이백조의 호수 문제는 BFS를 통해서 풀이가 가능하다.문제에서 요구하는 조건은 호수에 얼음이 덮여있다.얼음으로 뒤덮인 호수에 백조 두 마리가 있음물은 백조가 지나갈 수 있지만 얼음은 못 감매일 얼음이 물과 접촉한 부분부터 녹음두 백조가 만날 수 있는 최소 날짜를 구하는 문제입력 처리 및 초기 세팅을 진행R, C = map(int, input().split())A = [list(input()) for _ in range(R)]R, C와 맵을 2차원 리스트로 저장한다.백조 위치 탐색swans = []for i in range(R): for j in range(C): if A[i][j] == "L": swa..
[골드 5] 백준 12919 - A와 B 2 (파이썬)
[골드 5] 백준 12919 - A와 B 2 (파이썬)
2025.04.26https://www.acmicpc.net/problem/12919풀이문자열 S에서 시작하여 문자열 T를 만들 수 있는지 판단하는 문제이다.수행할 수 있는 연산은 다음과 같다,문자열 뒤에 ‘A’ 추가문자열을 뒤집고 뒤에 ‘B’ 추가하지만 이 코드에서는 역방향으로, 즉 T에서 시작해서 S로 갈 수 있는지 확인한다.def dfs(t): if len(t) == len(S): return t == S현재 문자열 t의 길이가 S와 같아졌다면 t == S 인지 비교해서 결과를 반환한다.if t[-1] == "A": if dfs(t[:-1]): return True재귀 조건으로 문자열 끝이 A라면 A를 추가한 결과였을 수 있으므로 마지막 문자를 제거하고 재귀를 호출한다.if t[0..
[골드 2] 백준 2381 - 최대 거리 (파이썬)
[골드 2] 백준 2381 - 최대 거리 (파이썬)
2025.04.25https://www.acmicpc.net/problem/2381풀이N = int(input())P = [list(map(int, input().split())) for _ in range(N)]N개의 점을 입력받고 리스트 P에 저장한다.max_plus = -1e9min_plus = 1e9for x, y in P : max_plus = max(max_plus, y + x) min_plus = min(min_plus, y + x)(x + y)의 최대값 최소값을 계산한다.max_minus = -1e9min_minus = 1e9for x, y in P : max_minus = max(max_minus, y - x) min_minus = min(min_minus, y - x)(y - x)의..