[골드 3] 백준 1719 - 택배 (파이썬)
[골드 3] 백준 1719 - 택배 (파이썬)
2025.07.13https://www.acmicpc.net/problem/1719분류 : 다익스트라링크 : https://www.acmicpc.net/problem/1719풀이이 문제는 어느 경로로 가는 것이 최단 경로인지를 알아내는 문제이다.각 도시(정점) 간의 최단 경로를 찾아야하며, 단순히 최단 거리만 출력하는 것이 아니라, 어디로 먼저 가야 하는지를 출력해야한다.즉, i → j 로 갈 때 첫번째로 가야하는 도시를 출력해야하는 것ㅇ디ㅏ.from queue import PriorityQueueN, M = map(int, input().split()) # 도시 수 N, 도로 수 Madj = [[] for _ in range(N)] # 인접 리스트# 간선 정보 입력for _ in range(M): a, ..
[Reversing.kr] Easy Crack
[Reversing.kr] Easy Crack
2025.07.12흠,, 포렌식만 공부하다가 이제 리버싱도 슬슬 해볼까 해서 reversing.kr 을 풀어보기 시작했다.역시 리버싱은 공부해도 어려운것 같다.. 포렌식 보다 훨씬 더,, 해당 포스팅은 포렌식 7년차의 리버싱 입문기라고 생각하고, 틀린점이 있어도 그냥 귀엽게 넘어가 주면 좋겠다.Easy_CrackMe.exe의 파일은 다음과 같다.FileNameEasy_CrackMe.exeFileSize40,960 ByteCRC32FE454D60MD5A74DB218A9175E0AE2CCFFB3476DD4CFSHA-1F153F26F16B5AE03E3A7BE7FFE5395E966051F3BEasy_CrackMe.exe 를 실행하면 다음과 같은 창이 나타난다.아무거나 입력 후 확인을 클릭하면 다음과 같이 Incorrect Pas..
[골드 5] 백준 14284 - 간선 이어가기 2 (파이썬)
[골드 5] 백준 14284 - 간선 이어가기 2 (파이썬)
2025.07.12https://www.acmicpc.net/problem/14284풀이이 문제는 조금 방향 없는 그래프, 즉 무방향 그래프가 주어지며, 정점수 N, 간선수 M이 주어진다.각 간선은 가중치를 가지며, 출발점 S에서 도착점 T까지의 최단 거리를 구하는 문제이다.이 문제에세의 핵심 알고리즘은, 단연코 다익스트라 알고리즘이라고 할 수 있다.먼저 가중치가 있는 그래프에서 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며, 이 문제에서는 특정 시작점에서 특정 도착점 까지의 거리만 구하면 된다.from queue import PriorityQueue우선순위 큐는 최소 거리 기준으로 정점을 꺼내기 위해서 위와 같이 사용한다.N, M = map(int, input().split())adj = [[]..
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
[골드 5] 백준 17072 - 나무 위의 빗물 (파이썬)
2025.07.11https://www.acmicpc.net/problem/17073풀이이 문제는 비의 양 W가 루트 노드에 고이며, 나무는 N개의 정점으로 이루어진 트리이고, 루트 노드는 1번이다.비는 모든 리프 노드까지 동일하게 분배되며, 각 리프 노드까지 고인 빗물의 양을 구하는 문제이다.결국 이 문제를 해결하는 방법은 다음과 같다.트리는 사이클이 없는 연결 그래프이므로, DFS로 리프 노드를 쉽게 찾을 수 있다.루트에서 DFS를 돌려 리프 노드의 개수를 센다.전체 물이의 양 W를 리프 노드 개수로 나눈다.리프노드마다 동일한 양의 물이 고이기 때문이다.먼저 정점 수, 물의 양을 입력받는 인접 리스트를 생성한다.N, W = map(int, input().split())adj = [[] for _ in range(N)]..
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
2025.07.09https://www.acmicpc.net/problem/20159풀이플레이어가 번갈아 가면서 카드를 가져간다.짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.psum0 = [0] * N # 내 차례에서의 누적합psum1 = [0] * N # 상대 차례에서의 누적합psum0[0] = A[0]psum1[0] = 0for i in range(1, N): if i % 2 == 0: # 내 차례 psum0[i] = psum0[i - 1] + A[i] psum1[i] = psum1[i - 1] else: ..
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
2025.07.09https://www.acmicpc.net/problem/29767풀이길이가 N인 정수 수열 A가 주어지며, 누적합(A[0]부터 A[i]까지의 합)을 구해 전체 N개의 누적합 중 K개를 선택해서 합을 최대로 만들어야한다.N, K = map(int, input().split())A = list(map(int, input().split()))N은 원소 개수, K는 선택할 누적합 개수를 입력 받는다.psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 A[0] + A[1] + … + A[i]를 의미하며, 즉, 누적합 배열을 만든다.psum.sort(reverse=True)print(sum(psum[:K]..
[플래티넘 5] 백준 1050 - 물약 (파이썬)
[플래티넘 5] 백준 1050 - 물약 (파이썬)
2025.07.08https://www.acmicpc.net/problem/1050풀이여러개의 기초 물약은 가격이 주어지고, 일부 물약은 다른 물약들로 조합하여 만들 있다.조합은 "LOVE=A+2B" 같은 형태로 주어진다.목표: 물약 “LOVE”를 만드는데 필요한 최소 비용 계산하는 것이다.N, M = map(int, input().split())stuff = {}N은 가격이 주어진 물약 수를 나타내며, M은 조합식 수를 나타낸다.for _ in range(N) : name, cost = input().split() cost = int(cost) stuff[name] = cost가격이 주어진 물약은 딕셔너리 stuff에 저장한다.formulas = [input() for _ in range(M)]LOVE ..
[골드 2] 백준 2461 - 대표 선수 (파이썬)
[골드 2] 백준 2461 - 대표 선수 (파이썬)
2025.07.07https://www.acmicpc.net/problem/2461분류 : 정렬 + 우선순위 큐링크 : https://www.acmicpc.net/problem/2461풀이N개의 반이 있고, 각 반에는 M명의 학생이 있음.각 학생마다 실력이 있고, 각 반에서 한 명씩 대표로 뽑아서 실력 차이를 최소로 하고 싶음.즉, N명의 대표를 뽑을 때 최소 실력차가 가장 작은 집합을 만들고, 그 차이를 출력해야 함.from queue import PriorityQueue• Python 표준 라이브러리의 우선순위 큐 (최소 힙 역할) 사용N, M = map(int, input().split())A = [list(map(int, input().split())) for _ in range(N)]N개의 반마다 M명의 학생 실..
[골드 5] 백준 23843 - 콘센트 (파이썬)
[골드 5] 백준 23843 - 콘센트 (파이썬)
2025.07.06https://www.acmicpc.net/problem/23843풀이총 N개의 기기를 충전해야 한다.충전기는 M개의 콘센트가 있다.각 기기를 충전하는 데 걸리는 시간이 배열 A로 주어진다.한 번에 M개까지 충전 가능하며, 각 콘센트는 병렬로 작동한다.모든 기기를 충전 완료하는 데 걸리는 최소 시간을 구하라.A.sort(reverse=True) # 시간이 긴 기기부터 우선 배정가장 긴 기기부터 먼저 처리해야 전체 시간이 줄어든다.그리디 전략: 긴 작업을 먼저 분산시켜야 부하가 치우치지 않음.pq = [0] * Mheapq.heapify(pq)pq: 각 콘센트의 누적 충전 시간을 관리처음엔 모두 0초 (아무것도 안 꽂힌 상태)heapq를 사용해서 가장 빨리 끝나는 콘센트를 찾기 용이하게 함 (최소 힙)f..
[실버 1] 백준 1629 - 곱셈 (파이썬)
[실버 1] 백준 1629 - 곱셈 (파이썬)
2025.07.05https://www.acmicpc.net/problem/1629풀이A^B % C를 직접 계산하면 시간 복잡도 O(B), 너무 크다.A^B = A^(B//2) * A^(B//2) (짝수일 경우)A^B = A^(B//2) * A^(B//2) * A (홀수일 경우)이를 이용해서 재귀적으로 절반씩 계산하면서 나머지를 구하는 방식을 사용한다. → 시간복잡도 O(log B)def power(a, b, c): if b == 0: return 1 # a^0 = 1 if b == 1: return a % c # a^1 % c = a % c x = power(a, b // 2, c) # A^(B//2) 값을 재귀 호출로 구함 if b % 2 == 0: ..
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
2025.07.04https://www.acmicpc.net/problem/12784풀이인하니카 공화국의 수도는 1번 정점(문제에서는 0번으로 인덱싱)이다.나머지 모든 정점은 루팡에 의해 공격받을 수 있고, 이들을 방어하기 위해 일부 간선에 폭탄을 설치해야 한다.폭탄은 정점에 도달하는 가장 짧은 경로에 설치되고, 그 간선의 최소 비용이 사용된다.최소한의 비용으로 모든 리프 노드를 보호하려고 할 때, 그 비용을 구하는 문제다.입력 및 그래프를 구성한다.N, M = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(M) : a, b, c = map(int, input().split()) a -= 1 b -= 1 adj[a].appen..
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
2025.07.04https://www.acmicpc.net/problem/2749풀이이미지 출처 : https://velog.io/@cha-suyeon/python-피보나치-수열-만들기-점프투파이썬-종합문제-5번피보나치 수열은 위 그림 처럼 제일 초기 1에서 1을 더한 값이 2, 2와 1을 더한 값이 3, …, n - 1번째 값과 n을 더한값.. 이런식으로 계속해서 늘어나는 수열이다.결국 식을 작성하면 다음과 같다.Fn = Fn-1 + Fn-2 (n >= 2)이런식으로 n 이 17일때의 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.여기서 한가지 고려해..
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
2025.07.03https://www.acmicpc.net/problem/20188풀이트리 DP 또는 서브트리 크기 기반의 조합 계산을 사용한 문제이다.무방향 트리이며, 등상 마니아들은 경로 (a, b, c)를 선택할 때 항상 a → b → c 순으로 이동한다.단, b는 a와 c의 LCA(최소 공통 조상)이어야 한다.모든 (a, b, c) 쌍에서의 경우의 수를 계산해야한다.사용한 아이디어어떤 간선을 제거하면 트리가 두 개의 서브트리로 나뉘게 된다.해당 간선을 통해 만들어지는 (a, b, c)의 경우의 수는 다음 두개로 나뉜다.서브 트리 내부에서 a, c를 고르고 b가 그 루트인 경우 → sizes[i] * (sizes[i] - 1) / 2서브트리와 바깥에서 a, c를 하나씩 고르고 b가 그 경계인 경우 → sizes[i..
[실버 2] 백준 17213 - 과일 서리 (파이썬)
[실버 2] 백준 17213 - 과일 서리 (파이썬)
2025.07.03https://www.acmicpc.net/problem/17213풀이서로 다른 N개의 과일 중에서 M개를 훔쳐올 때, 적어도 1개씩은 훔치는 경우의 수를 구하는 문제이다.적어도 1개씩 N종료의 과일을 가져온다는 조건은 곧 M개의 과일을 N개의 상자에 각각 적어도 1개씩 넣는 방법의 수를 묻는 것과 같다.이는 중복 조합의 문제로 환원되며, 중복 조합의 식은 다음과 같다.answer = 1for i in range(1, M - N + 1) : answer *= (M - i) answer //= i위 코드는 nCr의 계산 중에서 n = M - 1, r = M - N을 계산하는 것이다.파이썬 내장 함수 없이 직접 계산이 가능하다. (Collection 모듈)코드# 백준 17213 - 과일 서리# 분..
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
2025.07.02https://www.acmicpc.net/problem/1655풀이max_pq는 왼쪽 절반, 즉 중간값 이하를 담고 최대 힙으로 운용한다. (파이썬에서는 -값을 넣어 사용)min_pq는 오른쪽 절반, 즉 중간값 초과를 담고 최소 힙으로 운용한다.입력값과 max_pq, min_pq에서 하나씩 빼서 총 3개의 숫자 후보를 만들고 정렬 후 재분배한다.중간값은 항상 max_pq의 top인 -max_pq[0]이 된다.max_pq = [1e9]min_pq = [1e9]1e9를 미리 넣어둔다. 즉 힙이 비어있을때 heappop 하기 위한 임시값이다.하지만 이건 비정상적인 초기값이고, 결과적으로 정답이 이상해 질 수 도 있다.a = [A[i]]a.append(-heapq.heappop(max_pq))a.append(..