코딩테스트/백준12 [백준] 2573번 - 빙산 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석📌 문제 개요이 문제는 지구 온난화로 인해 빙산이 해마다 녹는 현상을 시뮬레이션하고, 빙산이 두 덩어리 이상으로 분리되는 최초 시점(년수) 을 구하는 문제입니다.🎯 요구사항빙산은 2차원 배열로 주어지며, 0은 바다, 1~10은 빙산의 높이를 의미합니다.매년, 각 빙산 칸은 상하좌우에 접한 바다(0)의 수만큼 높이가 감소합니다.빙산의 높이는 0 이하로 내려갈 수 없습니다.매년 시뮬레이션을 진행하면서 빙산 덩어리의 개수를 세고, 2개 이상으로 나뉘는 첫 해를 출력해야 합니다.만약 빙산이 전부 다 녹을 때까지 분리되지 않으면 0을 출력합니다.📈 입력 크기 및 제약3 ≤ N, M ≤ 300빙산 칸 수 ≤ 10,000시간 복잡도는 연산이 해마다 반복되므로, 연산당 O(NM) 이내여야 .. 2025. 5. 9. [백준] 1629번 - 곱셈 문제 풀이 및 코드 해석 (Python) 1. 문제 분석📌 문제 개요A^B mod C를 빠르게 계산하는 문제B가 최대 2,147,483,647이므로 직접 계산하면 시간 초과 발생거듭제곱을 O(log B)로 최적화해야 한다!🎯 요구사항거듭제곱을 빠르게 계산해야 한다.큰 수 연산을 방지하기 위해 매 연산마다 mod C를 적용해야 한다.반복문 또는 재귀를 활용하여 효율적으로 구현해야 한다.2. 해결 방법🔹 핵심 개념분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring)O(B)가 아니라 O(log B)로 거듭제곱을 구하는 방법재귀적으로 B를 절반으로 나누어 계산🔑 해결 절차거듭제곱 분할 정복A^B mod C를 직접 계산하지 않고 재귀적으로 반으로 나눠서 계산B가 짝수일 때와 홀수일 때를 구분하여 처리매 연산마다 mod .. 2025. 3. 7. [백준] 11403번 - 경로 찾기 문제 풀이 및 코드 해석 (Python) 1. 문제 분석📌 문제 개요가중치 없는 방향 그래프 G가 주어질 때, 모든 정점 (i, j)에 대해 경로가 있는지 확인해야 한다. i에서 j로 이동 가능한 경우 1, 불가능한 경우 0을 출력해야 한다. 입력으로 주어지는 인접 행렬을 기반으로 탐색을 진행한다. 🎯 요구사항i에서 j로 가는 경로가 있는지 확인해야 한다. 모든 정점 쌍 (i, j)에 대해 확인해야 한다. 인접 행렬 형식으로 출력해야 한다. 2. 해결 방법🔹 핵심 개념모든 정점 쌍 (i, j)에 대해 경로를 확인하는 문제 → 플로이드-워셜(Floyd-Warshall) 알고리즘 활용! 플로이드-워셜 알고리즘은 모든 노드 간 최단 경로를 구하는 알고리즘으로, O(N^3)의 시간 복잡도를 가진다. N ≤ 100이므로 최대 연산 횟.. 2025. 3. 7. [백준] 1655번 - 가운데를 말해요 문제 풀이 및 코드 해석 (Python) 1. 문제 분석📌 문제 개요숫자가 순차적으로 입력되며, 매 순간마다 중간값을 출력해야 한다. 입력된 숫자의 개수가 짝수라면 두 수 중 작은 수를 출력해야 한다. 정렬을 수행하면 O(N log N)이 걸리므로, Heap을 이용하여 O(log N)으로 해결해야 한다. 🎯 요구사항매 순간마다 중간값을 빠르게 찾아야 한다. 정렬된 상태를 유지하면서도 효율적으로 삽입이 가능해야 한다. 중간값을 즉시 출력해야 한다. 2. 해결 방법🔹 핵심 개념"중간값을 빠르게 찾는 문제" → Heap(우선순위 큐) 활용! 두 개의 힙(Heap)을 활용하여 정렬된 상태를 유지하면서 중간값을 찾는다. Python의 heapq는 기본적으로 최소 힙(Min-Heap)이므로, 최대 힙을 만들기 위해 음수 값을 저장한다... 2025. 3. 7. [백준] 7576번 - 토마토 문제 풀이 및 코드 해석 (Java) 문제 링크1. 문제 분석📌 문제 개요M x N 크기의 상자에 익은 토마토(1), 익지 않은 토마토(0), 빈 칸(-1)이 있다.익은 토마토는 인접한 네 방향(상, 하, 좌, 우)으로 익지 않은 토마토를 하루에 한 번 익게 만든다.모든 토마토가 익을 때까지 걸리는 최소 일수를 구해야 한다.익지 않은 토마토가 존재하지만 익을 수 없는 경우에는 -1을 출력한다.모든 토마토가 이미 익어 있다면 0을 출력한다.🎯 요구사항BFS(너비 우선 탐색) 을 활용하여 최소 일수를 구해야 한다.익은 토마토에서 BFS를 시작하여 인접한 익지 않은 토마토를 익게 만든다.익지 않은 토마토가 남아 있다면 -1을 출력해야 한다.2. 해결 방법🔹 핵심 개념BFS(너비 우선 탐색) 을 이용하여 최소 거리를 구하는 전형적인 문제여러 .. 2025. 2. 28. [백준] 11286번 - 절댓값 힙 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석📌 문제 개요절댓값 힙은 절댓값이 작은 순서대로 값을 정렬하는 힙(우선순위 큐)이다.만약 절댓값이 동일하다면 값이 작은 수가 우선순위를 갖는다.이 힙을 이용해 주어진 연산을 수행하는 프로그램을 작성해야 한다.🎯 요구사항정수 x를 힙에 추가 (x ≠ 0일 경우)절댓값이 가장 작은 값 출력 & 삭제 (x == 0일 경우)같은 절댓값을 가진 값이 여러 개일 경우, 값이 작은 수를 먼저 출력힙이 비어 있다면 0을 출력N의 최대 크기가 100,000이므로 O(log N) 이하의 연산 속도가 필요하다.2. 해결 방법🔹 핵심 개념우선순위 큐(Priority Queue) 를 활용하여 데이터를 정렬하고 관리할 수 있다.우선순위 큐에서 커스텀 정렬을 적용하여, 절댓값이 작은 순서 + 값이 작은.. 2025. 2. 27. 이전 1 2 다음
