Programming
[브론즈 1] 백준 10041 - 관광 (파이썬)
[브론즈 1] 백준 10041 - 관광 (파이썬)
2025.05.04https://www.acmicpc.net/problem/10041풀이W, H: 전체 지도 크기 (사용되지 않음)N: 방문할 지점 수P: 각 방문 지점의 좌표인접한 지점 (x1, y1) → (x2, y2)로 이동할 때 거리 계산 방식:y1 > y2일 때: 단순 맨해튼 거리|x1 - x2| + |y1 - y2|y1 ≤ y2일 때: 체스의 킹처럼 이동 (대각선 허용)max(|x1 - x2|, |y1 - y2|)answer = 0for i in range(N - 1): x1, y1 = P[i] x2, y2 = P[i + 1] # 방향을 통일 (x1 x2: x1, x2 = x2, x1 y1, y2 = y2, y1항상 x1 ≤ x2로 만들어 방향을 일관되게 처리한다.if..
[브론즈 2] 백준 10040 - 투표 (파이썬)
[브론즈 2] 백준 10040 - 투표 (파이썬)
2025.05.04https://www.acmicpc.net/problem/10040풀이N명의 선수에게 각각 가장 낮은 응모 번호 이상인 응모자 한 명씩을 배정한다.응모자는 B 리스트에, 선수의 응모 기준 번호는 A 리스트에 주어진다.가장 많은 응모자를 배정받은 선수의 번호(1-based)를 출력해야 한다.count = [0] * N # 각 선수에게 배정된 응모자 수for i in range(M): # 모든 응모자에 대해 for j in range(N): # 선수 순서대로 확인 if A[j] A[j] ≤ B[i]인 가장 첫번쨰 선수 J를 찾아서 B[i]를 배정한다.응모자는 한 번만 배정되며, 여러 선수가 가능하다면 가장 앞에 있는 선수에게 배정된다.max_vote = 0who = -1for i in..
[브론즈 2] 백준 14471 - 포인트 카드 (파이썬)
[브론즈 2] 백준 14471 - 포인트 카드 (파이썬)
2025.05.04https://www.acmicpc.net/problem/14471풀이N개의 포인트를 사용하여 M개의 카드를 구매하고 싶다.각 카드에는 (a, b)가 주어지며,a는 현재 모인 포인트 수b는 해당 카드의 포인트 카드 개수카드를 구매하기 위해서는 포인트가 a 이상이어야 한다.카드를 구매하면 b만큼 포인트가 오른다.목표는 총 N개의 포인트를 모으는 최소한의 비용을 계산하는 것.코드# 백준 14471 - 포인트 카드# 분류 : 그리디N, M = map(int, input().split())C = [list(map(int, input().split())) for _ in range(M)]C.sort(reverse=True)cost = 0for i in range(M - 1) : if C[i][0]
[골드 3] 백준 4179 - 불! (파이썬)
[골드 3] 백준 4179 - 불! (파이썬)
2025.05.03https://www.acmicpc.net/problem/4179풀이지훈이(J)는 미로에서 탈출해야 함.불(F)은 매 분마다 상하좌우로 번짐.지훈이는 1분에 1칸 이동 가능.벽(#)은 지나갈 수 없음.불이 도착한 시간보다 지훈이가 먼저 도착해야 탈출 가능.fire[][] 와 jihun[][] 배열fire[i][j]: (i,j)에 불이 도달하는 시간jihun[i][j]: (i,j)에 지훈이가 도달하는 시간1은 아직 도달하지 않은 상태while q1: ...먼저 모든 불의 위치에서 동시에 시작하여 BFS를 수행.(x, y) → (nx, ny)로 퍼져가며 fire[nx][ny] = fire[x][y] + 1로 시간 기록.while q2: ...지훈이가 이동할 수 있는 경로 탐색.이동하려는 칸이 불이..
[실버 5] 백준 31738 - 매우 어려운 문제 (파이썬)
[실버 5] 백준 31738 - 매우 어려운 문제 (파이썬)
2025.05.03https://www.acmicpc.net/problem/31738풀이이 문제는 시간에 매우 민감한 문제이다.# 백준 31738 - 매우 어려운 문제# 분류 : 수학import mathN, M = map(int, input().split())if N >= M : print(0)else : print(math.factorial(N) % M)대충 이렇게 math 패키지로 팩토리얼을 계산한 경우 시간 초과가 일어나게 된다. 아마 계속해서 수를 증가시키면서 곱하기 때문에 시간 초과가 일어나는것으로 보인다.먼저 N이 M보다 큰 경우에는 어떤 수로 나누어도 0이 나올 수 밖에 없다.수학적으로 N ≥ M인 경우 M은 N!의 약수가 되므로 N! mod M = 0이 된다예를들어서 5! = 120, M = 5인..
[골드 4] 백준 10830 - 행렬 제곱 (파이썬)
[골드 4] 백준 10830 - 행렬 제곱 (파이썬)
2025.05.03https://www.acmicpc.net/problem/10830풀이크기 N \times N의 정수 행렬 A가 주어짐자연수 B가 주어질 때,A^B \mod 1000 을 구하라(여기서 A^B는 행렬 곱 기준의 거듭제곱)내가 먼저 실수한 부분은 다음과 같다.A ** B → 원소별 제곱임 (X)for i in range(B): A = A @ A → 시간 초과 (X)풀이 순서를 생각하면 다음과 같다.팩토리얼 전처리0!부터 N!까지 전부 리스트에 저장 (O(N))분자 계산N!분모 계산K! * (N-K)!모듈러 역원 적용분모의 역원을 구해서 분자와 곱함최종 계산결과를 MOD로 나눈다✅ 정답 접근 (분할 정복)🔍 핵심 아이디어\( A^B = A^{B//2} \times A^{B//2} \) (짝수)\( A^B =..
[골드 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,..