쉽게 쉽게

script.js 에 별도 등록하세요. (티스토리가 서식 내 태그를 자동 삭제합니다) ================================================ -->📌 핵심 요약DFS(깊이 우선 탐색)는 한 방향으로 갈 수 있는 만큼 끝까지 파고든 뒤, 막히면 되돌아와 다른 길을 탐색하는 알고리즘입니다.“되돌아오기”를 구현하기 위해 스택(Stack) 또는 재귀 호출을 사용하며, 실전에서는 재귀 방식이 훨씬 간결합니다.최단 거리는 보장하지 않지만, 연결 요소 찾기 · 모든 경로 탐색 · 백트래킹의 기반이 되는 필수 알고리즘입니다.백준 11724(연결 요소의 개수), 2667(단지번호붙이기) 두 문제로 그래프 DFS와 2차원 격자 DFS를 직접 풀어봅니다. 목차1 DFS(깊..

script.js 에 별도 등록하세요. (티스토리가 서식 내 태그를 자동 삭제합니다) ================================================ -->📌 핵심 요약BFS(너비 우선 탐색)는 시작점에서 가까운 곳부터 차례대로 퍼져나가며 탐색하는 알고리즘입니다.탐색 순서를 관리하기 위해 큐(Queue) 자료구조를 사용하며, 먼저 발견한 노드를 먼저 방문합니다.모든 간선의 비용이 같을 때(가중치가 없을 때) 최단 거리를 보장하는 것이 BFS의 가장 큰 강점입니다.백준 2606(바이러스), 2178(미로 탐색) 두 문제로 연결 요소 탐색과 최단 거리 계산을 직접 풀어봅니다. 목차1 BFS(너비 우선 탐색)란?BFS(Breadth-First Search, 너비 우선..

📌 핵심 요약각 P에서 BFS를 시작 — 맨해튼 거리 2 이내에 다른 P가 있는지 확인한다X는 벽으로 처리 — 파티션으로 막힌 경로는 큐에 넣지 않으므로 자연스럽게 걸러진다거리 2에서 확장 중단 — dis == 2인 노드는 검사만 하고 이웃을 큐에 넣지 않는다 목차Programmers #81302거리두기 확인하기5×5 대기실 5개 · P(응시자) / O(빈 자리) / X(파티션)난이도: Lv.25×5 크기의 대기실 5개가 주어진다. 응시자들이 앉은 자리(P) 사이의 맨해튼 거리가 2 이하이면 거리두기 위반인데, 예외적으로 두 자리 사이가 파티션(X)으로 막혀 있으면 위반이 아니다. 각 대기실이 거리두기를 지키고 있으면 1, 아니면 0을 배열에 담아 반환한다.풀이 과정대기실 5개를 각각 독립적으로 검사한..

📌 핵심 요약StringTokenizer는 문자열을 구분자 기준으로 잘라주는 클래스 — 정규식을 쓰지 않아 split()보다 단순하고 빠르다세 번째 인자를 true로 주면 구분자도 토큰으로 반환 — 수식 파싱처럼 구분자 자체가 필요한 경우에 유용하다빈 토큰은 무시된다 — 구분자가 연속으로 나올 때 split()과 결과가 달라지므로 주의 목차1 StringTokenizer란?java.util.StringTokenizer는 문자열을 구분자(delimiter) 기준으로 잘라 토큰 단위로 꺼내 쓸 수 있게 해주는 클래스다. 문자열을 한 번에 배열로 바꾸는 split()과 달리, hasMoreTokens()로 남은 토큰이 있는지 확인하면서 nextToken()으로 하나씩 꺼내는 방식으로 동작한다.왜 사용하는가?..

📌 핵심 요약완전탐색 — 연산자 3개의 우선순위 순열은 6가지뿐이라 전부 시도해도 충분하다토큰 리스트 축약 — 우선순위가 높은 연산자부터 찾아 [숫자, 연산자, 숫자] 세 토큰을 결과 하나로 접는다인덱스 보정 — 리스트를 순회하면서 동시에 수정할 때는 줄어든 크기만큼 인덱스를 되돌려야 한다 목차1 문제 이해Programmers #67257수식 최대화expression 길이 ≤ 100 · 피연산자는 3자리 이하난이도: Lv.2+, -, * 세 연산자로 이루어진 수식이 주어진다. 연산자 우선순위를 마음대로 재정의할 수 있을 때(단, 우선순위가 같은 연산자는 없음), 수식 결과의 절댓값이 최대가 되는 값을 구하는 문제다.풀이 과정수식을 숫자와 연산자 토큰으로 분리한다우선순위 순열 6가지를 하나씩 시도한다각 ..

📌 핵심 요약연결 요소별 합계 — 격자에서 상하좌우로 이어진 육지(섬)를 BFS로 묶고, 섬마다 식량의 합을 구하는 문제입니다.거리 BFS vs 집계 BFS — 미로 탈출처럼 거리를 구할 땐 큐에 {r, c, day}를 싣지만, 이 문제는 탐색 밖의 변수 하나에 누적하면 충분합니다. 목차1 문제 소개Programmers #154540무인도 여행지도 최대 100×100 · 각 칸은 X 또는 1~9난이도: Lv.2문자열 배열로 주어지는 지도에서 X는 바다, 숫자는 그 칸에서 얻을 수 있는 식량입니다. 상하좌우로 연결된 숫자 칸들이 하나의 무인도를 이룰 때, 각 섬에서 얻을 수 있는 식량의 총합을 오름차순으로 반환해야 합니다. 섬이 하나도 없으면 {-1}을 반환합니다.풀이 과정문자열 배열을 char[][] ..

📌 핵심 요약무적권은 소급 적용이 가능하다 — "언제 쓸지" 미리 결정하지 말고, 병사가 부족해진 순간 지금까지 가장 병사를 많이 쓴 라운드에 쓴 셈 치면 된다.최대 힙(PriorityQueue)으로 최댓값 관리 — 매 라운드 적의 수를 힙에 넣어두면, 소급 적용할 최적의 라운드를 poll() 한 번(O(log N))으로 찾을 수 있다.검증 후 카운트 — answer++는 그 라운드를 실제로 막아냈다는 검증이 끝난 뒤에 실행해야 실패한 라운드가 세어지지 않는다. 목차1 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/142085Programmers #142085디펜스 게임n ≤ 10⁹ · k ≤ 500,000 · enemy ≤ 1,000,..

📌 핵심 요약경유지 최단거리 분해 — "S에서 E로 가되 반드시 L을 거쳐야 한다"는 조건은 S→L 최단거리 + L→E 최단거리로 쪼갤 수 있다. 경유지가 고정이면 두 BFS 결과를 독립적으로 합쳐도 최단이 보장된다.BFS는 target 문자만 알면 된다 — 목표 좌표를 미리 저장할 필요 없이, 탐색 중 처음 만난 target까지의 거리가 곧 최단거리다. 목차1 문제 분석Programmers #159993미로 탈출5 ≤ 세로 · 가로 ≤ 100 · Lv.2난이도: Level 2S(시작점)에서 출발해 E(출구)로 탈출해야 한다. 단, 출구는 잠겨 있어서 반드시 L(레버)을 먼저 당겨야 열린다. X는 벽이라 지나갈 수 없고, 한 칸 이동에 1초가 걸린다. 탈출까지 걸리는 최소 시간을 구하고, 탈출할 수 없..

script.js 에 별도 등록하세요. ================================================ -->📌 핵심 요약투 포인터로 O(N) 풀이 — 수열 길이가 최대 100만이라 O(N²) 완전 탐색은 시간 초과. left/right 두 포인터로 윈도우를 늘렸다 줄였다 하며 한 번만 훑습니다.성립 근거는 단조성 — 모든 원소가 1 이상(양수)이라 right를 밀면 합이 반드시 커지고 left를 밀면 반드시 작아집니다. 이 성질 덕분에 각 상황에서 취할 행동이 하나로 정해집니다.동점 처리는 부등호 하나로 — "길이가 같으면 시작 인덱스가 작은 것" 조건은 탐색 방향(왼쪽→오른쪽)과 엄격한 부등호()의 조합으로 자연스럽게 해결됩니다. 목차1 문제 소개Programmers #1..

📌 핵심 요약트리의 성질 — 노드 n개, 간선 n-1개면 트리. 간선 하나를 끊으면 정확히 두 개의 컴포넌트로 갈라진다.완전탐색으로 충분 — n ≤ 100이라 간선 99개를 전부 끊어봐도 여유롭게 통과한다. 그리디하게 고민할 필요가 없다.한쪽만 세면 끝 — 한쪽 크기가 count면 반대쪽은 n - count. 차이는 Math.abs(count - (n - count)).트리라서 가능한 단순화 — 간선을 끊는 대신 반대편 노드 하나를 차단하는 것으로 같은 효과를 낼 수 있다. 목차1 문제 소개Programmers #86971전력망을 둘로 나누기2 ≤ n ≤ 100 · 간선 n-1개난이도: Lv.2n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다. 전선 중 하나를 끊어 전력망을 2개로 분할하려..