Gom3rye

언제 '새 배열'을 만들고, 언제 '좌표 집합'만 쓸까?이 두 방식을 구별하는 기준은 "데이터의 밀도"와 "참조 방식"에 있다.A. 매 단계 '새 배열' 생성이 유리한 경우 (밀도가 높을 때)상태 전파: 한 칸의 변화가 주변 칸에 연쇄적으로 영향을 줄 때 (예: 모래바람, 불 번지기, 물 시뮬레이션)주변 참조: board[i][j]의 다음 값이 board[i-1][j], board[i+1][j] 등 주변 8칸의 모든 상태에 의존할 때객체가 꽉 찼을 때: 보드의 거의 모든 칸에 데이터가 들어있어서 좌표만 따로 관리하는 게 더 메모리를 많이 먹을 때B. '좌표 집합(Set/Dict)'만 관리해도 되는 경우 (밀도가 낮을 때)독립적 이동: 객체들이 서로의 상태를 실시간으로 참조하지 않고, 각자 자기 갈 길을 ..

🔹 DP / Stack의 본질과거에서부터 일직선으로 작동한다.무슨 의미냐 하면은DP상태가 dp[i] → dp[i+1]로 단방향한 번 계산된 과거 상태는 되돌리지 않음과거 선택이 “최선”이라는 전제 하에 누적👉 그래서✔ “지금 선택이 나중에 틀릴 수 있는 문제”에는 부적합Stack가장 최근 선택만 취소 가능 (LIFO)“조건 위반 시, 방금 넣은 것만 제거” 가능임의의 과거 선택 제거 불가능👉 백준) 컵라면 문제에서:제거해야 할 건 “가장 컵라면 적은 문제”이게 꼭 마지막에 넣은 것이 아니다 ❌🔹 Heap(우선순위 큐)의 본질우선순위 기준으로 과거 선택을 언제든지 되돌릴 수 있다 이게 힙의 핵심 능력 🔥힙은 시간 순서가 아니라 가치 순서로 관리따라서 과거에 “최선처럼 보였던 선택”도 더 좋은 선택..

아래 조건 중 3개 이상 맞으면 거의 확정1️⃣ “연속한 구간(부분 수열)”이라는 말이 있는가?투 포인터의 절대적 전제 조건✔ 연속한✔ 부분 수열✔ subarray✔ 구간 [L, R]❌ 순열, 조합, 임의 선택 → 투 포인터 아님2️⃣ 구간에 대한 “조건”이 단조적인가?🔑 단조성(monotonicity)이 핵심오른쪽을 늘리면 조건이 점점 나빠지거나 / 좋아지거나예시조건단조성합 ≤ Kright ↑ → 합 ↑중복 없음right ↑ → 중복 가능성 ↑서로 다른 수 개수 ≤ Kright ↑ → 개수 ↑최대 − 최소 ≤ Kright ↑ → 차이 ↑👉 조건이 깨지면 left를 움직여 회복 가능3️⃣ “최대 / 최소 / 개수”를 묻는가?투 포인터의 전형적인 질문들:✔ 가능한 최대 길이✔ 가능한 최소 길이✔ 조건을..

🔥 핵심 한 줄 요약heapq는 “여러 후보 중 최선 1개를 계속 고르는 문제”stack은 “앞에서 한 선택을 뒤에서 취소해야 하는 문제”이 한 줄을 기준으로 보면 대부분 문제가 정리된다.1️⃣ heapq 문제회의실 배정동시에 열리는 회의의 최대 개수또는 필요한 최소 회의실 수📌 이 문제에서 우리가 반복하는 질문“지금 시작하는 회의가 기존 회의 중 가장 빨리 끝나는 회의를 재사용할 수 있는가?”👉 매 순간 여러 회의 중 ‘가장 빨리 끝나는 회의 1개’만 중요📌 그래서 heapq가 딱 맞음q에는 현재 진행 중인 회의들의 종료 시간q[0] = 가장 빨리 끝나는 회의그 하나만 보면 됨 ❗for start, end in info: if q and q[0] 📌 과거 선택을 취소하지 않음이미 시작..

🎯 Union-Find를 떠올려야 하는 신호(패턴)아래 상황 중 하나라도 보이면 무조건 Union-Find부터 의심해야 해.✔ 1) "합치기(union) / 묶기 / 연결하기 / 같은 그룹"이라는 표현이 나올 때예:친구 관계(Friend Network)SNS 팔로우 묶기같은 팀 만들기섬/영역/구역을 하나로 합치기사람/도형/원소들을 같은 집합으로 묶기✔ 2) 결과가 "그룹 크기" 또는 "연결 요소 개수"일 때“현재 속한 네트워크의 인원 출력”“몇 개의 영역이 생기는가?”“그룹별 개수는?”“분리된 구역은?”✔ 3) 서로 겹치거나 닿는 기하학 도형(선분, 원, 직사각형) 문제이 문제도 여기에 해당됨.유형 예:원 1억 개 → 겹치는 원들을 하나의 영역으로 묶기직사각형이 맞닿는지 파악하기 → 묶기점/선분이 이어..

공통점은 전부 두 개의 증가하는 포인터로 어떤 조건을 만족하는 두 수(또는 구간)를 찾는 형태라는 점!🔥 1. 차이(difference)가 특정 값이 되는 두 수 찾기대표 문제: “수열에서 |A[j] – A[i]| = K 되는 쌍 찾기”정렬된 배열에서diff diff > K → left 증가diff == K → 정답 처리 후 right 증가딱 이 문제 다이어트 문제 구현과 동일 패턴🔥 2. 두 수의 합이 특정 값이 되는 pair 찾기 (Two-Sum sorted)예시: BOJ 3273 두 수의 합sum sum > target → right--sum == target → answer++이 문제는 하나는 증가, 하나는 감소지만“조건 비교를 통한 포인터 이동”이라는 패턴은 동일.🔥 3. 두 수의 합이 특..