전체 글25 [백준] 2573번 - 빙산 풀이 및 코드 분석 (Java) 문제 링크1. 문제 분석📌 문제 개요이 문제는 지구 온난화로 인해 빙산이 해마다 녹는 현상을 시뮬레이션하고, 빙산이 두 덩어리 이상으로 분리되는 최초 시점(년수) 을 구하는 문제입니다.🎯 요구사항빙산은 2차원 배열로 주어지며, 0은 바다, 1~10은 빙산의 높이를 의미합니다.매년, 각 빙산 칸은 상하좌우에 접한 바다(0)의 수만큼 높이가 감소합니다.빙산의 높이는 0 이하로 내려갈 수 없습니다.매년 시뮬레이션을 진행하면서 빙산 덩어리의 개수를 세고, 2개 이상으로 나뉘는 첫 해를 출력해야 합니다.만약 빙산이 전부 다 녹을 때까지 분리되지 않으면 0을 출력합니다.📈 입력 크기 및 제약3 ≤ N, M ≤ 300빙산 칸 수 ≤ 10,000시간 복잡도는 연산이 해마다 반복되므로, 연산당 O(NM) 이내여야 .. 2025. 5. 9. [프로그래머스] k진수에서 소수 개수 구하기 문제 링크1. 문제 분석주어진 n을 k진법으로 변환한 후, 연속된 0으로 둘러싸여 있거나 독립적으로 존재하는 소수의 개수를 찾는 문제입니다.즉, k진법 변환과 소수 판별을 수행해야 합니다.주요 고려 사항n을 k진법으로 변환n을 k로 나눈 나머지를 저장하면서 변환 수행변환된 문자열에서 0을 기준으로 나누어 소수 후보 추출연속된 0 사이에 있는 숫자들을 저장각 숫자가 소수인지 판별1이 포함된 경우는 소수에서 제외해야 함소수 판별을 효율적으로 수행해야 함 (에라토스테네스의 체 또는 제곱근까지만 확인)2. 해결 방법k진법 변환n을 k로 나눈 나머지를 Deque에 저장마지막에 pollLast()로 하나씩 꺼내면서 변환된 숫자를 만듦0을 기준으로 숫자 분리0P0, P0, 0P, P 형태의 숫자 추출0을 만나면 현재.. 2025. 3. 20. [프로그래머스] 두 큐 합 같게 만들기 풀이 및 코드 분석 문제 링크1. 문제 분석두 개의 큐가 주어지고, 한 큐에서 원소를 빼서 다른 큐에 추가하는 방식으로 두 큐의 원소 합을 같게 만들고자 한다. 최소 작업 횟수를 구하는 것이 목표이며, 어떤 방법으로도 같게 만들 수 없다면 -1을 반환해야 한다.핵심 포인트총합이 홀수이면 불가능두 큐의 원소 합이 홀수이면 절대 같은 값으로 만들 수 없다.투 포인터 (Two Pointers) 활용큐의 원소를 이동하며 합을 맞추는 방식이므로, 투 포인터 또는 슬라이딩 윈도우 기법을 활용할 수 있다.최대 이동 횟수 제한한 큐의 길이가 n일 때, 최악의 경우 3 * n번의 이동 내에서 해결할 수 있어야 한다.2. 해결 방법초기 설정두 큐의 합을 각각 계산한다.sum1, sum2의 합이 홀수이면 -1 반환.두 큐를 LinkedList.. 2025. 3. 20. [프로그래머스] 택배 배달과 수거하기 풀이 및 코드 분석 문제 링크1. 문제 분석📌 문제 개요택배 트럭이 여러 집을 방문하여 택배를 배달하고 빈 택배 상자를 수거해야 한다.트럭은 최대 cap개의 택배만 실을 수 있으며, 모든 집을 방문한 뒤 물류창고로 돌아와야 한다. 🚩 목표:모든 배달과 수거를 완료하는 데 필요한 최소 이동 거리를 계산하기.📌 문제의 제약 조건배달과 수거를 동시에 진행 가능.한 번에 최대 cap개의 택배만 실을 수 있음.deliveries[i]: i+1번 집에 배달해야 하는 택배 수pickups[i]: i+1번 집에서 수거해야 하는 빈 택배 수n ≤ 100,000 이므로 O(N^2) 이상의 시간 복잡도는 비효율적.2. 해결 방법🔹 그리디 (Greedy) 알고리즘 활용핵심 아이디어:가장 먼 집부터 배달 및 수거를 처리하면 불필요한 이동을.. 2025. 3. 20. [프로그래머스] 이모티콘 할인행사 풀이 및 코드 분석 문제 링크1. 문제 분석📌 문제 개요각 이모티콘에 대해 할인율(10%, 20%, 30%, 40%)을 결정해야 함모든 사용자가 특정 할인율 이상의 이모티콘을 구매하며, 특정 금액 이상 사용하면 이모티콘 플러스에 가입목표:이모티콘 플러스 가입자를 최대로 늘리기이모티콘 판매 수익을 최대로 늘리기2. 해결 방법🔹 완전 탐색 (백트래킹)이모티콘 개수 E가 최대 7개로 적기 때문에, 4^E(= 4^7 = 16384) 경우의 수를 탐색해도 무리가 없음.각 이모티콘이 가질 수 있는 할인율 (10%, 20%, 30%, 40%) 중 하나를 선택하는 모든 경우의 수를 확인백트래킹을 사용하여 가지치기하면서 탐색 진행3. 코드 구현 (Java)class Solution { static int U, E; stati.. 2025. 3. 20. [프로그래머스] 도넛과 막대 그래프 풀이 및 코드 분석 문제 링크1. 문제 분석📌 문제 개요주어진 단방향 그래프에서 다음 요소를 찾아야 한다:생성된 정점 (모든 그래프의 진입점)도넛 모양 그래프 개수 (순환)막대 모양 그래프 개수 (끝점이 하나 있는 트리 구조)8자 모양 그래프 개수 (두 개의 도넛이 연결된 구조)2. 해결 방법🔹 그래프 구성 및 특성edges를 이용하여 각 노드의 진입 차수 (in-degree)와 진출 차수 (out-degree)를 계산생성된 정점 찾기:out-degree >= 2이고 in-degree == 0인 노드 (다른 노드에서 진입하지 않고, 여러 노드로 나가는 노드)🔑 그래프 분류도넛 모양 그래프: 모든 노드의 in-degree == 1 및 out-degree == 1 (즉, 사이클)막대 모양 그래프: in-degree == .. 2025. 3. 20. 이전 1 2 3 4 5 다음
