알고리즘 선택 기준

PJPJ·2026년 8월 17일

CodingTest

Coding_Test

목록 보기

7/8

< 이분 탐색 >

💡 요약: "이분 탐색이네!" 판단 시나리오

"어? 탐색할 범위나 숫자가 10억 단위로 엄청 크네?"
"구해야 하는 답(K)을 하나 딱 정했을 때, 이게 조건(Limit)에 맞는지 O/X 판정 함수를 짜기 쉬운가?"
"K가 커질수록 결과도 한쪽으로만 변해서 [X, X, O, O, O] 형태의 경계선이 생기는가?"

1. 범위를 나타내는 입력값(N, Limit 등)이 매우 큼

가장 먼저 눈에 띄는 1차 신호입니다.

보통 for문으로 하나씩 다 검사(선형 탐색)하려면 입력값이 $10^5$ (10만) 내외여야 안전합니다.
하지만 문제 조건에서 범위나 제한 조건의 숫자가 $10^8$ (1억) ~ $10^{18}$ 처럼 말도 안 되게 크게 주어진다면, $O(N)$ 풀이는 무조건 시간 초과가 납니다.
$O(\log N)$ 알고리즘인 이분 탐색을 쓰라는 강력한 힌트입니다.

2. 정답(X)이 커질수록 결과(Y)가 한쪽 방향으로만 변함 (단조성)

이분 탐색을 적용하기 위한 가장 결정적인 필수 조건입니다.

"X(내가 찾는 값)를 높이면, Y(결과 값)는 계속 증가하거나 계속 감소한다"는 연관성이 명확해야 합니다.
예컨대 퍼즐 게임 챌린지 문제처럼:
숙련도(X) $\uparrow$ $\rightarrow$ 총 소요 시간(Y) $\downarrow$ (무조건 감소)

만약 X를 올렸을 때 Y가 커졌다 작아졌다 들쑥날쑥(비단조성)하다면 이분 탐색을 절대 쓸 수 없습니다.

3. "최댓값/최솟값을 구하라"를 "O/X 문제"로 바꿀 수 있음 (파라메트릭 서치)

코딩 테스트 이분 탐색 문제의 90%는 이 유형입니다. 질문의 관점을 뒤집는 것입니다.

원래 문제의 질문	이분 탐색으로 바꾸는 질문 (O/X 검사)
"제한시간 내에 풀어내는 최소 숙련도는 얼마인가?"	"숙련도가 K일 때, 제한시간 내에 풀 수 있는가? (O / X)"
"나무를 M미터 가져가기 위한 톱날 높이의 최댓값은?"	"톱날 높이가 K일 때, 나무 M미터를 얻을 수 있는가? (O / X)"

원래 질문("최댓값/최솟값을 직접 찾아라")은 풀기 어렵습니다.
하지만 "숫자 K 하나 정해줄 테니까, 이거 조건 만족해 안 해?"라고 묻는 O/X 검사 함수(isValid(K))를 만들기는 훨씬 쉽습니다.
이렇게 O/X 판정 함수를 만들 수 있고, 결과가 [X, X, X, O, O, O]처럼 경계선을 기준으로 나뉜다면 무조건 이분 탐색 문제입니다.

4. 파라메트릭 서치 템플릿 (★가장 중요)

"조건을 만족하는 최댓값 또는 최솟값"을 찾을 때 사용하는 템플릿입니다.

def solution(target_limit, data):
    # 1. 탐색 범위 설정 (문제에 맞춰 최소/최대 범위 지정)
    left = 1
    right = max(data)  # 또는 10**9 등 문제의 최대 범위
    
    answer = 0
    
    # 2. O/X 판정 함수 (mid 값으로 조건 만족 여부 확인)
    def is_valid(mid):
        # [문제 조건에 맞게 계산 로직 작성]
        total = 0
        for val in data:
            total += val // mid  # 예시 계산
            
        return total >= target_limit  # 조건을 만족하면 True, 아니면 False

    # 3. 이분 탐색 수행
    while left <= right:
        mid = (left + right) // 2
        
        if is_valid(mid):
            answer = mid        # 조건 만족 시 정답 기록!
            
            # [최댓값을 찾을 때]: 더 큰 값도 가능한지 오른쪽 탐색
            left = mid + 1
            
            # [최솟값을 찾을 때]: 더 작은 값도 가능한지 왼쪽 탐색
            # right = mid - 1
            
        else:
            # 조건 불만족 시 반대쪽 범위를 줄임
            right = mid - 1     # (최대 찾기일 때)
            # left = mid + 1    # (최소 찾기일 때)
            
    return answer

💡 살 붙이는 포인트

is_valid(mid) 함수: 이 부분이 문제의 핵심입니다. "숙련도가 mid일 때 시간 내에 풀 수 있는가?", "톱날 높이가 mid일 때 나무를 충분히 가져갈 수 있는가?"처럼 mid를 인자로 받아 True/False를 반환하는 함수를 구현하면 됩니다.
최댓값 vs 최솟값 방향 조절:
최댓값 구하기: 조건 만족 시 answer = mid, 더 크게 해보기 위해 left = mid + 1
최솟값 구하기: 조건 만족 시 answer = mid, 더 작게 해보기 위해 right = mid - 1

5. 기본 이분 탐색 템플릿

이미 정렬된 배열에서 '특정 값 Target이 어디에 있는지' 찾을 때 쓰는 기본 형태입니다.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # 찾았을 때의 인덱스 반환
            
        elif arr[mid] < target:
            left = mid + 1  # target이 오른쪽 구역에 있음
        else:
            right = mid - 1 # target이 왼쪽 구역에 있음
            
    return -1  # 찾지 못했을 때

📌 요약: 이분 탐색 템플릿 외우기 체크리스트

left <= right: while문 조건식에 <= (등호) 꼭 챙기기
mid = (left + right) // 2: 중간값 계산
left = mid + 1 / `right = mid - 1: 이동 시 반드시 +1, -1`을 해주어야 무한 루프에 빠지지 않음
is_valid(mid) 판정 함수 작성: 파라메트릭 서치 풀이의 핵심 로직

< BFS >

💡 요약: "BFS" 한 눈에 보기

구분	BFS (너비 우선 탐색)
핵심 질문	"A에서 B까지 가는 최단 경로 / 최소 시간은?"
데이터 구조	2차원 격자, 그래프, 상태 트리의 연결 관계
탐색 방식	`deque`(큐)를 써서 한 단계씩 동심원으로 확장
주요 키워드	상하좌우, 퍼짐, 미로 탈출, 최단 거리, 덩어리

1. "최단 거리" 또는 "최소 횟수"를 구하라고 할 때 (★가장 결정적!)

BFS의 가장 강력한 특징은 가장 먼저 목적지에 도달하는 경로가 무조건 최단 경로라는 점입니다.

질문 패턴: "목적지까지 가는 최소 이동 횟수는?", "모든 영역을 방문하는 최소 시간은?", "가장 빠른 경로는?"
이유: BFS는 깊이(거리) 1짜리를 다 찾고, 그다음 거리 2짜리를 찾고, 거리 3짜리를 찾는 식으로 동심원을 그리며 확장합니다. 따라서 목적지에 '처음 닿는 순간'이 무조건 최단 거리입니다.
※ 주의: 간선(이동)의 가중치가 모두 같을 때(예: 한 칸 이동할 때마다 1초씩 소요)만 BFS를 쓸 수 있습니다.

2. 2차원 격자(지지도/맵)에서 "사방 확장"이나 "퍼짐"이 발생할 때

2차원 배열 상에서 물리적으로 무언가가 퍼져나가는 상황은 99% BFS 문제입니다.

대표적인 상황:
익은 토마토 주변으로 안 익은 토마토가 익어가는 문제
바이러스나 미세먼지가 매초 사방(상하좌우)으로 퍼져나가는 문제
물이 차오르거나 불이 번져나가는 문제

특징: 여러 지점에서 동시에 퍼져나가는 상황을 구현할 때 deque에 시작점들을 한 번에 다 넣어두고 BFS를 돌리면 깔끔하게 해결됩니다.

3. "연결된 덩어리(영역)"의 개수나 크기를 세라고 할 때

그래프나 2차원 배열에서 서로 붙어있는 무리를 찾는 문제(Connected Components)입니다.

대표적인 상황:
석유 시추: 연결된 석유 덩어리의 크기 구하기
단지 번호 붙이기: 아파트 단지별 집의 개수 구하기
섬의 개수 구하기: 바다로 둘러싸인 땅 덩어리 개수 세기

※ 참고: 단순 덩어리 세기는 DFS로도 풀 수 있지만, 재귀 깊이 제한(RecursionLimit) 에러 위험이 없는 BFS를 선호하는 경우가 많습니다.

4. "상태 변화"의 최소 단계를 구할 때 (격자판이 아닌 문제)

꼭 2차원 지도가 아니더라도 "어떤 상태 A에서 상태 B로 바꾸는 최소 연산 횟수"를 물어볼 때도 BFS입니다.

대표적인 상황:
단어 변환: 한 번에 한 글자씩만 바꿔서 목표 단어로 만드는 최소 단계
숨바꼭질: 현재 위치 $X$ 에서 $X+1$ , $X-1$ , $2X$ 로 이동해서 동생을 찾는 최소 시간
퍼즐 맞추기: 3x3 슬라이딩 퍼즐을 완성하는 최소 이동 횟수

5. BFS 기본 템플릿 (큐 + 반복문)

최단 거리, 최소 시간, 퍼짐 문제를 풀 때 사용하는 템플릿입니다.

from collections import deque

def bfs(start_r, start_c, board):
    n = len(board)
    m = len(board[0])
    
    # 1. 방문 여부 체크 배열 (필요시 숫자로 거리를 기록: visited[r][c] = distance)
    visited = [[False] * m for _ in range(n)]
    
    # 2. 큐 생성 및 시작점 삽입
    queue = deque([(start_r, start_c)])
    visited[start_r][start_c] = True
    
    # 3. 4방향 이동 (상, 하, 좌, 우)
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    # 4. 큐가 빌 때까지 탐색
    while queue:
        r, c = queue.popleft()
        
        # [문제에 따른 처리 지점]: 현재 위치에서 작업 수행 (예: cnt += 1)
        
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            
            # 격자 범위 내인지 확인
            if 0 <= nr < n and 0 <= nc < m:
                # 이동 가능 조건 (벽이 아니고 + 방문 안 함)
                if board[nr][nc] != 0 and not visited[nr][nc]:
                    visited[nr][nc] = True
                    queue.append((nr, nc))

💡 살 붙이는 포인트

최단 거리/시간을 구할 때: visited를 False 대신 0으로 초기화하고, visited[nr][nc] = visited[r][c] + 1로 거리를 1씩 늘려가며 저장합니다.
여러 지점에서 동시에 퍼질 때: while문 실행 전에 큐에 시작점들을 for문으로 한 번에 다 쏟아 넣고 시작합니다.

📌 요약: 외워야 할 4가지 필수 요소

dr = [-1, 1, 0, 0], `dc = [0, 0, -1, 1]`: 상하좌우 방향 배열.
0 <= nr < n and 0 <= nc < m: 인덱스 에러 방지용 범위 체크 조건문.
visited 처리: 큐에 넣을 때(BFS) 또는 함수에 들어갈 때(DFS) 방문 체크.

< DFS >

💡 DFS vs BFS 한 눈에 비교하기

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
구현 방식	재귀 함수 또는 스택(Stack)	큐(Queue, `deque`)
탐색 방식	막힐 때까지 끝까지 깊게 탐색	시작점에서 동심원(넓게)으로 확장
대표 목적	모든 경우의 수 탐색, 백트래킹, 경로의 조건 검사	최단 거리 / 최소 시간 구하기
메모리 특징	트리의 높이(깊이)만큼 메모리 사용	큐에 넣는 동시 방문 수만큼 메모리 사용

1. "모든 경로/모든 경우의 수"를 전부 탐색해야 할 때 (★가장 결정적!)

BFS는 최단 경로를 찾으면 탐색을 중간에 끝내버리지만, DFS는 모든 가짓수를 다 확인해야 하는 문제에 적합합니다.

질문 패턴:
"A 지점에서 B 지점으로 가는 모든 경로의 개수를 구하라."
"주어진 숫자로 만들 수 있는 모든 조합/순열을 구하라."

이유: 한 경로를 끝까지 탐색하고 돌아오면서(Backtracking) 상태를 원상복구하기 때문에, 모든 가능한 경우의 수를 차례대로 탐색하기 매우 편리합니다.

2. "경로의 특징이나 조건"을 유지하면서 이동해야 할 때

"A에서 B로 가는데, 지나온 칸들의 합이 K여야 한다"처럼 지나온 경로의 기록(상태)이 중요한 문제입니다.

예시:
지나온 경로에 특정 방문 순서나 선택했던 값들을 리스트에 담아 다니며 검사해야 할 때
트리의 루트(뿌리) 노드부터 리프(잎) 노드까지의 경로상 가중치 합을 구할 때

이유: DFS는 재귀 함수를 사용하므로, 함수의 파라미터(인자)에 현재까지의 경로 정보를 넘겨주며 탐색하기가 매우 쉽습니다.

3. 그래프/트리에서 "깊이(Depth)나 구조" 자체가 중요할 때

2차원 격자판이 아니라 트리(Tree)나 순일성이 없는 그래프 구조를 탐색할 때 DFS가 훨씬 직관적입니다.

대표적인 상황:
트리 순회: 전위(Preorder), 중위(Inorder), 후위(Postorder) 순회
사이클(Cycle) 찾기: 그래프 내에 순환 고리가 존재하는지 확인
위상 정렬(Topological Sort): 작업의 선후 관계가 정해져 있을 때 차례대로 정렬

4. 단순 "연결된 덩어리(영역)" 세기 (BFS와 공통)

석유 시추, 섬의 개수, 단지 번호 붙이기처럼 "연결되어 있는 영역 하나를 싹 지우거나 카운트"할 때는 DFS와 BFS 둘 다 사용 가능합니다.

DFS로 풀면 코드가 몇 줄 안 되고 매우 간결해집니다.
※ 단, 파이썬에서는 재귀 깊이 제한(sys.setrecursionlimit)을 늘려주지 않으면 에러가 날 수 있어 BFS를 더 선호하기도 합니다.

5. DFS 기본 템플릿 (재귀 함수)

모든 경로 탐색, 연결된 영역 지우기, 백트래킹에 사용하는 템플릿입니다.

import sys
# 파이썬 재귀 깊이 제한 해제 (DFS 필수!)
sys.setrecursionlimit(10**6)

def dfs(r, c, board, visited):
    n = len(board)
    m = len(board[0])
    
    # 1. 현재 위치 방문 처리
    visited[r][c] = True
    
    # [문제에 따른 처리 지점]: 현재 위치에서 작업 수행
    
    # 2. 4방향 이동
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        
        # 격자 범위 내인지 확인
        if 0 <= nr < n and 0 <= nc < m:
            # 이동 가능 조건
            if board[nr][nc] != 0 and not visited[nr][nc]:
                dfs(nr, nc, board, visited)

💡 살 붙이는 포인트

백트래킹(모든 경우의 수 조합)을 할 때: dfs()를 호출한 직후에 visited[nr][nc] = False로 다시 방문을 해제해 주는 한 줄을 추가합니다.

📌 요약: 외워야 할 4가지 필수 요소

`sys.setrecursionlimit(106)`**: DFS 쓸 때는 무조건 맨 위에 적기.
dr = [-1, 1, 0, 0], `dc = [0, 0, -1, 1]`: 상하좌우 방향 배열.
0 <= nr < n and 0 <= nc < m: 인덱스 에러 방지용 범위 체크 조건문.
visited 처리: 큐에 넣을 때(BFS) 또는 함수에 들어갈 때(DFS) 방문 체크.

<시간,날짜 문제>

코딩 테스트에서 날짜, 시간, 요일 관련 문제가 나오면 "가장 작은 단위(초, 분, 일)로 통일해서 단일 숫자로 바꾸는 것"이 정석이자 가장 안전한 풀이법입니다.

복잡하게 연/월/일, 시/분/초를 따로 가지고 다니면서 if문으로 60초가 넘는지, 12달이 넘는지 분기 처리를 하면 오답이 나기 매우 쉽기 때문입니다.

💡 상황별 단위 통일 공식 3가지

1. "시, 분, 초" 문제 $\rightarrow$ '초(Second)'로 통일

아날로그 시계, 기차 시간표, 영상 재생 구간(프로그래머스 '볼드 타임' 등) 문제에 적용됩니다.

공식: $\text{총 초} = (\text{Hour} \times 3600) + (\text{Minute} \times 60) + \text{Second}$
예시 함수:

def to_seconds(time_str):
    h, m, s = map(int, time_str.split(':'))
    return h * 3600 + m * 60 + s

2. "시, 분" 문제 $\rightarrow$ '분(Minute)'으로 통일

주차 요금 계산, 영화 상영 시간, 대중교통 배차 간격 문제에 적용됩니다.

공식: $\text{총 분} = (\text{Hour} \times 60) + \text{Minute}$
예시 함수:

def to_minutes(time_str):
    h, m = map(int, time_str.split(':'))
    return h * 60 + m

3. "연, 월, 일 / 요일" 문제 $\rightarrow$ '일(Day)'로 통일

개인정보 유효기간, D-Day 계산, 2016년 요일 맞추기 문제 등에 적용됩니다.

달의 길이가 고정일 때 (예: 모든 달은 28일):
$\text{총 일수} = (\text{Year} \times 12 \times 28) + (\text{Month} \times 28) + \text{Day}$

달의 길이가 제각각일 때 (예: 1월=31일, 2월=28일, 3월=31일...):
각 달의 일수를 담은 배열 months = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]을 만든 뒤, 누적 합으로 구해줍니다.
요일 구하기: 기준일로부터 전체 지난 일수를 구한 뒤 총 일수 % 7 (나머지 연산)을 쓰면 요일이 바로 나옵니다.

📌 요약: 시간/날짜 문제 접근 공식

변환 함수 만들기: 입력을 받자마자 정수 1개(total_time)로 바꾸기
단순 연산: 정수끼리 빼기(끝 시간 - 시작 시간), 더하기(유효기간), 비교(>=) 수행
원래 형태 복원 (필요 시):

Hour = total_seconds // 3600
Minute = (total_seconds % 3600) // 60
Second = total_seconds % 60

PJPJ

이전 포스트

변환

다음 포스트

알고리즘 선택 기준

Coding_Test

< 이분 탐색 >

💡 요약: "이분 탐색이네!" 판단 시나리오

1. 범위를 나타내는 입력값(N, Limit 등)이 매우 큼

2. 정답(X)이 커질수록 결과(Y)가 한쪽 방향으로만 변함 (단조성)

3. "최댓값/최솟값을 구하라"를 "O/X 문제"로 바꿀 수 있음 (파라메트릭 서치)

4. 파라메트릭 서치 템플릿 (★가장 중요)

💡 살 붙이는 포인트

5. 기본 이분 탐색 템플릿

📌 요약: 이분 탐색 템플릿 외우기 체크리스트

< BFS >

💡 요약: "BFS" 한 눈에 보기

1. "최단 거리" 또는 "최소 횟수"를 구하라고 할 때 (★가장 결정적!)

2. 2차원 격자(지지도/맵)에서 "사방 확장"이나 "퍼짐"이 발생할 때

3. "연결된 덩어리(영역)"의 개수나 크기를 세라고 할 때

4. "상태 변화"의 최소 단계를 구할 때 (격자판이 아닌 문제)

5. BFS 기본 템플릿 (큐 + 반복문)

💡 살 붙이는 포인트

📌 요약: 외워야 할 4가지 필수 요소

< DFS >

💡 DFS vs BFS 한 눈에 비교하기

1. "모든 경로/모든 경우의 수"를 전부 탐색해야 할 때 (★가장 결정적!)

2. "경로의 특징이나 조건"을 유지하면서 이동해야 할 때

3. 그래프/트리에서 "깊이(Depth)나 구조" 자체가 중요할 때

4. 단순 "연결된 덩어리(영역)" 세기 (BFS와 공통)

5. DFS 기본 템플릿 (재귀 함수)

💡 살 붙이는 포인트

📌 요약: 외워야 할 4가지 필수 요소

<시간,날짜 문제>

💡 상황별 단위 통일 공식 3가지

1. "시, 분, 초" 문제 $\rightarrow$ '초(Second)'로 통일

2. "시, 분" 문제 $\rightarrow$ '분(Minute)'으로 통일

3. "연, 월, 일 / 요일" 문제 $\rightarrow$ '일(Day)'로 통일

📌 요약: 시간/날짜 문제 접근 공식

변환

SQL

0개의 댓글

알고리즘 선택 기준

Coding_Test

< 이분 탐색 >

💡 요약: "이분 탐색이네!" 판단 시나리오

1. 범위를 나타내는 입력값(N, Limit 등)이 매우 큼

2. 정답(X)이 커질수록 결과(Y)가 한쪽 방향으로만 변함 (단조성)

3. "최댓값/최솟값을 구하라"를 "O/X 문제"로 바꿀 수 있음 (파라메트릭 서치)

4. 파라메트릭 서치 템플릿 (★가장 중요)

💡 살 붙이는 포인트

5. 기본 이분 탐색 템플릿

📌 요약: 이분 탐색 템플릿 외우기 체크리스트

< BFS >

💡 요약: "BFS" 한 눈에 보기

1. "최단 거리" 또는 "최소 횟수"를 구하라고 할 때 (★가장 결정적!)

2. 2차원 격자(지지도/맵)에서 "사방 확장"이나 "퍼짐"이 발생할 때

3. "연결된 덩어리(영역)"의 개수나 크기를 세라고 할 때

4. "상태 변화"의 최소 단계를 구할 때 (격자판이 아닌 문제)

5. BFS 기본 템플릿 (큐 + 반복문)

💡 살 붙이는 포인트

📌 요약: 외워야 할 4가지 필수 요소

< DFS >

💡 DFS vs BFS 한 눈에 비교하기

1. "모든 경로/모든 경우의 수"를 전부 탐색해야 할 때 (★가장 결정적!)

2. "경로의 특징이나 조건"을 유지하면서 이동해야 할 때

3. 그래프/트리에서 "깊이(Depth)나 구조" 자체가 중요할 때

4. 단순 "연결된 덩어리(영역)" 세기 (BFS와 공통)

5. DFS 기본 템플릿 (재귀 함수)

💡 살 붙이는 포인트

📌 요약: 외워야 할 4가지 필수 요소

<시간,날짜 문제>

💡 상황별 단위 통일 공식 3가지

1. "시, 분, 초" 문제 →\rightarrow→ '초(Second)'로 통일

2. "시, 분" 문제 →\rightarrow→ '분(Minute)'으로 통일

3. "연, 월, 일 / 요일" 문제 →\rightarrow→ '일(Day)'로 통일

📌 요약: 시간/날짜 문제 접근 공식

변환

SQL

0개의 댓글

1. "시, 분, 초" 문제 $\rightarrow$ '초(Second)'로 통일

2. "시, 분" 문제 $\rightarrow$ '분(Minute)'으로 통일

3. "연, 월, 일 / 요일" 문제 $\rightarrow$ '일(Day)'로 통일