안녕하세요.오늘은 [백준] 15693번 : 거짓말 문제를 풀어보도록 하겠습니다.📌 접근 이 문제는 모든 CCTV가 바라보는 방향의 조합을 완전 탐색(Brute Force) 으로 시도해,사각지대(감시되지 않는 영역) 의 개수를 최소화하는 문제입니다. 1. CCTV 방향 조합 정의CCTV는 번호(1~5)에 따라 감시 가능한 방향이 다릅니다.각 CCTV가 감시할 수 있는 방향의 조합을 2진수 문자열(“상우하좌”) 형태로 정의했습니다.예를 들어,"0001" → 왼쪽만 감시"0110" → 오른쪽과 아래 감시"1111" → 네 방향 모두 감시 (5번 CCTV)이렇게 CCTV별 가능한 조합을 미리 선언해두면,각 CCTV마다 가능한 회전 방향을 순회하며 탐색할 수 있습니다. 2. 방향 이동 정의상하좌우 네 방..

안녕하세요.오늘은 [백준] 15681: 트리와 쿼리 문제를 풀며 TLE을 경험했습니다...이번 글에서는 정답코드와 시간초과 코드의 시간복잡도를 분석하고 왜 최적화가 필요했는지 알아보겠습니다. 🤔 고민했던 점 & 어려웠던 부분처음 접근 방법은 다음과 같았습니다.1. 문제에서 정해진 루트(R)을 기준으로 DFS 탐색하여 부모 정보를 기록한다.2. 쿼리마다 DFS 탐색하여 서브트리의 크기를 계산한다.// hyebleeimport java.util.*;import java.io.*;public class Main { // 정점 n, 루트 r, 쿼리 수 q // 간선 정보 (n-1개) -> 트리니까 단방향으로 연결해야함. // 쿼리의 루트노트 q개 public static List..

안녕하세요.오늘은 14502번: 연구소 문제를 풀어보도록 하겠습니다.요즘 목표 중 하나가 깃허브에 멋지게 플레티넘 티어를 달아두는 건데요. . .그래서 다시 코드트리에서 백준으로 넘어와 문제를 풀고 있습니다. 특히 BFS 문제는 알고리즘에서 가장 빈번하게 출제되는 유형 중 하나라 꼭 잡고 가야 한다고 생각했습니다.이번에 다룬 연구소(14502) 문제는 전형적인 완전탐색 + 시뮬레이션 + DFS 유형이라 복습하기에 적합했습니다. 📌 접근저는 이 문제를 크게 3가지 단계로 나눴습니다. 1. 빈 칸 3곳을 선택해 벽 세우기 (buildWall)2. 바이러스 퍼뜨리기 (spreadVirus)3. 안전 영역 카운팅 (getSafeArea) 💻 풀이// hyebleeimport java.util.*;impo..

안녕하세요.오늘은 [백준] 14889번 : 스타트와 링크 문제를 풀어보도록 하겠습니다. 📌 접근1. 팀 나누기 - 조합 탐색사람들을 두 팀으로 나누는 모든 조합을 탐색해야 합니다.단, [start: 1, 2], [link: 3, 4] 와 [start: 3, 4], [link: 1, 2] 는 사실상 같은 조합입니다.그래서 0번째 사람은 항상 start팀에 포함시키도록 고정하면 불필요한 연산을 절반으로 줄일 수 있습니다.2. 능력치 차이 계산조합이 완성되면, 두 팀의 능력치를 구합니다.팀의 구성원 쌍을 순회하며 arr[i][j] + arr[j][i]를 더합니다.차이가 최솟값이라면 갱신합니다. 💻 풀이// hyebleeimport java.util.*;import java.io.*;public class..

안녕하세요.오늘은 [백준] 1916 : 최소비용 구하기 문제를 풀어보도록 하겠습니다. 📌 접근다익스트라 알고리즘을 적용해서 풀이하면 됩니다. 다익스트라 알고리즘은,모든 가중치가 양수인 무방향 그래프에서 최소 비용을 구하는 문제에 적합합니다. 출발점에서 제일 가까운 노드를 먼저 탐색하며, 각 노드까지의 최소비용을 갱신합니다. 다익스트라는 항상 "가장 가까운 노드부터" 꺼내기 때문에, 한 번 꺼낸 노드는 그 시점에서의 거리가 최단 거리입니다. 다익스트라 알고리즘을 구현하기 위해서는 크게 4가지의 요소가 필요합니다.1. pq 사용이 가능한 Comparable을 구현한 노드2. 시작정점으로부터의 거리를 저장하는 dist 배열 (초기에 Integer.MAX_VALUE로 초기화 필수)3. 각 노드별 연결노드..

안녕하세요.오늘은 스티커 문제를 풀어보도록 하겠습니다. 📌 접근다이나믹 프로그래밍을 이용해서 풀어야합니다.점화식은 다음과 같이 세우면 됩니다.dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + cost[0][j];dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + cost[1][j]; 풀이를 위해서는,각 스티커의 비용을 저장하는 cost배열과해당 스티커를 뗐을 때 누적 최대 점수를 저장하는 dp배열가 필요합니다. dp[0][j] 구하기빨간색 스티커의 위치를 dp[0][j]라고 가정해봅시다.빨간색 스티커를 떼기 전에 가능한 case는 2가지 입니다. case1) 직전에 dp[1][j-1]을 뗀 경우 case2..