🚨 문제의 상황: IN은 되는데 NOT IN은 왜 안 될까?

-- 1. 정상 작동
WHERE ID IN (SELECT PARENT_ID FROM ECOLI_DATA)

-- 2. 결과가 아예 안 나옴 (Empty Set)
WHERE ID NOT IN (SELECT PARENT_ID FROM ECOLI_DATA)

서브쿼리 결과에 NULL이 포함되어 있을 때, 단지 NOT 하나만 붙였을 뿐인데 모든 데이터가 증발해 버린다. 일반적인 프로그래밍 언어의 2값 논리(True/False)로는 이해하기 힘든 이 현상의 원인을 파헤쳐 보자.

🔍 SQL의 3값 논리 (True, False, Unknown)

SQL에는 참과 거짓 외에 UNKNOWN(알 수 없음) 이라는 상태가 존재한다. NULL이 포함된 비교 연산(예: 1 = NULL, 1 != NULL)은 무조건 UNKNOWN을 반환한다.

1. IN 연산자의 내부 동작 (OR 연산)

IN (1, 2, NULL)은 내부적으로 OR로 풀린다.

• ID = 1 OR ID = 2 OR ID = NULL
• TRUE OR FALSE OR UNKNOWN $\rightarrow$ 최종 결과: TRUE
• 결론: OR 연산은 하나라도 참이면 전체가 참이므로, 일치하는 값이 있다면 NULL이 섞여 있어도 정상적으로 통과한다.

2. NOT IN 연산자의 내부 동작 (AND 연산)

NOT IN (1, 2, NULL)은 내부적으로 AND로 풀린다.

• ID != 1 AND ID != 2 AND ID != NULL
• TRUE AND TRUE AND UNKNOWN $\rightarrow$ 최종 결과: UNKNOWN
• 결론: AND 연산은 모두 참이어야 참이다. 하지만 ID != NULL이 UNKNOWN을 뱉어내기 때문에, 전체 논리식이 UNKNOWN이 되어버린다. WHERE 절은 오직 TRUE인 행만 통과시키므로, 서브쿼리에 NULL이 단 하나라도 있다면 모든 데이터가 필터링되어 사라진다.

🛠️ 해결 방안: NULL 지뢰 제거

이 함정을 피하는 가장 직관적인 방법은 서브쿼리 내부에서 원천적으로 NULL을 제거하는 것이다.

SELECT ID 
FROM TABLE_A
WHERE ID NOT IN (
    SELECT PARENT_ID 
    FROM ECOLI_DATA 
    WHERE PARENT_ID IS NOT NULL -- NULL 명시적 제거
)

[핵심 요약] 서브쿼리와 함께 NOT IN을 사용할 때는 기계적으로 "서브쿼리 결과에 NULL이 섞여 있지는 않은가?" 를 의심하고 방어 코드를 작성하는 습관을 들이자.

C++, Python, Java와 같은 언어에서는 for문으로 배열을 순회하며 if-else로 값을 변수에 대입하는 절차적(Imperative) 사고방식에 익숙해져 있다. 하지만 SQL은 데이터를 어떻게 처리할지 명시하는 것이 아니라, 결과적으로 무엇을 가져올지 선언하는 선언적(Declarative) 언어다.

따라서 원본 데이터를 변형하거나 변수에 값을 할당하는 대신, 전체 데이터 셋을 펼쳐놓고 조건에 맞는 새로운 파생 컬럼(Column)을 통째로 만들어낸다는 시각의 전환이 필요하다.

이번 글에서는 코딩테스트 SQL 문제에서 조건 분기를 처리할 때 반드시 알아야 할 3가지 핵심 무기를 해부해 본다.

1. 표준적이고 가장 강력한 무기: CASE WHEN

파이썬의 if - elif - else 구조를 SQL의 컬럼으로 투영해 내는 구문이다. 복잡한 다중 조건을 처리할 때 가장 많이 사용된다.

💡 기본 문법

CASE 
    WHEN 조건1 THEN 반환값1
    WHEN 조건2 THEN 반환값2
    ELSE 모든 조건에 맞지 않을 때 반환값 (생략 시 NULL)
END AS 새로운_컬럼명

🔍 구조 파헤치기: END와 AS의 역할

• END (필수): CASE 문의 끝을 알리는 '닫는 괄호' 역할을 한다. 프로그래밍 언어에서 if { ... }의 닫는 중괄호(})와 같다. END가 없으면 문법 에러가 발생한다.
• AS 새로운_컬럼명 (선택이나 필수 권장): AS는 계산된 결과가 들어갈 컬럼의 이름(별칭, Alias)을 지정해 준다. 생략할 경우 쿼리 실행 결과의 헤더(컬럼명)가 CASE WHEN... 구문 전체로 지저분하게 출력되므로, 가독성을 위해 반드시 명시하는 것이 좋다.

💻 실전 적용 예시

회원의 누적 구매 금액(TOTAL_PRICE)에 따라 VIP, GOLD, SILVER 등급을 부여하는 경우를 생각해보자.

SELECT 
    MEMBER_ID,
    TOTAL_PRICE,
    CASE 
        WHEN TOTAL_PRICE >= 100000 THEN 'VIP'
        WHEN TOTAL_PRICE >= 50000 THEN 'GOLD'
        ELSE 'SILVER'
    END AS MEMBER_GRADE
FROM 
    PURCHASE_HISTORY;

핵심 포인트: 변수에 'VIP'를 대입하는 것이 아니다! SELECT 조회 결과물에 MEMBER_GRADE라는 가상의 열을 하나 더 생성하여, 각 행의 조건에 맞는 텍스트를 출력하게 하는 것이다.

2. 단일 조건의 치트키: IF 함수 (MySQL 특화)

조건이 단순히 참(True)/거짓(False) 두 가지로만 나뉠 때는 CASE WHEN보다 삼항 연산자처럼 쓸 수 있는 IF 함수가 훨씬 간결하고 강력하다. 프로그래머스 코딩테스트 환경(MySQL)에서 유용하게 쓰인다.

💡 기본 문법

IF(조건, 참일 때 반환값, 거짓일 때 반환값) AS 새로운_컬럼명

💻 실전 적용 예시

중고거래 게시판에서 상태(STATUS)가 'SALE'이면 '판매중', 그 외의 경우 '판매완료'로 출력해야 하는 경우다.

SELECT 
    BOARD_ID,
    TITLE,
    IF(STATUS = 'SALE', '판매중', '판매완료') AS STATUS_KOR
FROM 
    USED_GOODS_BOARD;

3. NULL 값 처리의 스페셜리스트: IFNULL

코딩테스트에서 값을 직접 "대입"하고 싶게 만드는 가장 큰 원인은 바로 비어있는 NULL 데이터다. NULL 값을 다른 문자열이나 숫자로 대체하고 싶을 때는 IFNULL (또는 COALESCE)을 사용한다.

💡 기본 문법

IFNULL(검사할_컬럼, NULL일_때_대체할_값) AS 컬럼명

💻 실전 적용 예시

이름(NAME)이 없는 동물의 이름을 "No name"으로 대체해서 출력해야 하는 경우다.

SELECT 
    ANIMAL_ID,
    IFNULL(NAME, 'No name') AS NAME
FROM 
    ANIMAL_INS;

🚀 요약 (Cheat Sheet)

SQL 문제를 마주했을 때는 "원본 데이터를 수정하는 것이 아니라, 도화지(SELECT) 위에 내가 원하는 형태의 새로운 열(Column)을 그려낸다"고 시각화하자. 이 감각만 익히면 복잡한 코딩테스트 SQL 문제도 알고리즘처럼 명쾌하게 풀이할 수 있다!

1. 문제 분석

여러 개의 플레이리스트 배열이 주어질 때, 다음 규칙에 따라 음악을 정렬하여 하나의 문자열로 반환해야 합니다.

1. 1순위: 가장 많이 등장한 음악부터 정렬 (빈도수 내림차순)
2. 2순위: 빈도수가 같을 경우, 전체 데이터에서 더 먼저 등장한 음악부터 정렬 (등장 순서 오름차순)

2. 핵심 설계: 절대적 등장 순서(Global Order) 추적

단순히 플레이리스트 배열의 인덱스(enumerate)만으로는 한 문자열 내에 여러 음악이 있을 때의 세부 순서를 보장할 수 없습니다. 따라서 전체 탐색 과정에서 새로운 음악이 발견될 때마다 증가하는 전역 카운터(appearance_order)를 도입하여 해결했습니다.

3. 최종 구현 코드

def solution(playlists):
    freq_map = {}          # 음악별 총 빈도수 저장 (Hash Map)
    first_appearance = {}  # 음악별 최초 등장 절대 순서 저장
    appearance_order = 0   # 전역 순서 카운터

    for playlist in playlists:
        songs = playlist.split() # 공백 기준 파싱

        for song in songs:
            # 빈도수 업데이트: .get()을 사용하여 초기값 0 보장
            freq_map[song] = freq_map.get(song, 0) + 1

            # 최초 등장 시점에만 절대 순서 기록
            if song not in first_appearance:
                first_appearance[song] = appearance_order
                appearance_order += 1

    # 정렬 대상 추출
    unique_songs = list(freq_map.keys())

    # 다중 조건 정렬 적용
    # -freq_map[x]: 빈도수 기준 내림차순
    # first_appearance[x]: 등장 순서 기준 오름차순
    unique_songs.sort(key=lambda x: (-freq_map[x], first_appearance[x]))

    return "".join(unique_songs)

4. 주요 문법 및 기술적 포인트

① dict.get(key, default)의 안전성

딕셔너리에서 존재하지 않는 키를 참조하면 KeyError가 발생합니다. get() 메서드는 키가 없을 경우 두 번째 인자로 전달한 default 값을 반환하므로, + 1 연산을 통해 빈도수를 카운트할 때 별도의 조건문 없이 깔끔하게 처리할 수 있습니다.

② lambda를 활용한 다중 조건 정렬

파이썬의 sort는 튜플을 정렬 키로 반환하면 왼쪽 요소부터 차례대로 비교합니다.

• 내림차순이 필요한 숫자형 데이터에는 -를 붙여 대소 관계를 반전시킵니다.
• (-freq_map[x], first_appearance[x])는 "빈도수는 크면 클수록(마이너스 값이 작을수록) 앞으로, 등장 순서는 작으면 작을수록 앞으로"라는 복합적인 요구사항을 단 한 줄로 해결합니다.

③ 해시 테이블(Dictionary)의 시간 복잡도

음악의 이름을 키로 사용하여 데이터를 관리함으로써, 삽입과 조회 모두 $O(1)$의 시간 복잡도를 가집니다. 전체 음악의 개수가 $N$, 고유 음악의 개수가 $M$일 때, 전체 로직은 대략 $O(N + M \log M)$ 이내에 수행되므로 매우 효율적입니다.

5. 마무리

데이터의 물리적 순서가 논리적 우선순위에 영향을 미치는 경우, 탐색 시점의 상태를 해시 테이블에 박제해두는 테크닉이 유용합니다. enumerate의 한계를 global counter로 극복하는 과정이 이번 구현의 핵심이었습니다.

SQL 문제 해결 회고 프로그래머스 '조건에 맞는 개발자 찾기' 문제를 풀며, 일반적인 외래키(FK) 매핑이 아닌 비트 연산(Bitwise Operation)을 통한 조인 기법을 학습했다. 더 나아가, JOIN 연산 시 필연적으로 발생하는 '1:N 데이터 증식(뻥튀기)' 문제를 해결하기 위해 DISTINCT를 사용한 사후 처리 방식과 EXISTS를 사용한 사전 차단 방식의 아키텍처 차이를 깊이 있게 분석해 본다.

📌 1. 문제의 핵심: 비트 마스킹(Bit Masking) 해독

하나의 정수(SKILL_CODE) 안에 여러 개의 스킬 상태를 구겨 넣는 비트 마스킹 방식에서는 일반적인 등호(=)로 조인할 수 없다. 일치 여부가 아니라 '교집합'을 구해야 하므로, 비트 단위 연산자 & (AND)를 사용해야 한다.

• 조인 조건: (D.SKILL_CODE & S.CODE) = S.CODE
• 개발자의 스킬 코드와 특정 스킬 코드를 & 연산했을 때, 원본 스킬 코드가 그대로 나온다면 해당 스킬을 보유하고 있다는 뜻이다.

🚨 2. 첫 번째 접근: JOIN + DISTINCT (사후 처리)

가장 직관적인 방법은 비트 연산을 조건으로 JOIN을 수행하는 것이다.

SELECT DISTINCT D.ID, D.EMAIL, D.FIRST_NAME, D.LAST_NAME
FROM DEVELOPERS AS D
JOIN SKILLCODES AS S ON (D.SKILL_CODE & S.CODE) = S.CODE
WHERE S.NAME IN ('Python', 'C#')
ORDER BY D.ID ASC;

딜레마: 왜 DISTINCT가 필수적인가?

조인을 수행하는 순간, 압축되어 있던 코드가 풀리며 개발자 1명의 데이터가 자신이 보유한 스킬 개수만큼 여러 줄로 복제(증식)된다. 만약 어떤 개발자가 Python과 C#을 모두 할 줄 안다면, 조인된 거대한 임시 테이블에는 그 개발자의 행이 2줄 생성된다. 이 상태로 SELECT를 하면 동일한 개발자가 두 번 출력되는 논리적 오류가 발생하므로, 마지막에 DISTINCT로 중복을 제거해 주어야만 정답이 된다.

하지만 데이터가 수천만 건이라면? 쓸데없이 데이터를 1:N으로 복제해 놓고 다시 압축하는 것은 심각한 메모리 낭비를 초래한다.

🛡️ 3. 최적화된 아키텍처: EXISTS (원천 봉쇄)

JOIN이 두 테이블을 물리적으로 '결합'하여 데이터를 증식시킨다면, EXISTS는 결합하지 않고 서브쿼리를 통해 '존재 여부'만 질문하는 방식이다.

SELECT D.ID, D.EMAIL, D.FIRST_NAME, D.LAST_NAME
FROM DEVELOPERS AS D
WHERE EXISTS (
    SELECT 1 
    FROM SKILLCODES AS S
    WHERE S.NAME IN ('Python', 'C#')
      AND (D.SKILL_CODE & S.CODE) = S.CODE
)
ORDER BY D.ID ASC;

왜 이 방식이 압도적으로 우수한가? (성능 최적화)

1. 쇼트 서킷 평가 (Short-Circuit Evaluation): EXISTS는 서브쿼리 내에서 조건에 맞는 데이터(예: Python)를 딱 하나라도 발견하는 순간, 그 뒤의 데이터(예: C# 보유 여부)는 더 이상 쳐다보지도 않고 탐색을 즉시 종료(True 반환)한다. 불필요한 연산을 칼같이 끊어버린다.
2. 데이터 원형 보존 (무결성): DEVELOPERS 테이블의 데이터가 다른 테이블과 결합하지 않으므로, 원본 데이터가 단 한 줄도 복제되지 않는다. 애초에 중복이 발생하지 않으므로 무거운 DISTINCT 연산을 수행할 필요가 전혀 없다.

💡 결론 및 SQL SOP 업데이트

원칙: 대상 테이블(A)의 컬럼만 출력해야 하는데, 조건 확인을 위해 1:N 관계인 참조 테이블(B)을 뒤져야 한다면, 무지성 JOIN + DISTINCT를 쓰기 전에 EXISTS 서브쿼리로 탐색 공간을 소거할 수 있는지 먼저 검토하라.

최적화 철학 회고 SQL 문제를 풀면서, 무거운 그룹화(GROUP BY) 연산을 수행하기 전에 필터링(WHERE)을 먼저 걸어두는 것이 연산 속도 측면에서 압도적으로 이득일 것이라 판단했다. 이 생각은 데이터베이스 최적화 관점에서 100% 정답이었다. 하지만 놀라운 점은, 이것이 개발자의 '선택사항'이 아니라 SQL이라는 언어 자체가 성능 최적화를 강제하기 위해 만들어둔 '엄격한 문법적 실행 파이프라인'이라는 사실이다. 오늘은 그 파이프라인의 뼈대와 WHERE, HAVING의 본질적인 차이를 정리한다.

📌 SQL은 작성된 순서대로 실행되지 않는다

우리는 코드를 위(SELECT)에서부터 아래로 읽고 작성하지만, 데이터베이스 엔진(Optimizer)은 완전히 다른 순서로 쿼리를 조립하고 실행한다. 이 절대적인 실행 순서를 모르면 쿼리 최적화는 불가능하며, 잦은 문법 에러(Syntax Error)에 시달리게 된다.

⚙️ SQL의 절대적 실행 파이프라인 (Execution Order)

1. FROM / JOIN (데이터 탐색): "어느 테이블에서 데이터를 가져올 것인가?"
2. WHERE (사전 필터링): "가져온 원본 데이터 중 조건에 안 맞는 행(Row)은 버리자!"
3. GROUP BY (그룹화 연산): "살아남은 데이터들을 특정 기준(ID 등)으로 끼리끼리 묶자."
4. HAVING (사후 필터링): "묶어서 집계해 보니 조건에 미달하는 그룹이 있네? 버리자!"
5. SELECT (데이터 추출): "최종적으로 화면에 보여줄 컬럼만 선택하자."
6. ORDER BY (정렬): "결과를 예쁘게 정렬하자."

🚨 WHERE vs HAVING: 필터링 시점의 결정적 차이

두 키워드 모두 데이터를 걸러내는(Filtering) 역할을 하지만, 파이프라인 상의 '시점'이 완전히 다르다. 이 둘을 혼동하면 치명적인 성능 저하나 논리 오류가 발생한다.

1. WHERE (사전 필터링)

• 실행 시점: GROUP BY로 데이터를 묶기 전.
• 역할: 원본 테이블의 날것(Raw Data) 상태에서 개별 행(Row)들을 걸러낸다.
• 최적화 관점: 여기서 최대한 많은 데이터를 걸러내야, 다음 단계인 GROUP BY 연산에 들어가는 메모리와 CPU 비용이 비약적으로 줄어든다. (예: ADDRESS LIKE '서울%'로 서울 식당만 미리 남겨두기)
• 주의: WHERE 절 안에는 AVG(), COUNT() 같은 집계 함수를 절대 쓸 수 없다. 아직 묶이지 않았기 때문이다.

2. HAVING (사후 필터링)

• 실행 시점: GROUP BY 연산이 모두 끝난 후.
• 역할: 이미 끼리끼리 묶여서 연산(AVG, SUM 등)이 끝난 결과 그룹을 걸러낸다.
• 사용 예시: *"그룹화하여 계산한 리뷰 평균 점수가 4.0 이상인 식당만 구하세요."* 라는 조건은 사전에 알 수 없고 묶어봐야 알 수 있으므로 무조건 HAVING을 써야 한다. (HAVING AVG(SCORE) >= 4.0)

💡 최종 결론 (SOP)

*"GROUP BY를 먼저 쓰고 WHERE를 나중에 쓰면 안 되나요?"*

불가능하다. SQL은 애초에 개발자가 무거운 연산(GROUP BY)을 쓸데없이 방대한 데이터에 적용하는 참사를 막기 위해, WHERE로 먼저 모수를 줄이고 나서 GROUP BY를 하도록 문법적 순서를 강제해 두었다.

단순히 정답을 맞히는 것을 넘어 데이터베이스 엔진 내부의 파이프라인을 이해하고 쿼리를 작성하는 것. 이것이 쿼리 작성 SOP의 가장 중요한 첫 단추이다.

SOP (Standard Operating Procedure) 수립 회고 알고리즘 문제를 풀 때마다 플랫폼(백준 vs 프로그래머스)의 입출력 방식 차이로 코드가 꼬이는 것을 막기 위해, 나만의 범용 보일러플레이트(Boilerplate) 템플릿을 구축했습니다. 더 나아가, 함수형 프로그래밍의 핵심인 '데이터 불변성(Immutability)'과 '함수의 순수성(Purity)'을 템플릿의 기본 철학으로 강제하여 버그를 원천 차단하는 아키텍처를 설계했습니다.

📌 핵심 철학 1: 관심사의 완벽한 분리 (Separation of Concerns)

알고리즘 문제 풀이도 소프트웨어 설계입니다. 입출력을 처리하는 로직과 수학적 로직이 섞여 있으면 디버깅이 어렵습니다.

• main() (I/O 컨트롤러): 콘솔에서 데이터를 읽어와 파싱하고, 결과를 출력(print)하는 역할만 수행.
• solution() (비즈니스 컨트롤러): 플랫폼과 맞닿아 있는 함수. 데이터 전처리(정렬 등)를 수행하고 적절한 알고리즘 라이브러리를 호출.
• two_pointers() (순수 알고리즘 라이브러리): 정제된 파라미터를 받아 수학/알고리즘 연산만 수행 후 값을 return.

📌 핵심 철학 2: 데이터 훼손 금지 (Immutability)

*"a.sort()를 습관적으로 쓰다 보면, 원본 데이터를 훼손하는 나쁜 습관이 들지 않을까?"*

배열을 매개변수로 넘길 때 파이썬은 '참조(Reference)'로 넘깁니다. 알고리즘 함수 내부에서 a.sort()(In-place 정렬)를 해버리면, 밖에서 그 데이터를 기다리던 다른 로직들은 순서가 뒤죽박죽된 오염된 데이터를 받게 되는 치명적인 부수 효과(Side Effect)가 발생합니다.

따라서 원본 데이터의 훼손을 막기 위해 항상 sorted(a)를 사용하여 독립적인 복사본을 만들어 넘겨야 합니다. 특히 return two_pointers(n, sorted(a), target_sum) 처럼 매개변수 위치에서 인라인(Inline)으로 호출하면, 불필요한 지역 변수 할당을 막고 가비지 컬렉터(GC)가 깔끔하게 메모리를 정리하는 파이썬다운(Pythonic) 코드가 완성됩니다.

💻 파이썬 통합 보일러플레이트 템플릿 (최종 완성본)

실전 코딩 테스트에서 사용할 범용 뼈대입니다. (예시: 두 수의 합)

import sys

# [1. 전역 설정] 백준 시간 초과 방지
input = sys.stdin.readline

# ---------------------------------------------------------

# [2. 순수 알고리즘 라이브러리] - 연산만 수행
def two_pointers(n, sorted_a, target_sum):
    start = 0
    end = n - 1
    count = 0

    while start < end:
        current_sum = sorted_a[start] + sorted_a[end]
        if current_sum < target_sum:
            start += 1
        elif current_sum > target_sum:
            end -= 1
        else:
            count += 1
            start += 1
            end -= 1

    return count

# ---------------------------------------------------------

# [3. 비즈니스 로직 컨트롤러] - 프로그래머스 제출 환경
def solution(n, a, target_sum):
    # 습관의 형성: 원본 데이터 'a'를 훼손하지 않고(a.sort() 금지), 
    # sorted(a)를 인라인으로 넘겨 불필요한 변수 할당을 막고 불변성을 유지한다.
    return two_pointers(n, sorted(a), target_sum)

# ---------------------------------------------------------

# [4. 표준 입출력 컨트롤러] - 백준 환경
def main():
    n = int(input())
    a = list(map(int, input().split()))
    target_sum = int(input())

    # 여기서 a를 그대로 solution에 넘겨도, a의 원본 순서는 영원히 보호됨!
    print(solution(n, a, target_sum))

# ---------------------------------------------------------

# [5. 프로그램 진입점]
# 내가 '직접' 실행할 때만 main() 구동. 모듈로 import 될 때는 실행 방지.
if __name__ == "__main__":
    main()

SOP (Standard Operating Procedure) 수립 회고 백준(BOJ)과 프로그래머스는 입출력 환경이 완전히 다릅니다. 백준은 날것의 문자열을 직접 파싱해야 하고, 프로그래머스는 정제된 매개변수를 던져줍니다. 이 두 플랫폼 사이에서 코드를 짤 때마다 헷갈리는 것을 방지하고, '관심사의 분리(Separation of Concerns)'를 완벽하게 지키기 위해 나만의 범용 보일러플레이트(Boilerplate) 템플릿을 구축했습니다.

📌 왜 범용 템플릿이 필요한가? (아키텍처 설계)

알고리즘 문제 풀이도 결국 소프트웨어 엔지니어링의 일환입니다. 입출력을 처리하는 로직과 실제 문제를 푸는 수학적 로직이 섞여 있으면 디버깅이 어렵고 코드를 재사용할 수 없습니다.

• main()의 역할 (I/O 전담): 콘솔에서 데이터를 읽어와 파싱하고, 결과를 출력하는 역할만 수행합니다.
• solution()의 역할 (비즈니스 로직 전담): 데이터를 가공하여 정답을 도출하는 순수 수학/알고리즘 연산만 수행합니다.

이렇게 설계하면 백준에서 통과한 solution() 내부 로직만 그대로 복사해서 프로그래머스에 제출해도 단 한 줄의 수정 없이 통과할 수 있는 플랫폼 독립성을 얻게 됩니다.

💻 파이썬 통합 보일러플레이트 템플릿

실전 코딩 테스트에서 타건 시간을 최소화하기 위해 군더더기를 모두 뺀 가장 축약된 형태의 템플릿입니다. 앞으로 모든 문제는 이 뼈대 위에서 시작합니다.

import sys

# [1. 전역 설정] 백준 시간 초과 방지
input = sys.stdin.readline

# ---------------------------------------------------------

# [2. 비즈니스 로직 전담 구역]
# 프로그래머스 환경과 동일. 내부에 print나 input을 절대 넣지 않는다.
def solution(N, M, A):
    answer = 0

    # ... 핵심 알고리즘(투 포인터, 이분 탐색 등) 수행 ...

    return answer

# ---------------------------------------------------------

# [3. I/O 및 컨트롤러 구역]
def main():
    # 3-1. 입력 파싱 (문제에 맞게 수정)
    # ex) N, M = map(int, input().split())
    # ex) A = list(map(int, input().split()))

    # 임시 목업 데이터 (실제 풀이 시 삭제)
    N, M = 0, 0
    A = []

    # 3-2. 로직 호출 및 출력
    result = solution(N, M, A)
    print(result)

# ---------------------------------------------------------

# [4. 프로그램 진입점]
if __name__ == "__main__":
    main()

🚨 [핵심 회고] if __name__ == "__main__": 은 왜 쓰는 걸까?

파이썬 코드를 작성하며 가장 궁금했던 것은 *"선언한 적도 없는 __name__이라는 변수를 어떻게 조건문에서 비교하고 있는가?"* 였습니다. 이 특수 내장 변수(Magic Variable)의 작동 원리를 파헤친 결과는 다음과 같습니다.

1. 직접 실행할 때 (주인공): 터미널에서 이 파일을 직접 실행하면, 파이썬 인터프리터가 몰래 맨 윗줄에 __name__ = "__main__"을 할당해 줍니다. 즉, 이 조건문이 True가 되어 main()(입출력 및 테스트)이 정상 작동합니다.
2. Import 할 때 (부품): 내가 만든 알고리즘 함수를 다른 파일에서 import 해서 쓰려고 하면, 파이썬은 __name__에 __main__ 대신 '파일의 원래 이름'을 넣어줍니다. 조건문이 False가 되므로, 무거운 main()의 입출력 과정이 멋대로 실행되는 것을 완벽하게 차단하고 순수 함수(solution)만 안전하게 가져다 쓸 수 있습니다.

이 원리를 이해함으로써, 이제 내가 작성하는 템플릿의 모든 코드를 100% 통제할 수 있게 되었습니다.

학습 철학 회고 알고리즘 템플릿을 무작정 외우는 것을 경계하며, 뼈대 코드의 아주 사소한 '초기화 값' 하나까지 극한으로 의심해 보았습니다. "왜 뻔히 더할 첫 번째 값을 놔두고 0으로 시작해서 덧셈 연산을 한 번 낭비하는가?"에 대한 답을 치열하게 고민했고, 그 결과 우아한 템플릿이 지불하는 '가장 값싼 보험료'의 비밀을 깨달았습니다.

📌 문제 요약: 백준 2003번 (수들의 합 2)

N개의 자연수로 이루어진 배열에서, 연속된 부분 배열의 합이 정확히 M이 되는 경우의 수를 구하는 문제입니다.

• $N$이 최대 10,000이므로 이중 for문을 돌리면 $O(N^2)$이 되어 비효율적입니다.
• 배열의 원소가 모두 '자연수'라는 단조성(Monotonicity)이 보장되므로, 같은 방향으로 전진하는 투 포인터(애벌레 방식)를 사용하여 단 한 번의 스캔 $O(N)$으로 해결할 수 있습니다.

💻 정답 코드 (SOP 적용)

import sys

input = sys.stdin.readline

def two_pointers(N, M, A):
    # 배열 구간 [start, end)의 시작점과 끝점, 그리고 구간의 합 초기화
    end = 0
    total = 0
    count = 0

    # start를 0부터 N-1까지 차례대로 순회
    for start in range(N):
        # 1. 합이 M보다 작고, end가 배열의 끝에 도달하지 않았다면 계속 합을 키움
        while total < M and end < N:
            total += A[end]
            end += 1

        # 2. while문을 빠져나왔을 때 합이 정확히 M과 일치하는지 확인
        if total == M:
            count += 1

        # 3. 다음 start로 넘어가기 전, 현재 꼬리(start)가 가리키는 값을 합에서 빼줌
        total -= A[start]

    return count

def solution():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    print(two_pointers(N, M, A))

if __name__ == "__main__":
    solution()

🚨 [핵심 회고] 우리는 왜 total = 0으로 시작해야 하는가?

투 포인터를 구현하면서 가장 납득하기 어려웠던 부분은 초기화 로직이었습니다. *"어차피 첫 번째 원소를 참조할 거라면, 처음부터 total = A[0]으로 꽉 채워서 시작하면 while문의 첫 번째 0 + A[0] 덧셈 연산을 아낄 수 있는 것 아닌가? 왜 쓸데없이 0으로 시작해서 루프를 낭비하게 만들까?"*

이 1회의 연산을 아끼기 위한 '수동 언롤링(Manual Loop Unrolling)' 최적화 시도가 왜 오히려 독이 되는지, 컴퓨터의 시각에서 3가지 근거를 찾아냈습니다.

💡 나의 깨달음: 0으로 초기화하는 것은 낭비가 아니라 '영점 조절'이다.

1. 배열 참조 횟수는 사실 똑같다. 밖에서 A[0]을 미리 꺼내든, 안에서 A[0]을 더하든 결국 메모리 접근 횟수는 정확히 1번으로 동일하다. 절대적인 시간 이득이 생각보다 미미하다.

2. 덧셈 1번 아끼려다 '분기문(Branch)' 폭탄을 맞는다. 만약 밖에서 A[0]을 무작정 참조하려면, 배열이 비어있을 때(N = 0) 발생하는 IndexError를 막기 위해 함수 최상단에 if N == 0: return 0이라는 방어 로직을 반드시 넣어야 한다. 현대 CPU 아키텍처에서 단순 덧셈 비용은 거의 0에 수렴하지만, 이 조건 분기문(Branch)은 파이프라인을 깰 수 있어 비용이 훨씬 비싸다. 배보다 배꼽이 더 커진다.

3. 가장 버그가 적은 수학적 구간 설계: [start, end) (start 포함, end 미포함) 투 포인터에서 창문(Window)의 범위를 [start, end)로 설계하는 것이 실전에서 헷갈리지 않고 버그를 최소화하는 핵심 비결이다. 처음 start = 0, end = 0, total = 0으로 시작하면 구간의 길이는 end - start = 0, 즉 아무 원소도 포함하지 않은 텅 빈 창문 상태가 되어 수학적으로 완벽히 들어맞는다. 이때 end 포인터는 "다음에 더해야 할 새로운 원소의 인덱스"라는 아주 명확한 역할을 갖게 된다. 반면 시작부터 A[0]을 미리 더해버리면, end가 '이미 더해진 값'을 가리키게 되어 변수의 역할이 오염된다. 이를 막기 위해 end = 1부터 시작하게 억지로 끼워 맞추다 보면 온갖 엣지 케이스에서 누더기 코드가 탄생한다.

결론적으로 total = 0, start = 0, end = 0으로 시작하는 것은 불필요한 연산 낭비가 아니었다. 어떤 형태의 배열(빈 배열, 길이 1짜리 배열)이 들어와도 에러 없이 수학적 구간 [start, end)를 완벽하게 유지하기 위해 기꺼이 지불하는 가장 값싸고 확실한 보험료였다.

학습 철학 회고 단방향으로 이동하는 '애벌레' 투 포인터에 이어, 정렬된 배열에서 양끝에서 마주 보며 좁혀오는 '양끝 교차 투 포인터'의 뼈대를 세웠습니다. 특히 "왜 지나온 포인터를 다시 되돌려보지 않아도 모든 경우의 수를 보장하는가?"에 대한 수학적 의심을 품고, 탐색 공간이 소거되는 원리를 완벽하게 논리적으로 증명해 냈습니다.

📌 개념 요약: 양끝 교차 투 포인터 (Meeting in the Middle)

오름차순으로 정렬된 1차원 배열에서 두 개의 포인터(left, right)를 각각 양끝(인덱스 0과 N-1)에 배치하고, 서로를 향해 좁혀오며 원하는 타겟을 찾는 알고리즘입니다. 주로 '두 수의 합'을 구할 때 강력한 위력을 발휘하며, $O(N^2)$의 시간 복잡도를 단 한 번의 스캔인 $O(N)$으로 압축합니다.

💻 추상화된 템플릿 코드

정렬된 배열에서 두 수의 합이 target_sum이 되는 쌍의 개수를 찾는 순수 뼈대입니다.

def two_pointers_opposite_template(arr, target_sum):
    """
    :param arr: 오름차순으로 '정렬된' 1차원 배열
    :param target_sum: 찾고자 하는 두 수의 합
    """
    count = 0
    left = 0
    right = len(arr) - 1

    # 두 포인터가 교차하기 전까지 반복 (같은 원소를 두 번 고를 수 없으므로 < 사용)
    while left < right:
        current_sum = arr[left] + arr[right]

        # 1. 정답을 찾은 경우
        if current_sum == target_sum:
            count += 1
            # 다른 쌍을 찾기 위해 두 포인터 모두 안쪽으로 좁힘
            left += 1
            right -= 1

        # 2. 합이 타겟보다 작은 경우 -> 값을 키워야 하므로 left를 오른쪽으로
        elif current_sum < target_sum:
            left += 1

        # 3. 합이 타겟보다 큰 경우 -> 값을 줄여야 하므로 right를 왼쪽으로
        else:
            right -= 1

    return count

🚨 [핵심 회고] 탐색 공간의 소거: 우리는 왜 뒤돌아보지 않는가?

투 포인터를 공부할 때 가장 큰 의문은 이것이었습니다. *"합이 목표보다 크거나 작아서 포인터를 한쪽으로 이동시켰다면, 반대쪽 포인터를 과거로 되돌려서 다시 조합해 봐야 모든 경우의 수를 다 확인하는 것 아닌가?"*

이 의문에 대해 치열하게 고민한 결과, 다음과 같은 '탐색 공간 소거의 절대 법칙'을 깨달았습니다. 투 포인터가 지나온 길을 미련 없이 버릴 수 있는 이유는, 직접 더해보지 않아도 결과를 100% 확신할 수 있기 때문입니다.

💡 나의 깨달음: 투 포인터 소거의 미학

1. 합이 목표보다 작을 때 left가 오른쪽으로 이동하며 사라지는 이유: 유효한 원소들 중 가장 큰 값(right)과 더해졌는데도 목표보다 작았다면, 앞으로 만날 그 어떤 더 작은 right 값들과 더해봐야 어차피 무조건 작을 것이 수학적으로 확실하기 때문이다. 따라서 해당 left는 영구 폐기된다.

2. 합이 목표보다 클 때 right가 왼쪽으로 이동하며 사라지는 이유: 유효한 원소들 중 가장 작은 값(left)과 더해졌는데도 목표보다 컸다면, 앞으로 만날 그 어떤 더 큰 left 값들과 더해봐야 어차피 무조건 클 것이 수학적으로 확실하기 때문이다. 따라서 해당 right는 더 이상 볼 필요 없이 영구 폐기된다.

이중 for문이 무식하게 모든 것을 다 계산해보는 방식이라면, 투 포인터는 정렬의 성질을 이용해 "안 해봐도 오답인 걸 아니까 전체 경우의 수를 통째로 날려버리는" 극강의 지능적인 알고리즘이라는 것을 완벽히 체화했습니다.

학습 철학 회고 10만 개의 데이터가 주어졌을 때, 부분 연속 수열의 합을 구하려고 이중 for문($O(N^2)$)을 돌리면 100억 번의 연산이 발생하여 무조건 시간 초과가 납니다. 이때, 두 개의 포인터(손가락)를 사용하여 배열을 단 한 번만 스캔($O(N)$)하고 지나가는 우아한 최적화 기법의 뼈대를 세웁니다.

📌 개념 요약: 투 포인터란 무엇인가?

1차원 배열에서 두 개의 포인터(인덱스를 가리키는 변수)를 조작하여 원하는 결과를 얻는 알고리즘입니다. 동작 방식에 따라 크게 두 가지 철학으로 나뉩니다.

1. 같은 방향으로 이동 (애벌레 꿈틀대기): start와 end 포인터가 모두 인덱스 0에서 출발하여 오른쪽으로 이동합니다. 주로 '연속된 부분 배열의 합'을 구할 때 사용합니다.
2. 양끝에서 출발하여 교차 (가운데로 모이기): left는 0에서, right는 끝에서 출발하여 서로를 향해 다가옵니다. 주로 '정렬된 배열'에서 두 수의 합을 찾을 때 사용합니다.

📌 개념 요약: 슬라이딩 윈도우 (투 포인터의 특수 형태)

투 포인터처럼 두 개의 포인터를 쓰지만, 두 포인터 사이의 간격(창문 크기)이 항상 고정되어 있다는 점이 다릅니다. 마치 고정된 크기의 창문을 배열 위로 스르륵 밀고(Slide) 지나가는 것과 같습니다.

💡 동작 원리: 상태의 갱신과 포인터의 이동 (같은 방향 기준)

애벌레가 앞으로 나아가는 모습을 상상하면 쉽습니다.

• 머리(end) 전진: 현재 합이 목표값보다 작다면, end 포인터를 한 칸 앞으로 밀고 새로운 값을 합에 더합니다. (길이가 늘어남)
• 꼬리(start) 전진: 현재 합이 목표값보다 크거나 같다면, 현재 start 포인터가 가리키는 값을 합에서 빼고 start를 한 칸 앞으로 밉니다. (길이가 줄어듦)

💻 추상화된 템플릿 코드

가장 헷갈리기 쉬운 "같은 방향으로 이동하는 투 포인터 (연속 부분 배열의 합)"의 순수 뼈대입니다. 이 템플릿의 핵심은 IndexError를 완벽하게 통제하는 while문의 조건 설계에 있습니다.

def two_pointers_template(arr, target_sum):
    """
    :param arr: 1차원 배열 (자연수로만 이루어져 있어야 성립함)
    :param target_sum: 우리가 찾고자 하는 연속 부분 배열의 합
    """
    n = len(arr)
    count = 0        # 조건을 만족하는 경우의 수
    current_sum = 0  # 현재 포인터 구간의 합
    end = 0          # 꼬리(start)와 머리(end) 모두 0에서 시작

    # 1. 꼬리(start)를 0부터 끝까지 차례대로 이동시키며 탐색
    for start in range(n):

        # 2. [핵심 로직] 합이 타겟보다 작고, 머리(end)가 배열 범위를 벗어나지 않을 때까지 머리 전진
        while current_sum < target_sum and end < n:
            current_sum += arr[end]
            end += 1

        # 3. while문이 끝났다는 것은 합이 타겟 이상이 되었거나, end가 끝에 도달했다는 뜻
        if current_sum == target_sum:
            count += 1
            # 정답을 찾은 상태에서 다른 로직(예: 최소 길이 갱신 등)을 추가할 수 있음

        # 4. 다음 start로 넘어가기 전, 현재 start가 가리키는 값을 합에서 빼줌 (꼬리 당기기)
        current_sum -= arr[start]

    return count

🚨 설계 및 회고

• 자연수 전제 조건: 이 애벌레 방식은 배열에 '음수'가 섞여 있으면 사용할 수 없습니다. end를 전진시키면 무조건 합이 커지고, start를 전진시키면 무조건 합이 작아진다는 단조성(Monotonicity)이 보장되어야만 투 포인터의 논리가 성립하기 때문입니다.
• for문과 while문의 결합: 바깥쪽 for문이 start를, 안쪽 while문이 end를 조작합니다. 언뜻 보면 이중 루프라 $O(N^2)$ 같지만, end 변수는 루프가 돌아도 절대 뒤로 후진하지 않고 앞을 향해 $N$번만 이동합니다. 따라서 두 포인터가 각각 최대 $N$번씩만 움직이므로 전체 시간 복잡도는 $O(N)$이 되는 마법 같은 효율을 자랑합니다.

🚨 [핵심 회고] 우리는 왜 current_sum = 0으로 시작해야 하는가?

투 포인터를 구현하면서 가장 납득하기 어려웠던 부분은 초기화 로직이었습니다. *"어차피 첫 번째 원소를 참조할 거라면, 처음부터 current_sum = A[0]으로 꽉 채워서 시작하면 while문의 첫 번째 0 + A[0] 덧셈 연산을 아낄 수 있는 것 아닌가? 왜 쓸데없이 0으로 시작해서 루프를 낭비하게 만들까?"*

이 1회의 연산을 아끼기 위한 '수동 언롤링(Manual Loop Unrolling)' 최적화 시도가 왜 오히려 독이 되는지, 컴퓨터의 시각에서 3가지 근거를 찾아냈습니다.

💡 나의 깨달음: 0으로 초기화하는 것은 낭비가 아니라 '영점 조절'이다.

1. 배열 참조 횟수는 사실 똑같다. 밖에서 A[0]을 미리 꺼내든, 안에서 A[0]을 더하든 결국 메모리 접근 횟수는 정확히 1번으로 동일하다. 절대적인 시간 이득이 생각보다 미미하다.

2. 덧셈 1번 아끼려다 '분기문(Branch)' 폭탄을 맞는다. 만약 밖에서 A[0]을 무작정 참조하려면, 배열이 비어있을 때(N = 0) 발생하는 IndexError를 막기 위해 함수 최상단에 if N == 0: return 0이라는 방어 로직을 반드시 넣어야 한다. 현대 CPU 아키텍처에서 단순 덧셈 비용은 거의 0에 수렴하지만, 이 조건 분기문(Branch)은 파이프라인을 깰 수 있어 비용이 훨씬 비싸다. 배보다 배꼽이 더 커진다.

3. 가장 버그가 적은 수학적 구간 설계: [start, end) (start 포함, end 미포함) 투 포인터에서 창문(Window)의 범위를 [start, end)로 설계하는 것이 실전에서 헷갈리지 않고 버그를 최소화하는 핵심 비결이다. 처음 start = 0, end = 0, current_sum = 0으로 시작하면 구간의 길이는 end - start = 0, 즉 아무 원소도 포함하지 않은 텅 빈 창문 상태가 되어 수학적으로 완벽히 들어맞는다. 이때 end 포인터는 "다음에 더해야 할 새로운 원소의 인덱스"라는 아주 명확한 역할을 갖게 된다. 반면 시작부터 A[0]을 미리 더해버리면, end가 '이미 더해진 값'을 가리키게 되어 변수의 역할이 오염된다. 이를 막기 위해 end = 1부터 시작하게 억지로 끼워 맞추다 보면 온갖 엣지 케이스에서 누더기 코드가 탄생한다.

결론적으로 current_sum = 0, start = 0, end = 0으로 시작하는 것은 불필요한 연산 낭비가 아니었다. 어떤 형태의 배열(빈 배열, 길이 1짜리 배열)이 들어와도 에러 없이 수학적 구간 [start, end)를 완벽하게 유지하기 위해 기꺼이 지불하는 가장 값싸고 확실한 보험료였다.

학습 철학 회고 본격적인 알고리즘 딥 워크(CPU Overclocking)에 들어가기 전, 뇌를 예열(Cache Loading)하기 위해 가장 기본적이고 순수한 형태의 이분 탐색 뼈대를 백지에서 구현해 보았습니다. 어제 학습한 '파라메트릭 서치(Parametric Search)'와 무엇이 다른지 그 본질적 차이를 몸으로 체화하는 과정이었습니다.

📌 문제 요약: 1920번 수 찾기

$N$개의 정수가 주어져 있을 때, 이 안에 $X$라는 정수가 존재하는지 알아내는 가장 기본적인 탐색 문제입니다.

• $N$과 $M$이 최대 100,000이므로, 배열을 매번 선형 탐색($O(N)$)하게 되면 $O(NM)$으로 무조건 시간 초과가 발생합니다.
• 따라서 데이터를 한 번 정렬해 둔 뒤($O(N \log N)$), 절반씩 탐색 범위를 날려버리는 이분 탐색($O(\log N)$)을 $M$번 수행하여 $O(N \log N + M \log N)$의 시간 복잡도로 방어해야 합니다.

💻 실전 조립 코드 (SOP 적용 및 미세 최적화)

import sys
input = sys.stdin.readline

def binary_search(A, target):
    # 1. 탐색 공간 설정: 배열의 '인덱스' 양끝점
    start = 0
    end = len(A) - 1

    # 2. start와 end가 교차하기 전까지 반복
    while start <= end:
        mid = (start + end) // 2

        # 3. [핵심] 찾고자 하는 값을 정확히 발견한 경우 (Early Return)
        if A[mid] == target:
            return 1 

        # 4. 타겟이 더 크다면 오른쪽 탐색 (start를 mid 위로 끌어올림)
        elif A[mid] < target:
            start = mid + 1

        # 5. 타겟이 더 작다면 왼쪽 탐색 (end를 mid 아래로 끌어내림)
        else:
            end = mid - 1

    # 무한 루프를 다 돌았는데도 return 되지 않았다면 없는 것
    return 0

def solution():
    N = int(input())
    A = list(map(int, input().split()))
    M = int(input())
    B = list(map(int, input().split()))

    # [치명적 실수 방어] 탐색 루프에 들어가기 전, 반드시 딱 한 번만 정렬!
    A.sort()

    for target in B:
        print(binary_search(A, target))

if __name__ == "__main__":
    solution()

🚨 트러블 슈팅 및 심화 회고

순수 이분 탐색을 구현하며 정립한 3가지 핵심 엔지니어링 포인트입니다.

1. 순수 이분 탐색 vs 파라메트릭 서치 이 코드는 파라메트릭 서치가 아닙니다. 파라메트릭 서치는 딱 떨어지는 정답이 없어 부등호(>=)를 쓰고, best_answer라는 안전망을 두며 '최적의 조건'을 찾는 방식입니다. 반면, 이 문제는 A[mid] == target으로 '정확히 일치하는 값'을 찾으면 바로 탈출하는 전형적인 '순수 이분 탐색(Standard Binary Search)'입니다.

2. 정렬(sort())의 생명주기 통제 가장 흔하게 하는 치명적 실수가 sort()를 탐색 함수 안이나 쿼리를 도는 for문 안에 넣는 것입니다. 매 탐색마다 정렬을 수행하면 시간 복잡도가 폭발합니다. A.sort()를 입력 직후 단 한 번만 수행하여 생명주기를 완벽하게 통제했습니다.

3. 상태 변수와 break를 제거한 Early Return 구조 초기 코드에서는 answer = 1로 상태를 기록하고 break를 건 뒤 마지막에 return answer를 했습니다. 하지만 파이썬에서는 불필요한 상태 변수를 두지 않고, 타겟을 찾은 즉시 함수 자체를 탈출하는 return 1을 사용하면 코드가 훨씬 간결해지고 유지보수가 쉬워집니다.

학습 철학 회고 단순히 주어진 배열에서 숫자를 찾는 것을 넘어, "적어도 M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값"을 구하는 최적화 문제를 만났습니다. 이를 해결하기 위해 이분 탐색을 응용한 '파라메트릭 서치(Parametric Search)'의 뼈대를 설계하고, 탐색 공간을 재정의하는 과정을 거쳤습니다.

📌 문제 요약: 2805번 나무 자르기

나무의 수 $N$은 최대 100만, 가져가야 하는 나무의 길이 $M$은 최대 20억입니다. 톱의 높이를 1씩 줄여가며 선형 탐색($O(N \times \text{max_height})$)을 하면 무조건 시간 초과가 발생합니다. 따라서 "높이를 $H$로 설정했을 때, 얻을 수 있는 나무가 $M$ 이상인가? (Yes/No)"라는 결정 문제로 바꾸어 $O(N \log (\text{max_height}))$ 시간 복잡도로 해결해야 합니다.

💻 실전 조립 코드 (SOP 적용)

import sys

input = sys.stdin.readline

def binary_search_parametric(N, M, trees):
    # 1. 탐색 공간 설정: 배열의 인덱스가 아니라 '톱의 설정 높이' 범위!
    left = 0
    right = max(trees)
    best_answer = -1

    # 2. 이분 탐색 진행
    while left <= right:
        mid = (left + right) // 2

        # 3. 결정 함수(Yes/No) 통과 여부 확인
        if check_condition(trees, mid) >= M: 
            best_answer = mid # 조건을 만족하므로 일단 안전망에 저장 (Checkpoint)
            left = mid + 1    # "더 톱을 높게 설정해도 M미터가 나오는지 욕심내보자!"
        else:
            right = mid - 1   # 잘린 나무가 부족하므로 톱의 높이를 낮춰야 함

    return best_answer

def check_condition(trees, target_height):
    # [최적화] sum()과 제너레이터 표현식을 활용하여 O(N) 연산을 단 1줄로 압축
    # 나무가 톱의 높이(target_height)보다 클 때만 잘라서 더함
    return sum(tree - target_height for tree in trees if tree > target_height)

def solution():
    N, M = map(int, input().split())
    trees = list(map(int, input().split()))

    print(binary_search_parametric(N, M, trees))

if __name__ == "__main__":
    solution()

🚨 트러블 슈팅 및 심화 회고

파라메트릭 서치의 뼈대를 세우며 겪었던 3가지 핵심 고민을 기록합니다.

1. 탐색 공간(Search Space)의 착각 처음에는 left = 0, right = N - 1로 설정하여 '배열의 인덱스'를 탐색하려고 했습니다. 하지만 톱의 높이는 배열 안에 존재하는 나무의 높이와 정확히 일치하지 않을 수 있습니다. 따라서 탐색 공간 자체를 '톱이 가질 수 있는 높이의 범위 (0부터 가장 높은 나무까지)'로 재설정해야 완벽한 시뮬레이션이 가능함을 깨달았습니다.

2. 왜 == M으로 찾지 않고 부등호(>= M)를 쓰는가? 정확히 $M$미터로 떨어지는 톱의 높이가 존재하지 않을 수 있습니다. 문제의 요구사항은 '적어도 $M$미터'이므로, $M$미터 이상을 만족하는 조건 안에서 최댓값을 찾아야 합니다. 따라서 부등호는 필수불가결한 요소입니다.

3. check_condition의 음수 예외 처리 톱의 높이보다 낮은 나무는 잘리지 않아야 합니다. 처음에 조건문 없이 tree - height를 모두 더했다가, 잘리지 않은 나무가 오히려 전체 길이를 깎아먹는 논리적 오류를 발견했습니다. 이를 파이썬의 조건부 제너레이터 if tree > target_height를 통해 아주 깔끔하고 파이썬답게 방어했습니다.

학습 철학 회고 이전에 '다익스트라 완벽 해부' 포스팅에서 정리했던 특정 문제에 종속되지 않은 '순수한 다익스트라 뼈대(Template)'를 꺼내어, 실제 코딩 테스트 환경(백준 1753번)의 요구사항에 맞춰 조립해 보는 실전 훈련을 진행했습니다. 머릿속의 추상화된 논리를 실제 파이썬 코드로 번역할 때 발생하는 미세한 마찰음들을 디버깅하며 완벽한 SOP(설계 주도형 사고)를 체화했습니다.

📌 문제 요약: 1753번 최단경로

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는, 다익스트라(Dijkstra) 알고리즘의 교과서이자 표준과도 같은 문제입니다.

• 모든 간선의 가중치는 10 이하의 자연수입니다. (음수 가중치가 없으므로 다익스트라 적용 가능)
• 정점의 개수 $V$는 최대 20,000개, 간선의 개수 $E$는 최대 300,000개이므로, $O(V^2)$의 단순 탐색으로는 무조건 시간 초과가 발생합니다. 반드시 우선순위 큐(heapq)를 활용하여 $O(E \log V)$로 최적화해야 합니다.

💻 실전 조립 코드 (SOP 적용)

입력 파싱부터 알고리즘 실행, 출력까지 생명주기를 완벽하게 통제한 최종 코드입니다.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9) # 무한대

def dijkstra(graph, start, V) : 
    # 1. 메모장 초기화 및 시작점 세팅
    distance = [INF] * (V+1)
    distance[start] = 0

    # 2. 우선순위 큐 생성 및 튜플 (비용, 노드) 삽입
    pq = []
    heapq.heappush(pq, (0, start))

    # 3. 큐가 빌 때까지 탐색 반복
    while pq: 
        current_cost, current_node = heapq.heappop(pq)

        # [핵심 방어 로직] 큐에서 꺼낸 낡은 정보(현재 거리보다 큰 비용)는 무시
        if current_cost > distance[current_node]:
            continue 

        # 4. 인접 노드 탐색 및 지름길 갱신
        for next_node, weight in graph[current_node]:
            cost = current_cost + weight

            # 지름길을 발견했다면 메모장 갱신 및 큐에 삽입
            if distance[next_node] > cost:
                distance[next_node] = cost
                heapq.heappush(pq, (cost, next_node))

    return distance

def solution():
    V, E = map(int, input().split())
    start = int(input())

    # [최적화] 입력을 받는 즉시 인접 리스트(graph) 생성하여 메모리 낭비 방지
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        u, v, w = map(int, input().split())
        graph[u].append((v, w)) # (도착노드, 가중치)

    distance = dijkstra(graph, start, V)

    # 5. 1-based 인덱싱에 맞춘 정답 출력
    for i in range(1, V+1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])

# 전역 변수 오염을 막기 위한 메인 함수 호출
if __name__ == "__main__":
    solution()

🚨 트러블 슈팅 및 실전 최적화 포인트

뼈대를 실전에 적용하는 과정에서 겪은 파이썬 특화 문법과 구조적 고민을 회고합니다.

1. heapq 모듈의 올바른 사용과 튜플 정렬 원리 파이썬의 힙 큐는 튜플의 '첫 번째 원소'를 기준으로 오름차순 정렬합니다. 따라서 큐에 데이터를 넣을 때 습관적으로 (노드, 비용) 순으로 넣으면 엉뚱한 탐색을 하게 됩니다. 반드시 비용(Cost)을 맨 앞에 배치한 (cost, node) 형태로 heapq.heappush에 넘겨주어 최단 거리 우선 추출을 보장해야 합니다.

2. 입력과 동시에 그래프 가공 (메모리 최적화) 모든 입력을 2차원 배열에 한 번 다 담아둔 뒤, 그걸 다시 graph[u].append((v,w))로 재가공하는 것은 시간과 공간을 2배로 낭비하는 안 좋은 습관입니다. 데이터를 읽어 들이는 for 루프 안에서 즉시 목적지인 인접 리스트에 꽂아 넣음으로써 I/O 오버헤드를 최소화했습니다.

3. 스코프(Scope) 통제를 통한 전역 변수 오염 차단 distance나 graph 같은 핵심 배열들을 무분별하게 전역으로 빼지 않고, solution()이라는 큰 틀 안에서 생성하여 dijkstra() 함수의 파라미터로 안전하게 넘겨주었습니다. 이는 향후 여러 개의 테스트 케이스가 동시에 주어지는 시뮬레이션 환경에서 이전 데이터가 섞이는 치명적인 버그를 막아주는 강력한 설계 체력(SOP)입니다.

학습 철학 회고 그래프 알고리즘 중 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘은 '그리디'와 '자료구조'의 완벽한 융합체입니다. 복잡한 2차원 간선 배열을 BFS로 힘들게 탐색하는 대신, 1차원 부모 배열을 활용한 '유니온 파인드(Union-Find)'의 우아한 추상화를 통해 순환(Cycle)을 완벽하게 통제하는 뼈대를 세웁니다.

📌 개념 요약: 유니온 파인드 (Disjoint Set)

수많은 노드들이 서로 연결되어 있는지(같은 네트워크/조직인지) 판별하기 위한 자료구조입니다.

• Find (보스 찾기): 특정 노드의 '최상위 부모(Root)'를 찾습니다.
• Union (조직 병합): 두 노드가 속한 각각의 그룹을 하나로 합칩니다. 한쪽 보스를 다른 쪽 보스의 부하로 만듭니다.

📌 개념 요약: 크루스칼 (Kruskal's Algorithm)

가장 적은 비용으로 모든 노드를 연결하는 최소 신장 트리(MST)를 구하는 알고리즘입니다.

1. 모든 간선(도로)을 비용 기준으로 오름차순 정렬합니다. (Greedy)
2. 가장 싼 간선부터 확인하며, 두 노드의 보스(Root)가 다를 때만 도로를 연결(Union)합니다.
3. 보스가 같다면 이미 연결된 그룹이므로 버립니다. (순환/Cycle 방지)

💻 추상화된 템플릿 코드 (유니온 파인드 & 크루스칼)

가장 빈번하게 실수하는 Union 연산의 부모 갱신 로직과, 탐색 시간을 $O(1)$에 가깝게 줄여주는 Find 연산의 경로 압축(Path Compression)이 완벽하게 반영된 순수 템플릿입니다.

# ----------------------------------------
# 1. 유니온 파인드 (Union-Find) 핵심 모듈
# ----------------------------------------

def find_parent(parent, x):
    # 자기 자신이 보스가 아니라면, 진짜 보스를 찾을 때까지 재귀적으로 파고듦
    if parent[x] != x:
        # [핵심 최적화: 경로 압축] 
        # 거쳐간 모든 노드의 부모를 최상위 보스로 바로 갱신해버림 (다음 탐색 시간 O(1) 단축)
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    # 1. 각 노드의 진짜 보스(Root)를 찾음
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)

    # 2. 보스가 다르다면 병합 진행 (일반적으로 번호가 작은 쪽이 보스가 되도록 규칙 설정)
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

# ----------------------------------------
# 2. 크루스칼 (Kruskal) 메인 템플릿
# ----------------------------------------

def kruskal_template(v, edges):
    """
    :param v: 노드의 개수
    :param edges: (비용, 노드A, 노드B) 형태의 간선 리스트
    """
    # 1. 부모 테이블 초기화: 처음엔 모두 자기 자신이 보스
    parent = [0] * (v + 1)
    for i in range(1, v + 1):
        parent[i] = i

    # 2. 간선을 비용 기준으로 오름차순 정렬 (Greedy 철학)
    edges.sort()

    total_cost = 0
    edge_count = 0 # 조기 종료를 위한 간선 개수 카운팅

    # 3. 가장 싼 간선부터 하나씩 확인
    for cost, a, b in edges:

        # [방어 로직] 사이클이 발생하지 않는 경우에만(보스가 다를 때만) 연결
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b) # 조직 병합
            total_cost += cost         # 비용 합산
            edge_count += 1

            # [최적화] 모든 노드가 연결되려면 간선은 정확히 v - 1개가 필요함
            if edge_count == v - 1:
                break

    return total_cost

🚨 설계 및 회고

• 치명적 실수 방어 (Union 로직): 초보자들이 union_parent를 짤 때 parent[b] = a라고 잘못 작성하여, 최상위 보스가 아닌 말단 부하의 부모만 바꿔버리는 치명적인 논리 오류를 범하곤 합니다. 반드시 find_parent를 통해 양쪽의 최상위 보스(root_a, root_b)를 먼저 찾은 뒤, 보스끼리 계급장을 떼고 연결(parent[root_b] = root_a)해야 합니다.
• 경로 압축 (Path Compression): find 함수에서 return find_parent(...)를 하지 않고 parent[x] = find_parent(...)로 값을 덮어씌우는 이 단 한 줄의 코드가, 일렬로 늘어선 최악의 트리 형태 $O(V)$를 $O(\log V)$ 수준의 평평한 트리로 마법처럼 압축해 줍니다.

🚨 아키텍처 개선: 중복 검사 제거와 union 함수의 최적화

크루스칼 알고리즘 템플릿을 분석하다 보면 메인 루프에서 다음과 같은 구조를 마주하게 됩니다.

# [방어 로직] 사이클이 발생하지 않는 경우에만(보스가 다를 때만) 연결
if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b) # 조직 병합
    total_cost += cost         # 비용 합산

이 코드는 논리적으로 완벽하지만, 메인 루프에서 부모를 굳이 한 번 더 확인해야 했던 이유는, 기존의 union_parent 함수가 병합의 성공 여부(사이클 발생 여부)를 외부로 반환(Return)하지 않고 침묵했기 때문입니다.

만약 메인 루프에서 if 조건문을 빼버리고 함수를 바로 호출한다면, 사이클을 만드는 무효한 간선의 비용까지 total_cost에 합산되는 치명적인 논리 오류가 발생합니다.

이러한 중복을 제거하고 응집도를 높이기 위해, union_parent 함수가 단방향 실행으로 끝나지 않고 성공 여부를 반환(Boolean Return)하도록 아키텍처를 수정할 수 있습니다.

1. union_parent 함수 개선

def union_parent(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)

    # 이미 같은 보스라면 사이클 발생. 병합하지 않고 False 반환
    if root_a == root_b:
        return False

    # 보스가 다르다면 병합 후 True 반환
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

    return True

2. 메인 루프 개선

for cost, a, b in edges:
    # union_parent가 True(새로운 병합 성공)를 반환했을 때만 내부 로직(비용 및 간선 추가) 실행
    if union_parent(parent, a, b):
        total_cost += cost
        edge_count += 1

        # [최적화] 모든 노드가 연결되려면 간선은 정확히 v - 1개가 필요함
        if edge_count == v - 1:
            break

이렇게 설계하면 메인 루프에서 불필요하게 find_parent를 반복 호출하는 일을 막아 시간 복잡도를 최적화하고, 코드의 가독성과 책임 분배를 명확히 할 수 있습니다.

학습 철학 회고 그리디 알고리즘은 직관적으로 풀기 쉽다는 함정이 있습니다. "그냥 지금 제일 좋아 보이는 걸 고르면 되는 거 아니야?"라는 생각으로 접근하다가 수많은 반례(Edge Case)에 부딪혀 무너지곤 합니다. 이번에는 감각에 의존하는 코딩을 멈추고, '탐욕'이 수학적인 정답으로 귀결되기 위해 반드시 갖춰야 할 이론적 전제 조건을 뼈대로 세웁니다.

📌 개념 요약: 그리디 알고리즘이란?

미래를 내다보지 않고, "오직 현재 상태에서 가장 최선이라고 생각되는 선택"만을 반복하여 최종 해답에 도달하는 방법론입니다.

하지만 모든 문제에 그리디를 적용할 수는 없습니다. 눈앞의 마시멜로를 당장 먹는 것이 최종적으로는 손해일 수 있기 때문입니다. 따라서 그리디가 완벽한 알고리즘으로 작동하려면 다음 두 가지 절대 조건이 모두 성립해야 합니다.

1. 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 전혀 영향을 주지 않아야 합니다. 즉, 지금의 최적의 선택이 '전체 문제의 최적해'를 무조건 보장해야 합니다.
2. 최적 부분 구조 (Optimal Substructure): DP와 마찬가지로, 전체 문제의 최적해가 부분 문제들의 최적해로 이루어져 있어야 합니다.

💡 동작 원리: "정렬(Sort)"이라는 필수 전제

그리디 알고리즘 자체는 DFS나 이분 탐색처럼 정형화된 코드 템플릿(자료구조)이 존재하지 않습니다. 문제마다 '탐욕의 기준'이 다르기 때문입니다.

하지만 거의 모든 그리디 코딩 테스트 문제에는 공통된 뼈대가 있습니다. 바로 가장 좋은 것을 빠르게 뽑아내기 위해, 데이터를 특정한 기준에 맞춰 '정렬(Sort)'하거나 '우선순위 큐(Min-Heap)'에 담아두고 시작한다는 점입니다.

💻 추상화된 템플릿 로직 (설계 뼈대)

정형화된 코드는 없지만, SOP(설계 주도형 사고) 관점에서 그리디 문제를 마주했을 때 전개해야 하는 사고의 흐름과 뼈대 로직은 다음과 같습니다.

def greedy_template(data):
    # 1. [핵심] 탐욕의 기준 설정 및 정렬
    # (예: 회의가 끝나는 시간이 빠른 순, 무게가 가벼운 순 등)
    data.sort(key=lambda x: (x[1], x[0])) 
    # 또는 heapq.heapify(data) 사용

    answer = 0
    current_state = 0 # 현재 상태를 추적할 변수

    # 2. 정렬된 데이터를 순회하며 탐욕적 선택 진행
    for item in data:
        # 3. [방어 로직] 현재 아이템이 제약 조건을 만족하는가? (가지치기)
        if is_valid(item, current_state):
            # 4. 선택 및 상태 갱신
            answer += item.value
            current_state = item.end_time # 다음 선택을 위한 상태 업데이트

    return answer

🚨 설계 및 회고

• 정당성 증명: 그리디 문제를 풀 때는 코드를 짜기 전에 *"반례가 정말 없을까?"*를 최소 5분 이상 종이에 그려가며 검증해야 합니다. 만약 동전 거스름돈 문제에서 동전 단위가 배수 관계가 아니라면(예: 100원, 70원, 10원), 가장 큰 동전부터 탐욕적으로 고르는 방식은 오답을 냅니다. 이때는 DP나 BFS로 돌아가야 합니다.
• 우선순위 큐의 결합: 매 순간 변화하는 상황 속에서 계속 최솟값/최댓값을 뽑아야 한다면, 매번 .sort()를 호출하는 대신 $O(\log N)$으로 값을 뽑아주는 heapq를 사용하는 것이 완벽한 그리디 구현체입니다. (예: 백준 1715 카드 정렬하기)

학습 철학 회고 다이나믹 프로그래밍(DP)은 번뜩이는 천재성을 요구하는 퍼즐이 아닙니다. 복잡하고 거대한 문제를 '완벽하게 똑같은 구조를 가진 아주 작은 문제'로 쪼개고, 그 작은 문제들의 정답을 메모장에 적어두었다가 재활용하는 철저한 메모의 기술입니다.

📌 개념 요약: DP는 무엇인가?

수학의 점화식을 코드로 옮겨 놓은 것입니다. 피보나치 수열처럼 똑같은 연산이 미친 듯이 반복될 때, 한 번 계산한 결과는 배열(dp 테이블)에 저장(Memoization)해 두고, 나중에 똑같은 질문이 들어오면 계산 없이 배열에서 바로 꺼내 쓰는 최적화 기법입니다.

• 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해답이 작은 문제들의 최적 해답으로 구성될 때 성립합니다.
• 중복되는 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 반복해서 나타나야 메모장의 효율이 극대화됩니다.

💡 동작 원리: 상태 전이 방정식 (점화식) 설계

DP 문제를 푸는 설계 주도형 사고(SOP)의 핵심은 dp[i]가 무엇을 의미하는지 한국어로 정확히 정의하는 것입니다. "계단을 오를 때 연속 3번 밟지 않는 최대 점수", "1을 만들기 위한 최소 연산 횟수" 등 정의가 명확해야, dp[i]를 구하기 위해 과거의 값(dp[i-1], dp[i-2])을 어떻게 조합할지 점화식이 보입니다.

💻 추상화된 템플릿 코드

DP는 문제마다 점화식이 모두 다르기 때문에 고정된 코드는 없지만, 가장 빈번하게 사용되는 바텀업(Bottom-Up) 방식의 뼈대 설계는 정형화할 수 있습니다.

def dp_bottom_up_template(N, data):
    """
    :param N: 구하고자 하는 목표 인덱스
    :param data: 각 단계에서 주어지는 비용이나 점수 리스트
    """
    # 1. [방어적 프로그래밍] N이 작을 때의 IndexError를 방지하기 위해 넉넉한 크기 할당
    MAX_SIZE = 100001 # 문제 조건의 N_MAX + 1
    dp = [0] * MAX_SIZE

    # 2. 초기값 (Base Case) 세팅
    dp[1] = data[1]
    dp[2] = data[1] + data[2] # 예: 첫 칸과 두 번째 칸은 무조건 더하는 게 이득일 경우

    # 3. 바텀업 점화식 전개 (루프 설계)
    for i in range(3, N + 1):
        # [핵심 로직] 과거의 최적해를 조합하여 현재의 최적해를 도출
        # 예시: i-2에서 두 칸 점프해서 오거나, i-3에서 두 칸 점프 후 한 칸 걸어오는 경우 중 최댓값
        dp[i] = max(dp[i-2] + data[i], dp[i-3] + data[i-1] + data[i])

    # 4. 최종 목표값 반환
    return dp[N]

🚨 설계 및 회고

• 방어적 프로그래밍 (배열 크기 통제): dp = [0] * (N + 1)로 선언한 상태에서 N=1이 주어지면 dp[2]에 접근하다가 즉시 IndexError가 터집니다. 메모리를 약간 더 쓰더라도 문제의 최대 조건만큼 배열을 넉넉히 초기화해 두면 런타임 에러의 80%를 막을 수 있습니다.
• 출력의 위치 통제: DP 연산 과정인 for 문 안에 print(dp[N])이 들어가 있지 않은지 주의해야 합니다. 생명주기와 스코프를 통제하여, 모든 계산이 끝난 뒤 깔끔하게 한 번만 반환하도록 설계해야 합니다.

학습 철학 회고 단순히 배열에서 숫자를 빨리 찾는 기법으로만 이분 탐색을 외우면, 정작 코딩 테스트의 꽃인 '파라메트릭 서치(Parametric Search)' 응용 문제를 풀지 못합니다. 탐색 공간을 반으로 접어 나간다는 본질적 철학과, left와 right 포인터가 교차하는 그 아슬아슬한 경계값을 어떻게 통제할 것인지 뼈대를 세웁니다.

📌 개념 요약: 이분 탐색이란 무엇인가?

1억 개의 데이터가 있을 때, 앞에서부터 하나씩 찾으면 최대 1억 번($O(N)$)이 걸리지만, "업 앤 다운" 게임처럼 중간값을 찔러보고 탐색 범위를 절반씩 날려버리면 단 27번($O(\log N)$) 만에 답을 찾아내는 극한의 최적화 알고리즘입니다.

• 절대 전제 조건: 탐색하려는 데이터는 반드시 정렬(Sorted)되어 있어야 합니다.
• 파라메트릭 서치(Parametric Search): "원하는 값을 찾아라"라는 문제를 "이 조건을 만족하는 가장 큰(혹은 작은) 값은 무엇인가?"라는 결정 문제(Yes/No)로 뒤집어서 푸는 고급 응용 기법입니다.

💡 동작 원리: 공간의 분할과 포인터 이동

이분 탐색의 핵심은 3개의 포인터(left, right, mid)를 관리하는 것입니다.

1. mid = (left + right) // 2로 중간 지점을 잡습니다.
2. 타겟이 mid보다 크다면, 정답은 무조건 오른쪽에 있으므로 left = mid + 1로 당겨옵니다.
3. 타겟이 mid보다 작다면, 정답은 무조건 왼쪽에 있으므로 right = mid - 1로 줄입니다.

💻 추상화된 템플릿 코드

가장 헷갈리는 '경계값 포함 여부(+1, -1)'를 명확하게 통제하는 순수 템플릿입니다. 특정 값을 찾는 기본형을 넘어, 조건을 만족하는 최댓값을 찾는 '파라메트릭 서치' 뼈대를 소개합니다.

def binary_search_parametric_template(arr, target_condition):
    """
    :param arr: 반드시 오름차순 정렬된 1차원 탐색 공간 (또는 가능한 값의 범위)
    :param target_condition: 결정 함수(Yes/No)에서 통과해야 할 목표치
    """
    left = 0
    right = len(arr) - 1 # 범위를 탐색할 땐 max(arr) 등으로 설정 가능

    # 1. 정답을 기록할 변수
    best_answer = -1 

    # 2. left와 right가 교차하기 전까지 무한 반복
    while left <= right:
        mid = (left + right) // 2

        # 3. [핵심 로직] 현재 mid 값이 우리가 원하는 조건을 만족하는가? (Yes/No 결정 함수)
        if check_condition(arr[mid]) >= target_condition:
            best_answer = arr[mid] # 일단 조건을 만족하므로 정답 후보에 기록
            left = mid + 1         # "더 큰 값도 가능한지 확인해보자!" (오른쪽 탐색)
        else:
            right = mid - 1        # 조건을 만족하지 못하므로 크기를 줄여야 함 (왼쪽 탐색)

    return best_answer

def check_condition(value):
    # 문제의 요구사항에 맞춰 value를 가공했을 때 나오는 결과값을 반환 (O(N) 탐색 등)
    pass

🚨 설계 및 회고

• Off-by-one Error 방어: 무한 루프에 빠지는 것을 막기 위해 left = mid나 right = mid가 아닌, 반드시 + 1, - 1을 해줌으로써 탐색 공간을 확실하게 축소시켜야 합니다.
• 정답 기록 시점 (best_answer): 조건을 만족할 때마다 best_answer에 값을 덮어씌워 두면, while 문이 끝난 후 고민할 필요 없이 가장 최적화된 경계값이 안전하게 남아있게 됩니다.

🚨 [심화 회고] 파라메트릭 서치: 왜 ==로 찾지 않고 부등호로 찾을까?

🤔 의문점: 이분 탐색에서 조건을 만족(target_condition)했을 때 바로 return하지 않고, 왜 부등호(>=, <=)를 사용하며 best_answer에 값을 덮어씌우고 계속 탐색할까? ==로 딱 떨어지는 값을 찾으면 연산이 훨씬 줄어들지 않을까?

💡 깨달음:

1. 정확한 값이 존재하지 않을 수 있다: 파라메트릭 서치는 '딱 맞는 값'을 찾는 것이 아니라, '조건을 만족하는 최댓값(또는 최솟값)'을 찾는 최적화 문제다. 예를 들어 랜선을 105cm로 자르면 11조각, 106cm로 자르면 9조각이 나오는 경우, 정확히 10조각이 나오는 길이는 존재하지 않는다. 이때는 조건을 만족하는(10개 이상) 선에서 가장 최댓값인 105cm를 찾아야 하므로 부등호가 필수적이다.
2. best_answer의 진짜 역할 (Checkpoint 🎯): 조건을 만족했다고 바로 탐색을 멈추면, 그 값이 우리가 낼 수 있는 '최고의 한계치(최댓값)'라는 보장이 없다. 따라서 best_answer에 현재 값을 '안전망'으로 기록해 두고, 포인터(left, right)를 조절하여 한계치까지 계속 욕심을 내어 탐색을 이어가야 한다. while문이 완전히 종료된 후 남아있는 값이 가장 완벽한 최적의 경계값이 된다.

학습 철학 회고 실전에서 itertools를 쓰면 한 줄에 끝날 문제라도, 그 이면에 숨겨진 '상태 공간 트리(State Space Tree)'의 작동 방식을 뼛속까지 이해해야 복잡한 제약 조건이 걸린 시뮬레이션 문제를 통제할 수 있습니다.

📌 개념 요약: 백트래킹은 무엇인가?

모든 가능한 경우의 수를 전부 탐색하는 브루트 포스(Brute Force)를 기반으로 하되, "이 길이 아니면 즉시 뒤로 돌아간다"는 철학을 더한 영리한 완전 탐색입니다.

• 상태 공간 트리 (State Space Tree): 내가 선택할 수 있는 모든 경우의 수를 나무의 가지처럼 펼쳐놓은 가상의 공간입니다.
• 가지치기 (Pruning): 재귀로 트리를 타고 내려가다가, 문제의 조건에 위배되는 순간 더 이상 깊이 들어가지 않고 부모 노드로 돌아(Back)가는 최적화 기법입니다.

💡 동작 원리: 상태의 전이와 복구

백트래킹의 심장은 바로 '상태 복구'에 있습니다. 재귀 함수가 하나의 세계선(Branch)을 탐색하고 부모 노드로 돌아왔을 때, 이전의 행동을 완벽하게 '없던 일'로 만들어주어야 다음 평행 세계(다른 Branch)를 온전하게 탐색할 수 있습니다.

💻 추상화된 템플릿 코드

어떤 순열/조합이나 N-Queen 문제에도 적용할 수 있는 가장 순수한 백트래킹 구조입니다.

def backtracking_template(depth, target_depth, path):
    """
    :param depth: 현재까지 탐색한 깊이 (선택한 개수)
    :param target_depth: 도달해야 하는 목표 깊이 (M개)
    :param path: 현재까지 선택한 경로를 담은 리스트
    """

    # 1. 종료 조건 (Base Condition)
    if depth == target_depth:
        print(path) # 정답 처리 또는 출력
        return

    # 2. 다음 상태 탐색 (상태 공간 트리의 자식 노드들)
    for i in range(1, 5): # 예시: 1부터 4까지의 후보

        # [가지치기 로직 삽입부]
        # if i in path: continue (순열의 경우 중복 방지)

        # 3. 상태 변화 (선택)
        path.append(i)

        # 4. 다음 뎁스로 깊이 파고들기
        backtracking_template(depth + 1, target_depth, path)

        # 5. [핵심] 상태 복구 (원상 복구하여 다음 평행 세계 탐색 준비)
        path.pop() 

# 실행
backtracking_template(0, 3, [])

🚨 설계 및 회고

• append와 pop의 대칭성: 선택을 했으면(append), 재귀가 끝난 직후 반드시 그 선택을 취소(pop)해야 합니다. 이 대칭성이 깨지면 전역 상태가 오염되어 원치 않는 쓰레기 데이터가 누적됩니다.
• 조합(Combination)으로의 변형: 순열이 아니라 조합을 구하고 싶다면, 반복문이 항상 '이전 선택보다 큰 값'부터 시작하도록 재귀 함수에 start 파라미터를 하나 더 넘겨주는 것만으로 우아하게 가지치기를 구현할 수 있습니다.

학습 철학 회고 단순히 미로를 찾고 단지에 번호를 붙이는 1차원적인 풀이를 넘어, '그래프를 남김없이 탐색한다'는 본질적 목표를 어떻게 코드로 추상화할 것인지 고민했습니다. 특정 조건에 휘둘리지 않는, DFS와 BFS의 가장 순수하고 일반화된 뼈대(Skeleton)를 세웁니다.

📌 개념 요약: DFS와 BFS란 무엇인가?

데이터가 거미줄처럼 얽혀있는 그래프(Graph) 공간에서, 모든 정점을 단 한 번씩만, 누락 없이 방문하기 위한 두 가지 상반된 탐색 철학입니다.

• DFS (깊이 우선 탐색): "갈 수 있을 때까지 끝까지 파고든다." 막다른 길에 다다르면 직전 갈림길로 돌아와 다른 길을 찾습니다.
• BFS (너비 우선 탐색): "내 주변부터 꼼꼼하게 살핀다." 시작점에서 가까운 노드들을 모두 방문한 뒤, 점차 탐색 반경을 넓혀갑니다. 최단 거리를 보장하는 강력한 특징이 있습니다.

💡 동작 원리 및 자료구조의 선택

탐색의 순서를 결정하는 것은 결국 '어떤 자료구조(그릇)에 다음 방문할 곳을 담을 것인가'입니다.

1. DFS와 스택(Stack) / 재귀: 방금 발견한 새로운 길을 먼저 가야 하므로, 나중에 들어온 것을 먼저 꺼내는 LIFO(Last-In First-Out) 구조가 필요합니다. 파이썬에서는 별도의 스택 리스트보다는 재귀 함수(Recursion) 자체가 시스템 스택을 이용하므로 가장 우아한 구현 방식이 됩니다.
2. BFS와 큐(Queue): 먼저 발견한 가까운 길을 먼저 가야 하므로, 들어온 순서대로 꺼내는 FIFO(First-In First-Out) 구조가 필요합니다. 파이썬에서는 collections.deque를 사용하여 양방향 입출력을 $O(1)$로 최적화해야 합니다. 리스트의 pop(0)은 $O(N)$이 걸리므로 절대 사용해선 안 됩니다.

💻 추상화된 템플릿 코드

1. BFS (너비 우선 탐색) 템플릿

from collections import deque

def bfs_template(start, graph, visited):
    # 1. 큐 초기화 및 시작점 방문 처리
    queue = deque([start])
    visited[start] = True

    # 2. 큐가 빌 때까지 반복
    while queue:
        # 가장 먼저 들어온(가까운) 노드 꺼내기
        current = queue.popleft()
        print(f"현재 방문한 노드: {current}") # 핵심 로직 수행 위치

        # 3. 인접 노드 탐색
        for next_node in graph[current]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True # [핵심] 큐에 넣을 때 반드시 방문 처리!

2. DFS (깊이 우선 탐색) 템플릿

def dfs_template(current, graph, visited):
    # 1. 현재 노드 방문 처리
    visited[current] = True
    print(f"현재 방문한 노드: {current}") # 핵심 로직 수행 위치

    # 2. 인접 노드 탐색
    for next_node in graph[current]:
        # 아직 방문하지 않은 노드가 있다면, 즉시 그곳으로 깊게 파고들기(재귀 호출)
        if not visited[next_node]:
            dfs_template(next_node, graph, visited)

🚨 설계 및 회고

• 방문 처리(Visited)의 시점: BFS에서 가장 많이 하는 실수가 노드를 큐에서 '꺼낼 때' 방문 처리를 하는 것입니다. 큐에 들어있는 상태에서도 다른 노드에 의해 중복으로 큐에 삽입될 수 있으므로, 반드시 '큐에 넣는 순간(발견한 순간)' 방문 처리를 해야 큐 폭발(메모리 초과)을 막을 수 있습니다.
• 모듈화의 이점: 이 순수한 뼈대 로직을 그대로 유지한 채, print 부분만 count += 1로 바꾸면 연결 요소의 개수를 구하는 문제가 되고, distance[next] = distance[current] + 1로 바꾸면 최단 거리 내비게이션으로 변신합니다.

학습 철학 회고 특정 문제의 꼬인 조건에 맞춰진 코드를 달달 외우는 것은 융통성을 잃게 만듭니다. 알고리즘의 본질을 '언어'로 먼저 이해하고, 그것을 순수한 템플릿으로 추상화한 뒤, 실전 문제의 요구사항에 맞춰 조립하는 '설계 주도형 사고(SOP)'를 다익스트라 알고리즘에 적용해 보았습니다.

📌 개념 요약: 다익스트라는 무엇인가?

"하나의 시작점에서 다른 모든 도착점까지 가는 '최단 경로(최소 비용)'를 찾는 길찾기 내비게이션"입니다. 단, 과거로 돌아가는 길(음수 가중치)은 존재하지 않는다는 강력한 전제가 있습니다.

💡 동작 원리 (핵심 로직)

다익스트라는 소문을 퍼뜨리고 메모장을 수정하는 과정과 같습니다.

1. 가장 싼 곳 먼저 방문 (Greedy): 현재까지 알려진 경로 중 가장 비용이 적게 드는 노드를 우선 방문합니다.
2. 지름길 갱신 (Memoization): 그 노드를 거쳐서 이웃 노드로 가는 비용을 계산합니다. 만약 내가 기존에 알던 길보다 방금 방문한 노드를 거쳐 가는 것이 더 싸다면, 최단 거리 메모장을 갱신합니다.
3. 자료구조의 선택 (Min-Heap): 1번 과정에서 '가장 싼 곳'을 찾기 위해 매번 전체 배열을 뒤지면 $O(V^2)$의 시간이 걸립니다. 이를 해결하기 위해 파이썬의 heapq(우선순위 큐)를 사용하여 탐색 시간을 $O(E \log V)$로 혁신적으로 단축합니다.

🧠 핵심 증명: 큐에서 특정 노드를 처음으로 pop한 순간 왜 '최단 거리'로 확정되는가?

단순히 코드를 암기하는 것을 넘어, 다익스트라 알고리즘의 무결성을 귀류법(Proof by Contradiction)으로 증명합니다. (전제 조건: 모든 간선의 가중치 $w \ge 0$)

1. 가설 설정: 우선순위 큐에서 가장 비용이 작은 노드 $u$가 팝(Pop)되었고, 이때의 기록된 비용을 $d(u)$라고 합시다. 만약 $d(u)$가 진짜 최단 거리가 아니며, 아직 발견하지 못한 더 짧은 진짜 최단 경로 $D(u)$가 존재한다고 가정해 봅니다. 즉, $D(u) < d(u)$ 입니다.
2. 진짜 최단 경로 추적: 출발지 $S$에서 $u$로 가는 진짜 최단 경로를 따라가다 보면, 이미 방문이 확정된 노드 그룹을 벗어나 가장 처음 마주치는 '미확정 노드' $x$가 반드시 존재합니다.
3. 비용의 대소 관계: 출발지에서 이 중간 기착지 $x$까지 도달하는 비용을 $d(x)$라고 합시다. 그래프의 모든 가중치는 0 이상이므로, $x$를 거쳐 종착지 $u$로 가는 동안 거리는 무조건 늘어나거나 최소한 유지됩니다. 따라서 $d(x) \le D(u)$ 가 성립합니다.
4. 모순 발생: 위 수식들을 연결하면 $d(x) \le D(u) < d(u)$ 가 되며, 결론적으로 $d(x) < d(u)$ 가 도출됩니다.
5. 결론: 우선순위 큐는 '가장 값이 작은 노드'를 먼저 꺼내는 자료구조입니다. 만약 $d(x) < d(u)$ 가 사실이라면, 큐에서는 $u$가 아니라 $x$가 먼저 팝(Pop)되었어야 합니다. 이는 "노드 $u$가 큐에서 가장 먼저 꺼내졌다"는 현재의 팩트와 정면으로 충돌하므로 모순입니다. 따라서 초기 가설은 거짓이 되며, "큐에서 꺼내진 노드 $u$의 비용 $d(u)$보다 더 짧은 경로는 존재할 수 없다"는 것이 수학적으로 증명됩니다.

💻 추상화된 템플릿 코드

어떤 문제의 엣지 케이스(Edge Case)에도 오염되지 않은, 가장 범용적인 순수 파이썬 다익스트라 뼈대입니다.

import heapq

def dijkstra_template(start, graph, n):
    INF = int(1e9) # 무한대
    distance = [INF] * (n + 1) # 메모장 초기화

    pq = []
    # 힙은 첫 번째 원소 기준으로 정렬되므로 반드시 (비용, 노드) 순으로 삽입
    heapq.heappush(pq, (0, start)) 
    distance[start] = 0

    while pq:
        current_cost, current_node = heapq.heappop(pq)

        # [방어 로직] 이미 처리된 적이 있는 노드라면 무시 (지연 삭제)
        if distance[current_node] < current_cost:
            continue

        for weight, next_node in graph[current_node]:
            cost = current_cost + weight # 거쳐서 가는 총 비용

            # [핵심] 거쳐가는 것이 기존 경로보다 싸다면 (지름길 발견)
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(pq, (cost, next_node))

    return distance

🚨 설계 및 회고

• 생명주기 관리: distance 배열과 pq를 전역 변수로 두지 않고 함수 내부에 가두어, 여러 번의 테스트 케이스가 주어져도 이전 데이터가 섞이는 치명적인 사이드 이펙트(Side Effect)를 원천 차단했습니다.
• 튜플 정렬의 원리: 파이썬 heapq의 특성을 살려 (비용, 도착점) 순서로 튜플을 구성함으로써, 별도의 정렬 함수 구현 없이 자연스럽게 최소 비용 노드가 추출되도록 설계했습니다.
• BFS와의 비교: 결국 다익스트라 알고리즘은 BFS의 업그레이드 버전입니다. 시작 노드에서 다음 노드들을 전부 큐에 넣고, 다 넣으면 그 노드의 인접한 노드들을 또 큐에 넣는 완벽한 BFS 형식입니다. 하지만 여기서 heapq를 사용함으로써, 맹목적인 탐색이 아닌 비용이 최소인 인접 노드를 먼저 탐색하도록 통제하는 점이 가장 중요한 차이점입니다.

🤔 심화 고찰: 왜 힙에 중복 데이터 푸시를 사전에 차단하지 않을까? (Lazy Deletion)

다익스트라 알고리즘을 설계하다 보면 아주 자연스럽게 다음과 같은 엔지니어링적 의문이 듭니다. *"불필요한 낡은 데이터가 힙(Heap)에 들어가는 것 자체를 사전에 차단하면 큐가 가벼워져서 시간 복잡도를 더 줄일 수 있지 않을까?"*

이 의문은 자료구조 최적화의 핵심 쟁점이며, 작성된 템플릿 코드에는 이 딜레마를 해결하기 위한 의도적인 트레이드오프(Trade-off)가 숨어있습니다.

1. 이미 최단 거리가 확정된 노드는 애초에 푸시되지 않는다 "이미 팝(Pop)되어 최단 거리가 고정된 노드는 더 이상 힙에 넣지 말자"는 완벽한 논리는 아래의 단 한 줄의 코드가 이미 수행하고 있습니다.

if cost < distance[next_node]:

어떤 노드가 이미 큐에서 꺼내져(Pop) 최단 거리가 영구 확정되었다면, 그 노드의 distance 메모장 값은 수학적으로 도달 가능한 '절대적 최솟값' 상태입니다. 따라서 나중에 탐색을 돌다가 다른 길을 통해 이 노드로 다시 진입하려 해도, 그 새로운 비용(cost)은 무조건 기존 최솟값보다 크거나 같을 수밖에 없습니다. 결과적으로 조건문이 False가 되어 이미 확정된 노드는 힙에 두 번 다시 푸시되지 않습니다.

2. 자료구조의 물리적 한계와 '지연 삭제(Lazy Deletion)' 전략 그렇다면 힙에 중복된 낡은 데이터가 쌓이는 진짜 이유는 무엇일까요? 바로 '아직 팝되지 않고 힙에서 대기 중인 노드'에 대해 더 짧은 지름길을 발견했을 때 발생합니다.

이때 중복 푸시를 막으려면, 힙 내부를 뒤져서 대기 중이던 낡은 경로 값을 찾아 지우거나 새 값으로 갱신(Decrease-key)해야 합니다.

• 힙 탐색의 비용: 일반적인 우선순위 큐(이진 힙)는 최솟값을 뽑는 데는 최적화되어 있지만, 내부의 특정 원소를 찾는 데는 최악의 경우 $O(V)$ (V는 노드 수)의 시간이 걸립니다.
• 새로운 값 푸시 비용: 반면, 낡은 값을 그대로 둔 채 새로운 값을 힙의 말단에 밀어 넣는 데는 고작 $O(\log V)$의 시간밖에 걸리지 않습니다.

즉, 중복을 막겠다고 매번 $O(V)$의 막대한 비용을 지불하며 힙을 뒤지는 것보다, 그냥 $O(\log V)$로 중복 데이터를 밀어 넣는 것이 전체 시스템 관점에서는 압도적으로 효율적입니다. 어차피 힙의 특성상 값이 더 작은 '진짜 최단 경로'가 먼저 팝되어 메모장을 갱신할 것입니다.

이후 힙 구석에 방치되어 있던 '낡은 데이터'가 뒤늦게 팝되어 나오면, 우리는 이미 준비해 둔 방어 로직(if distance[current_node] < current_cost: continue)을 통해 단 $O(1)$의 비용으로 무시하고 폐기(Discard)해 버리면 됩니다. 이것이 바로 컴퓨터 과학에서 널리 쓰이는 지연 삭제(Lazy Deletion) 아키텍처입니다.