Programming/백준
[실버 2] 백준 15666 - N과 M (12) (파이썬)
[실버 2] 백준 15666 - N과 M (12) (파이썬)
2025.05.07https://www.acmicpc.net/problem/15666풀이자연수 N개 중에서 M개를 중복 선택 가능하게 고르되,고른 수열은 비내림차순이어야 하고,중복되는 수열은 한 번만 출력해야 합니다.N, M = map(int, input().split())nums = list(map(int, input().split()))nums = sorted(list(set(nums)))nums에서 중복 제거 후 정렬한다. 왜냐하면 중복 수열 출력을 방지하기 위해서이다.def back(start, depth): if depth == M: print(' '.join(map(str, result))) return for i in range(start, len(nums)): ..
[실버 2] 백준 16953 - A → B (파이썬)
[실버 2] 백준 16953 - A → B (파이썬)
2025.05.07https://www.acmicpc.net/problem/16953풀이정수 A를 B로 만들기 위해 사용할 수 있는 연산은A → A * 2A → A * 10 + 1최소한의 연산 횟수로 A를 B로 만들고 싶다. 만들 수 없다면 -1을 출력.이 코드는 B에서 A로 거꾸로 줄여나가는 방식왜냐하면 A에서 B로 모든 경우를 시도하면 탐색 공간이 매우 커질 수 있기 때문주요 아이디어B를 줄여가면서 A가 될 수 있는지 확인한다.가능한 줄이는 방법B % 10 == 1 → 끝자리가 1이면 B // 10B % 2 == 0 → 짝수면 B // 2그 외에는 더 이상 줄일 수 없으므로 중단코드# 백준 16953 - A -> B# 분류 : 그래프A, B = map(int, input().split())count = 1while B..
[골드 1] 백준 2933 - 미네랄 (파이썬)
[골드 1] 백준 2933 - 미네랄 (파이썬)
2025.05.07https://www.acmicpc.net/problem/2933풀이막대기를 던져 미네랄(‘x’)을 부수면, 공중에 뜬 미네랄 클러스터는 중력 방향으로 낙하해야 한다.미네랄은 바닥 또는 다른 미네랄과 맞닿아 있어야 멈춘다.막대기는 번갈아 가며 왼쪽/오른쪽에서 날아오며, 부딪힌 첫 번째 미네랄을 부순다.1. 막대기 던지기입력받은 높이에 따라 해당 줄에서 가장 먼저 만나는 미네랄(‘x’)을 제거한다.던지는 방향은 짝수 턴에는 왼쪽에서 오른쪽, 홀수 턴에는 오른쪽에서 왼쪽이다.2. 클러스터 탐색 (BFS)미네랄 덩어리(클러스터)는 상하좌우 인접한 미네랄끼리 연결되어 있다.visited 배열을 이용해 미네랄 덩어리를 하나씩 탐색한다.3. 공중 클러스터 분리 및 낙하 처리바닥에 닿지 않은 클러스터는 중력의 영향을..
[골드 5] 백준 1419 - 등차수열의 합 (파이썬)
[골드 5] 백준 1419 - 등차수열의 합 (파이썬)
2025.05.07https://www.acmicpc.net/problem/1419풀이주어진 등차수열의 규칙은 다음과 같다.k = 2: 수열은 3, 4, 5, ... 이므로 x ≥ 3k = 3: 수열은 4, 7, 10, 13, ... → 일반항 3n + 1 → n ≥ 1k = 4: 수열은 4, 6, 8, 10, 14, 16, ... → 짝수 중에서 12만 빠짐k ≥ 5: 5n + 2 이고, n ≥ 2각 케이스마다 상한 (r)까지 몇 개 있는지와 하한 (l)보다 작은 부분까지 몇 개 있는지를 구해서 그 차이를 구한다.즉, f(r) - f(l - 1) 형태로 개수를 구한다.각각 K = 2 ~ 4, K ≥ 5일때의 상황을 구해야한다.k == 2 일때if k == 2 : upper = max(0, r - 2) lowe..
[실버 3] 백준 25418 - 정수 a를 k로 만들기 (파이썬)
[실버 3] 백준 25418 - 정수 a를 k로 만들기 (파이썬)
2025.05.06https://www.acmicpc.net/problem/25418풀이이 문제는 정수 A에서 출발해서 두가지 연산이 가능하다.1을 더하기 (x → x + 1)2배 만들기 (x → 2x)를 사용하여 목표 정수 K를 만드는 최소 연산 횟수를 묻는다.그래프 모델링각 정수 i를 노드로 보고,i → i+1, i → 2*i 두 개의 간선을 가진다.시작 노드는 A, 목표 노드는 K가 된다.최단 경로 탐색모든 간선의 가중치가 1이므로, 너비 우선 탐색(BFS)을 사용하면 시작점에서 목표점까지의 최소 간선 수(연산 횟수)를 구할 수 있다.구현 세부사항visit[i]: 정수 i에 한 번이라도 도달했는지 표시dist[i]: 시작 정수 A에서 i에 도달하기까지의 최소 연산 횟수queue: BFS용 덱(Deque)인접 리스트 ..
[실버 4] 백준 18242 - 네모네모 시력검사 (파이썬)
[실버 4] 백준 18242 - 네모네모 시력검사 (파이썬)
2025.05.05https://www.acmicpc.net/problem/18242풀이#으로 구성된 직사각형 모양에서 하나의 칸만 .으로 뚫려 있음.이 구멍이 어느 방향에 뚫려 있는지 출력해야 함: UP, DOWN, LEFT, RIGHTmin_y, max_y, min_x, max_x = 1e9, 0, 1e9, 0for i in range(N): for j in range(M): if B[i][j] == '#': min_y = min(min_y, i) max_y = max(max_y, i) min_x = min(min_x, j) max_x = max(max_x, j)“#”의 좌표 중 가장 위, 아래, 왼쪽, 오른쪽을 찾아 네모..
[골드 5] 백준 10710 - 실크로드 (파이썬)
[골드 5] 백준 10710 - 실크로드 (파이썬)
2025.05.05https://www.acmicpc.net/problem/10710풀이N개의 도시간 거리: D[1] ~ D[N]M일간 날씨 나쁨 정도: C[1] ~ C[M]도시 0 → 도시 N까지 정확히 N번 이동해야 함 (각 이동은 하루 소요)한 날에 이동하거나, 대기 가능이동일을 적절히 골라, 총 피로도 = D[i] * C[j]의 합이 최소가 되도록 해야 함이 문제는 배낭 문제의 변형 + 구간 DP 또는 최적 부분 구조를 활용한 다이나믹 프로그래밍 문제이다.먼저 dp[i][j]는 i일째까지 고려했을 때, j개의 도시를 이동한 최소 피로도를 나타낸다.dp = [[1e9] * (N + 1) for _ in range(M + 1)]dp[0][0] = 0예를들어서 dp[3][1] = 3 이라면 3일 동안 도시 한칸만 이동했..
[브론즈 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: ..