[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)
[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)
2025.05.08https://www.acmicpc.net/problem/5639풀이전위 순회를 후위 순회로 변환하는 구현을 진행해야한다.즉, 전위 순회 결과가 주어졌을 때, 해당 트리의 후위 순위 결과를 출력해야한다.입력은 전위 순회 결과이며, 이진 검색 트리 조건이 적용된다.왼쪽 자식 def postorder(start, end): if start >= end: return root = preorder[start] # 현재 서브트리의 루트 # 오른쪽 서브트리의 시작 인덱스를 찾기 right = start + 1 while right preorder[start]는 항상 서브트리의 루트 노드이며, 그 다음부터 preorder[right] 조건이 깨지는 최초의 right는 ..
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
2025.05.08https://www.acmicpc.net/problem/1916풀이방향성이 있는 그래프에서 start 도시에서 end 도시로 가는 최소 비용을 구하는 문제이다. 즉 다익스트라를 이용해야한다.가중치가 있는 간선들이 주어지며, 음의 간선이 없다.인접리스트와 최단거리 테이블을 초기화 하기 위해서 다음과 같이 초기화 한다.adj = [[] for _ in range(N + 1)] # 인접 리스트distance = [INF] * (N + 1) # 최단거리 테이블 초기화도시 번호는 1부터 시작하므로 N + 1 크기로 배열을 잡고, INF는 초기 거리를 무한대로 세팅한다.간선 정보 저장을 위해서 다음과 같이 정의 한다.for _ in range(M) : u, v, cost = map(int, input()..
[실버 1] 백준 27970 - OX (파이썬)
[실버 1] 백준 27970 - OX (파이썬)
2025.05.08https://www.acmicpc.net/problem/27970풀이문자열 S가 주어집니다. S는 'O'와 'X'로만 구성되어 있다.우리는 문자열 내 'O'들이 가지는 “가중치 합”을 구해야 한다.'O'가 있는 위치의 2의 거듭제곱 값을 더한다.결과는 1,000,000,007 (10^9 + 7) 로 나눈 나머지를 출력한다.✅ 풀이 로직power는 현재 인덱스의 2의 거듭제곱 값을 의미한다.예를 들어, 인덱스 0: 2^0, 인덱스 1: 2^1, …, 인덱스 i: 2^i문자열을 왼쪽부터 오른쪽으로 순회하면서만약 해당 문자가 'O'라면, answer에 현재의 power 값을 더한다.그 후 power *= 2 로 2의 거듭제곱을 갱신한다.중간중간 mod 연산으로 값을 줄여준다.코드# 백준 27970 - OX#..
[실버 1] 백준 1697 - 숨바꼭질 (파이썬)
[실버 1] 백준 1697 - 숨바꼭질 (파이썬)
2025.05.08https://www.acmicpc.net/problem/1697풀이수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이는 1초에 다음 세 가지 행동 중 하나를 선택할 수 있다:X - 1로 이동 (1초 소요)X + 1로 이동 (1초 소요)2 * X로 순간이동 (1초 소요)목표는 수빈이가 동생에게 도달하는 데 걸리는 최소 시간을 구하는 것이다.이 문제는 각 위치를 정점으로 보고, 가능한 이동을 간선으로 간주하여 최단 거리를 구하는 그래프 탐색 문제로 볼 수 있다.특정 위치에서 세 방향으로 이동 가능하므로, 그래프 탐색을 통해 가장 먼저 도착하는 경우가 최소 시간이 된다.BFS는 그래프에서 최단 거리를 구할 때 매우 적절한 알고리즘이다. BFS는 먼저 도달한 경로가 최단 경로임을 보장하므로, 동생..
[실버 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일 동안 도시 한칸만 이동했..
[Level 3] 프로그래머스 - 가장 먼 노드
[Level 3] 프로그래머스 - 가장 먼 노드
2025.05.04https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이노드 1번부터 출발하여 최단 거리로 이동할 떄가장 멀리 있는 노드의 개수를 구하는 문제이다.간선 수 기준이며, 모든 간선은 양방향이다.모든 간선이 동일한 비용이기 때문에, BFS로 최단 거리를 구할 수 있다.각 노드까지의 최소 간선 수를 구한 뒤, 가장 큰 거리 값을 갖는 노드의 개수를 세면 된다.너무나도 자연스럽게 인접리스트는 무방향 그래프로 생성하고, 0-based index로 생성한다.adj = [[] for _ in range(n)]f..
[Level 3] 프로그래머스 - 스티커 모으기(2)
[Level 3] 프로그래머스 - 스티커 모으기(2)
2025.05.04https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이원형으로 배열된 스티커에서 서로 인접한 스티커 2개를 동시에 뜯을 수 없다.스티커를 뜯어서 점수를 얻는데, 최대로 얻을 수 있는 점수를 구하라일반 스티커 문제에서는 그냥 DP로 풀면되는데, 이 문제는 원형 배열을 사용하는 문제이다.즉, 첫 번째와 마지막 스티커가 서로 인접한다.그래서 둘 중 하나만 고를 수 있다.케이스를 나눠서 생각해야한다.케이스 1첫번째 스티커를 선택하는 경우이 경우 마지막 스티커는 절대 선택할 수 없다.즉 사용 가능한 범위..
[브론즈 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..