7일 자료구조·알고리즘(Python) 총몰입 프로토콜

목표는 “모든 알고리즘을 아는 것”이 아니라, 카카오 계열사 코딩테스트에서 자주 나오는 유형을 빠르게 분류하고 제한 시간 내 구현하는 것입니다.

1. Pareto 집중 범위

반드시 익힐 20%

1. 구현·시뮬레이션

   • 문자열 처리, 조건 분기, 좌표 이동
   • 정렬·그리디를 결합한 구현
   • 시간복잡도 계산

2. 핵심 자료구조

   • list, dict, set, deque, heapq
   • 스택·큐·우선순위 큐
   • 누적합, 투 포인터, 슬라이딩 윈도우

3. 탐색

   • DFS/BFS
   • 격자 그래프
   • 방문 처리, 최단거리
   • 이분 탐색

4. 그래프

   • 인접 리스트
   • 연결 요소
   • 위상 정렬
   • 다익스트라
   • 유니온 파인드

5. DP

   • 1차원·2차원 DP
   • 상태 정의
   • 점화식
   • 메모이제이션과 바텀업
   • 배낭·격자·문자열 DP 기초

6. 문제 해결 프로세스

   • 문제 유형 분류
   • 제한 조건으로 알고리즘 결정
   • 예제 외 반례 만들기
   • 시간복잡도 검증
   • 디버깅 템플릿화

이번 주에 버릴 것

고급 세그먼트 트리, KMP, 네트워크 플로우, 고급 기하, suffix array, 복잡한 조합론은 제외합니다. 이미 자주 풀어본 유형이 아니라면 투자 대비 효율이 낮습니다.

---

2. 하루 운영 규칙

하루 최소 8시간을 기준으로 합니다.

• 오전: 3시간 개념
• 오후: 4시간 문제 풀이
• 저녁: 1~2시간 복습
• 한 문제에 45분 이상 막히지 않기
• 풀이를 본 뒤 반드시 빈 화면에서 재구현
• 틀린 문제는 “왜 틀렸는지”를 한 문장으로 기록

문제 풀이 순서는 다음과 같습니다.

1. 제한 조건 확인
2. 입력·출력 구조 요약
3. 가능한 알고리즘 2개 이상 후보화
4. 시간복잡도 계산
5. 작은 반례 작성
6. 구현
7. 테스트
8. 실패 원인 기록

---

3. 7일 일정

Day 1 — 복잡도, 자료구조, 구현 기본기

시간	학습 내용
오전	Big-O, 정렬, 해시, 스택, 큐, deque, heapq, Python 입력 최적화 학습
오후	구현 3문제, 해시 2문제, 스택·큐 2문제, 정렬 2문제
저녁	각 자료구조의 연산 복잡도 암기. 오늘 푼 문제를 풀이 없이 1개 재구현

반드시 구현할 템플릿

import sys
input = sys.stdin.readline

from collections import deque

q = deque([start])
while q:
    x = q.popleft()

import heapq

heap = []
heapq.heappush(heap, value)
value = heapq.heappop(heap)

문제 유형

• 완주하지 못한 선수
• 전화번호 목록
• 기능 개발
• 같은 숫자는 싫어
• 가장 큰 수
• 체육복
• 문자열 압축
• 신규 아이디 추천

목표: 문제를 읽고 5분 안에 자료구조와 접근법을 선택합니다.

---

Day 2 — 완전탐색, 재귀, 백트래킹, 그리디

시간	학습 내용
오전	순열·조합, 부분집합, 재귀 종료 조건, 백트래킹 가지치기, 그리디의 정당성
오후	완전탐색 3문제, 백트래킹 3문제, 그리디 3문제
저녁	재귀 호출 구조를 손으로 추적하고, 오답 문제 2개 재풀이

핵심 템플릿

def dfs(depth):
    if depth == target:
        # 정답 처리
        return

    for choice in choices:
        if visited[choice]:
            continue

        visited[choice] = True
        path.append(choice)

        dfs(depth + 1)

        path.pop()
        visited[choice] = False

문제 유형

• 모음사전
• 카펫
• 전력망을 둘로 나누기
• 소수 만들기
• 타겟 넘버
• 피로도
• 모험가 길드
• 큰 수 만들기
• 구명보트

주의: 그리디는 “현재 최선”만으로 풀지 말고, 왜 최적해가 되는지 한 문장으로 설명할 수 있어야 합니다.

---

Day 3 — DFS/BFS와 격자 그래프

시간	학습 내용
오전	그래프 표현, DFS/BFS 차이, 방문 배열, 격자 탐색, 연결 요소, BFS 최단거리
오후	격자 BFS 4문제, 연결 요소 2문제, DFS 2문제
저녁	DFS와 BFS 템플릿을 빈 화면에서 각각 작성. 거리 배열 사용 연습

BFS 템플릿

from collections import deque

def bfs(start):
    q = deque([start])
    visited[start] = True

    while q:
        current = q.popleft()

        for nxt in graph[current]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)

격자 BFS 템플릿

from collections import deque

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

q = deque([(sr, sc)])
dist[sr][sc] = 0

while q:
    r, c = q.popleft()

    for dr, dc in directions:
        nr, nc = r + dr, c + dc

        if not (0 <= nr < n and 0 <= nc < m):
            continue
        if grid[nr][nc] == 0 or dist[nr][nc] != -1:
            continue

        dist[nr][nc] = dist[r][c] + 1
        q.append((nr, nc))

문제 유형

• 네트워크
• 단지번호붙이기
• 미로 탈출
• 게임 맵 최단거리
• 카카오 프렌즈 컬러링북
• 아이템 줍기
• 연구소
• 바이러스

목표: 격자 문제를 보면 방향 배열 + 범위 확인 + 방문 처리를 자동으로 떠올립니다.

---

Day 4 — 이분 탐색, 누적합, 투 포인터, 우선순위 큐

시간	학습 내용
오전	이분 탐색의 조건, 매개변수 탐색, 누적합, 투 포인터, 슬라이딩 윈도우, 힙
오후	이분 탐색 3문제, 누적합·투 포인터 3문제, 힙 3문제
저녁	각 유형의 “언제 사용하는가”를 문제 조건과 연결해 정리

이분 탐색 템플릿

left, right = 0, max_value

while left <= right:
    mid = (left + right) // 2

    if possible(mid):
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

문제 유형

• 입국심사
• 징검다리
• 예산
• 숫자 카드
• 두 수의 합
• 부분합
• 연속된 부분 수열의 합
• 더 맵게
• 디스크 컨트롤러
• 이중우선순위큐

판별 기준:

• 정렬된 배열에서 값을 찾는다 → 이분 탐색
• 연속 구간의 합·개수를 구한다 → 누적합 또는 투 포인터
• 매 순간 최솟값·최댓값을 꺼낸다 → 힙
• 답의 범위를 정하고 가능한가?를 판정한다 → 매개변수 탐색

---

Day 5 — 그래프 심화: 다익스트라, 유니온 파인드, 위상 정렬

시간	학습 내용
오전	다익스트라, 유니온 파인드, 위상 정렬의 적용 조건과 템플릿
오후	다익스트라 3문제, 유니온 파인드 2문제, 위상 정렬 2문제
저녁	그래프 문제 3개를 보고 유형만 30초 안에 분류

다익스트라 템플릿

import heapq

INF = 10**18
distance = [INF] * (n + 1)
distance[start] = 0

heap = [(0, start)]

while heap:
    cost, node = heapq.heappop(heap)

    if cost > distance[node]:
        continue

    for nxt, weight in graph[node]:
        new_cost = cost + weight

        if new_cost < distance[nxt]:
            distance[nxt] = new_cost
            heapq.heappush(heap, (new_cost, nxt))

유니온 파인드 핵심

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return False

    parent[b] = a
    return True

문제 유형

• 순위
• 합집합
• 여행 가자
• 섬 연결하기
• 가장 먼 노드
• 배달
• 경주로 건설
• 줄 세우기
• 항공권
• 네트워크 연결 비용 문제

판별 기준:

• 가중치가 있고 최단거리 → 다익스트라
• 그룹 합치기·같은 그룹인지 확인 → 유니온 파인드
• 선행 조건·순서 결정 → 위상 정렬
• 모든 간선을 최소 비용으로 연결 → 크루스칼 + 유니온 파인드

---

Day 6 — DP 집중 훈련

시간	학습 내용
오전	DP 상태 정의, 초기값, 점화식, 1차원·2차원 DP, 메모이제이션·바텀업
오후	기초 DP 3문제, 격자 DP 2문제, 배낭·문자열 DP 2문제
저녁	DP 문제를 풀이 보기 전에 상태·점화식만 먼저 작성

DP 접근 순서

문제를 보면 다음 네 가지를 먼저 적습니다.

1. dp[i] 또는 dp[i][j]가 무엇을 의미하는가?
2. 초기값은 무엇인가?
3. 이전 상태에서 현재 상태로 어떻게 이동하는가?
4. 최종 답은 어느 상태인가?

기본 템플릿

dp = [0] * (n + 1)
dp[0] = initial

for i in range(1, n + 1):
    dp[i] = transition(dp, i)

문제 유형

• 정수 삼각형
• 등굣길
• 도둑질
• N으로 표현
• 평범한 배낭
• 계단 오르기
• 1로 만들기
• LCS
• 가장 긴 증가하는 부분 수열
• 동전 교환

DP에서 막히면 20분 이상 고민하지 말고 다음 순서로 전환합니다.

1. 작은 입력을 직접 써본다.
2. i번째까지의 최적값을 표로 만든다.
3. 직전 상태와의 관계를 찾는다.
4. 점화식을 적는다.
5. 풀이를 본 뒤 코드를 닫고 재구현한다.

---

Day 7 — 실전 모의고사와 약점 보완

시간	학습 내용
오전	실제 시험처럼 2~3시간 모의고사
오후	오답 분석 후 가장 약한 유형 3문제 재풀이
저녁	템플릿 복습, 실전 전략 정리, 수면 확보

모의고사 규칙

• 문제를 처음부터 끝까지 읽고 난이도 분류
• 10분 안에 접근이 안 나오면 다음 문제로 이동
• 구현 전 시간복잡도 작성
• 제출 후 실패한 테스트 케이스 기록
• 풀이를 본 문제는 반드시 30분 뒤 백지 재구현

카카오형 문제 대응 순서

1. 전체 문제를 10~15분 동안 훑기
2. 구현·해시·정렬 문제부터 확보
3. BFS/DFS·그리디 문제 진행
4. DP·그래프 심화 문제에 남은 시간 투자
5. 완벽한 한 문제보다 부분 점수와 안정적인 여러 문제를 우선
6. 마지막 20분은 예외 처리와 시간복잡도 점검

---

4. 추천 리소스

문제 플랫폼

• 프로그래머스 코딩테스트 고득점 Kit
  • 해시, 스택/큐, 힙, 정렬, 완전탐색, DFS/BFS, 그리디, 이분 탐색, DP 순서로 학습
• 백준
  • 실버 2 ~ 골드 4 범위에서 유형별 문제 선택
• 카카오 기출
  • 프로그래머스의 카카오 기출 문제를 Day 7 모의고사로 사용

검색어

• 파이썬 코딩테스트 DFS BFS 템플릿
• 파이썬 코딩테스트 다익스트라 우선순위 큐
• 파이썬 코딩테스트 유니온 파인드
• 파이썬 코딩테스트 위상 정렬
• 파이썬 DP 상태 정의 점화식
• 프로그래머스 카카오 기출 해설
• 백준 DP 실버 골드 문제

학습 자료 사용 규칙

강의나 해설은 개념 이해용으로만 사용합니다.

• 강의 시청: 최대 30분
• 문제 풀이: 최소 45분
• 해설 확인 후: 코드 복사 금지
• 해설을 닫고 직접 재구현
• 다음 날 같은 문제를 다시 풀어 통과 여부 확인

---

5. 최종 성공 기준

시험 전날까지 다음을 충족하면 목표 달성으로 봅니다.

• 제한 조건을 보고 시간복잡도를 2분 안에 추정할 수 있다.
• DFS/BFS 격자 문제를 15분 안에 기본 코드로 작성할 수 있다.
• 다익스트라, 유니온 파인드, 위상 정렬 템플릿을 암기하고 변형할 수 있다.
• DP 문제에서 상태와 점화식을 먼저 정의할 수 있다.
• 프로그래머스 중간 난도 문제를 40~60분 안에 해결할 수 있다.
• 2~3시간 모의고사에서 최소 2문제를 안정적으로 해결하고, 추가 문제의 접근법을 설명할 수 있다.
• 다음 템플릿을 빈 화면에서 작성할 수 있다:
  • BFS/DFS
  • 격자 탐색
  • 다익스트라
  • 유니온 파인드
  • 이분 탐색
  • 백트래킹
  • 1차원 DP

시험 당일에는 새로운 알고리즘을 공부하지 말고, 템플릿·오답·자주 발생하는 실수만 복습한 뒤 충분히 수면을 확보하세요.