[Baekjoon] 1006 – 습격자 초라기
📖 문제 이해하기 이 문제는 도넛 모양의 건물에 배치된 적들을 효율적으로 제압하기 위한 최소 특수소대 개수를 구하는 문제입니다. 건물은 내부 원과 외부 원으로 이루어진 이중 원형 구조이며, 각 원은 N개의 구역으로 나뉘어 총 2N개의 구역이 존재합니다. 특수소대는 W명으로 구성되며, 한 구역만 점령하거나 인접한 두 구역을 함께 점령할 수 있습니다. 여기서 인접이란 같은 경계를 공유하는 구역을…
[Baekjoon] 1734 – 교통체계
📖 문제 이해하기 이 문제는 그래프 이론에서 핵심적인 개념인 절단점(Articulation Point)과 브리지(Bridge)를 활용하여 그래프의 연결성을 판단하는 문제입니다. 문제에서는 N개의 도시와 E개의 양방향 도로로 이루어진 연결된 그래프가 주어집니다. 우리는 두 가지 유형의 질문에 답해야 합니다: 예를 들어, 도시 1-2-3-4가 일직선으로 연결된 그래프에서 도시 2와 3을 잇는 도로를 제거하면, 도시 1에서 도시 4로 갈 수 없게 됩니다….
[Baekjoon] 10891 – Cactus? Not cactus?
📖 문제 이해하기 선인장(Cactus) 그래프는 그래프 이론에서 특별한 성질을 가진 연결 그래프입니다. 핵심은 각 정점이 최대 하나의 단순 사이클에만 속할 수 있다는 제약입니다. 다시 말해, 어떤 정점도 두 개 이상의 서로 다른 사이클의 일부가 될 수 없습니다. 예를 들어, 정점이 4개이고 간선이 (1,2), (2,3), (3,4), (4,1)인 그래프를 생각해보겠습니다. 이는 하나의 사이클 1→2→3→4→1을 형성하며, 각 정점은…
[Baekjoon] 11400 – 단절선
📖 문제 이해하기 단절선 문제는 주어진 그래프에서 “제거했을 때 연결 요소의 개수가 증가하는 간선”을 모두 찾는 문제입니다. 쉽게 말해, 어떤 다리를 끊었을 때 원래 하나였던 섬이 두 개로 분리되는 그 다리를 찾는 것입니다. 예를 들어, 정점 5개와 간선 5개로 구성된 그래프가 있다고 해봅시다: 1-2, 2-3, 3-4, 3-5, 4-5. 여기서 간선 1-2나 2-3을 제거하면 그래프가 두…
2338. Count the Number of Ideal Arrays
https://leetcode.com/problems/count-the-number-of-ideal-arrays/description 📖 문제 해석 길이가 n인 0‑인덱스 배열 arr가 “이상적(ideal)”이려면 두 가지 조건을 만족해야 합니다. 우리가 구해야 하는 것은 가능한 서로 다른 이상적 배열의 개수이며, 결과는 1_000_000_007으로 나눈 나머지입니다. 간단한 예로 n = 3, maxValue = 4를 생각해 보면, 제약을 보면 n과 maxValue 모두 최대 10<sup>4</sup>로, 단순 완전탐색은 불가능합니다. 🧠 첫 시도와 그 한계 가장…
[Baekjoon] 2568 – 전깃줄 2
https://www.acmicpc.net/problem/2568 전깃줄이 서로 엉켜있는 모습을 상상해보세요. 두 전봇대 사이에 여러 개의 전깃줄이 연결되어 있는데, 일부는 서로 교차하여 합선의 위험을 만들고 있습니다. 이 문제는 교차하는 전깃줄들 중 최소한의 개수만 제거하여 나머지 전깃줄들이 모두 평행하게 만드는 것이 목표입니다. 문제를 좀 더 구체적으로 살펴보면, 각 전깃줄은 A 전봇대의 특정 위치와 B 전봇대의 특정 위치를 연결합니다. 예를 들어 A의…
[Baekjoon] 5373 – 큐빙
https://www.acmicpc.net/problem/5373 📖 문제 이해하기 이 문제는 루빅스 큐브의 회전 동작을 정확히 시뮬레이션하는 것입니다. 우리에게는 완전히 풀린 상태의 3×3×3 루빅스 큐브가 주어지고, 일련의 회전 명령어들을 순서대로 적용한 후 최종적으로 윗면의 색상 배치를 출력해야 합니다. 초기 상태에서 각 면의 색상은 다음과 같이 정해져 있습니다. 윗면(U)은 흰색(w), 아랫면(D)은 노란색(y), 앞면(F)은 빨간색(r), 뒷면(B)은 오렌지색(o), 왼쪽면(L)은 초록색(g), 오른쪽면(R)은 파란색(b)입니다. 각…
[Baekjoon] 2243 – 사탕상자
https://www.acmicpc.net/problem/2243 📖 문제 해석하기 이 문제는 동적으로 변화하는 사탕상자에서 순위 기반 조회를 효율적으로 수행하는 문제입니다. 수정이는 사탕상자에 사탕을 넣거나 빼면서, 동시에 “몇 번째로 맛있는 사탕”을 꺼내야 합니다. 구체적으로 살펴보면, 각 사탕은 1부터 1,000,000까지의 맛 점수를 가지며(1이 가장 맛있음), 우리는 다음 두 가지 연산을 처리해야 합니다: 예를 들어, 사탕상자에 맛 점수가 [3, 3, 5, 7, 7,…
[Baekjoon] 10999 – 구간 합 구하기 2
https://www.acmicpc.net/problem/10999 📖 문제 해석 이 문제는 배열에서 두 가지 연산을 효율적으로 처리해야 하는 상황을 다룹니다. 첫째는 특정 구간의 모든 원소에 동일한 값을 더하는 구간 업데이트이고, 둘째는 특정 구간의 원소들의 합을 구하는 구간 합 쿼리입니다. 예시를 통해 살펴보겠습니다. 배열 [1, 2, 3, 4, 5]가 있을 때, “3번째부터 4번째 원소에 6을 더하라”는 명령을 받으면 배열은 [1, 2,…
버스 노선으로 최단 경로 찾기: 그래프 변환의 힘
📖 문제 이해하기 이 문제는 복잡한 버스 시스템에서 최소한의 환승으로 목적지에 도달하는 방법을 찾는 것입니다. 각 버스는 정해진 노선을 무한히 반복하며, 우리는 출발지에서 목적지까지 가는데 필요한 최소 버스 수를 구해야 합니다. 예를 들어, routes = [[1,2,7],[3,6,7]]이고 source = 1, target = 6인 경우를 생각해봅시다. 첫 번째 버스는 1→2→7→1→2→7… 순서로 운행하고, 두 번째 버스는 3→6→7→3→6→7… 순서로…