먼저 알아야 할 것

1단원 · 파이썬으로 문제 풀기

읽기 전에
  1. 7 // 2, 7 % 2, -7 // 2의 값은 각각 무엇일까? → 파이썬 기본 문법
  2. 입력이 10만 개일 때, 모든 쌍을 비교하는 방법은 1초 안에 끝날까? → 시간 복잡도로 방법 고르기
  3. 이름 10만 개 중에서 한 이름이 있는지 확인하는 가장 빠른 방법은? → 딕셔너리와 집합
번호 개념 한 줄 개념 코드 연습
01 파이썬 기본 문법 값과 변수, 조건문, 반복문, 함수. solution 함수 하나가 답안이다 verify 짝수와 홀수 (코드)
02 시간 복잡도로 방법 고르기 제한의 크기를 보고 연산 횟수를 어림해, 쓸 수 있는 방법을 미리 고른다 (무거움) bench · fig1 · fig2 · plot · verify 시간 복잡도 어림 예제 사다리
03 리스트와 문자열 번호로 꺼내는 줄. 인덱스, 슬라이싱, 메서드, 컴프리헨션 verify 평균 구하기 (코드), 숫자 문자열과 영단어 (코드), k진수에서 소수 개수 구하기 (코드), n진수 게임 (코드)
04 딕셔너리와 집합 이름표로 바로 찾는 표(해시). 넣기·찾기가 평균 O(1) (무거움) fig1 · impl · plot 완주하지 못한 선수 (코드), 성격 유형 검사하기 (코드), 신고 결과 받기 (코드), 가장 많이 받은 선물 (코드), 뉴스 클러스터링 (코드), 압축 (코드), 오픈채팅방 (코드)
05 정렬과 정렬 기준 sorted와 key로 원하는 순서 만들기. 같은 값은 원래 순서를 지킨다 fig1 · impl · plot K번째수 (코드), 실패율 (코드), 무지의 먹방 라이브 (코드)

떠올려 보기: 노트를 닫고 리스트·딕셔너리·정렬로 각각 무엇을 빠르게 할 수 있는지, 그 비용(빅오)과 함께 적어 본다.

2단원 · 구현의 기본기

읽기 전에
  1. “09:05”와 “10:02” 사이는 몇 분일까? 가장 실수가 적은 계산법은? → 시간·날짜 계산
  2. 격자에서 상하좌우 이웃을 네 개의 if 없이 돌 수 있을까? → 구현과 시뮬레이션
  3. 9와 30을 이진수로 쓰고 OR 하면 무엇이 될까? → 비트 연산과 비트마스크
번호 개념 한 줄 개념 코드 연습
06 문자열 파싱과 정규 표현식 글자를 하나씩 읽거나 규칙(정규식)으로 잘라 의미 단위로 바꾼다 verify 다트 게임 (코드), 신규 아이디 추천 (코드), 중요한 단어를 스포 방지 (코드), 튜플 (코드), 파일명 정렬 (코드)
07 시간·날짜 계산 모든 시각을 가장 작은 단위 하나로 바꿔 빼고 더한다 verify 개인정보 수집 유효기간 (코드), 동영상 재생기 (코드), 주차 요금 계산 (코드), 방금그곡 (코드)
08 구현과 시뮬레이션 규칙을 그대로 한 단계씩 따라 한다. 격자와 방향 배열 verify 키패드 누르기 (코드), 붕대 감기 (코드), 프렌즈4블록 (코드), 거리두기 확인하기 (코드), 셔틀버스 (코드), 기둥과 보 설치 (코드), 블록 게임 (코드)
09 비트 연산과 비트마스크 수를 0과 1의 칸으로 보고 칸 단위로 계산한다. 부분집합을 수 하나로 verify 비밀지도 (코드)

떠올려 보기: 문자열 자르기, 시간 바꾸기, 격자 이동, 비트 연산에서 각각 가장 자주 하는 실수 하나씩을 적어 본다.

3단원 · 기본 자료구조

읽기 전에
  1. 괄호 문자열 “(()”가 짝이 맞지 않는다는 것을 어떤 자료구조로 가장 쉽게 알 수 있을까? → 스택
  2. 리스트의 맨 앞에서 pop(0)을 10만 번 하면 왜 느릴까? → 큐와 덱
  3. “같은 무리인가?”라는 질문을 수백만 번 빠르게 답하려면? → 유니온 파인드
번호 개념 한 줄 개념 코드 연습
10 스택 나중에 넣은 것을 먼저 꺼내는 접시 더미 impl 같은 숫자는 싫어 (코드), 크레인 인형뽑기 게임 (코드)
11 큐와 덱 먼저 온 것이 먼저 나가는 줄. 양쪽 끝을 모두 쓰면 덱 impl 캐시 (코드), 행렬과 연산 (코드)
12 힙과 우선순위 큐 가장 작은 것을 늘 O(log n)에 꺼내는 자료구조 impl —
13 연결 리스트 앞뒤 이웃만 기억하는 줄. 중간 삭제·복구가 O(1) impl 표 편집 (코드)
14 트라이 단어를 글자 단위 가지로 저장한 나무. 앞부분 검색에 강하다 impl 자동완성 (코드)
15 유니온 파인드 같은 무리인지 빠르게 묻고, 두 무리를 합친다 fig1 · impl · plot 호텔 방 배정 (코드)

떠올려 보기: 스택·큐·덱·힙·연결 리스트·트라이·유니온 파인드를 각각 한 줄로 설명하고, 대표 연산의 비용을 적어 본다.

4단원 · 탐색 기법

읽기 전에
  1. 원소 8개로 만들 수 있는 순서는 몇 가지이고, 모두 확인해도 될까? → 완전탐색
  2. 정렬된 100만 개에서 값 하나를 찾는 데 비교가 대략 몇 번 필요할까? → 이분 탐색
  3. “가장 긴 최소 거리”처럼 최대·최소를 묻는 문제를 예/아니오 문제로 바꿀 수 있을까? → 매개변수 탐색
번호 개념 한 줄 개념 코드 연습
16 완전탐색 가능한 경우를 모두 만들어 확인한다. 경우의 수가 작을 때 가장 확실하다 verify 노란불 신호등 (코드), 메뉴 리뉴얼 (코드), 수식 최대화 (코드), 문자열 압축 (코드), 후보키 (코드), 자물쇠와 열쇠 (코드), 외벽 점검 (코드), 추석 트래픽 (코드)
17 재귀와 백트래킹 자기 자신을 부르는 함수로 선택을 하나씩 쌓고, 안 되면 되돌린다 (무거움) verify 괄호 변환 (코드), 양궁대회 (코드), 불량 사용자 (코드), 양과 늑대 (코드), 4단 고음 (코드), 재귀와 백트래킹 예제 사다리
18 투 포인터와 슬라이딩 윈도 두 손가락을 한 방향으로만 움직여 구간을 O(n)에 훑는다 fig1 · plot · verify 두 큐 합 같게 만들기 (코드), 보석 쇼핑 (코드), 쿠키 구입 (코드)
19 누적 합과 차분 배열 앞에서부터 더해 둔 합으로 구간 합을 O(1)에. 구간 더하기는 차분으로 fig1 · plot · verify 파괴되지 않은 건물 (코드), 광고 삽입 (코드), 지형 편집 (코드), 문자열의 아름다움 (코드)
20 이분 탐색 정렬된 곳에서 절반씩 버리며 찾는다. O(log n) (무거움) fig1 · impl · plot 순위 검색 (코드), 가사 검색 (코드), 문자열과 알파벳과 쿼리 (코드)
21 매개변수 탐색 “최댓값은?”을 “x가 되는가?”로 바꿔 답을 이분 탐색한다 (무거움) fig1 · plot · verify 징검다리 건너기 (코드), 징검다리 (코드), 재밌는 레이싱 경기장 설계하기 (코드), 매개변수 탐색 예제 사다리
22 그리디 지금 가장 좋아 보이는 선택을 되돌리지 않고 이어 간다. 맞는지 증명이 필요하다 fig1 · plot · verify 미로 탈출 명령어 (코드), 1,2,3 떨어트리기 (코드)

떠올려 보기: 완전탐색, 백트래킹, 투 포인터, 누적 합, 이분 탐색, 그리디를 언제 쓰는지 신호 하나씩과 함께 적어 본다.

5단원 · 그래프와 트리

읽기 전에
  1. 미로의 최단 거리를 구할 때 BFS가 DFS보다 나은 이유는? → 너비 우선 탐색(BFS)
  2. 간선 가중치에 음수가 있으면 다익스트라는 왜 틀릴 수 있을까? → 다익스트라
  3. 도시 100개의 모든 쌍 최단 거리를 한 번에 구하는 가장 짧은 코드는? → 플로이드–워셜
번호 개념 한 줄 개념 코드 연습
23 그래프 표현 점과 선을 인접 리스트나 격자로 코드에 담는다 verify 방의 개수 (코드)
24 너비 우선 탐색(BFS) 가까운 곳부터 물결처럼 퍼진다. 가중치 없는 최단 거리 (무거움) impl 블록 이동하기 (코드), 동굴 탐험 (코드)
25 깊이 우선 탐색(DFS) 한 길로 끝까지 갔다가 돌아온다. 연결된 덩어리 찾기 impl 시험장 나누기 (코드), 스마트한 프로도 (코드)
26 다익스트라 가장 가까운 곳부터 확정하는 최단 경로. 간선 가중치가 음수가 아닐 때만 (무거움) impl 경주로 건설 (코드), 등산코스 정하기 (코드), 미로 탈출 (코드)
27 플로이드–워셜 모든 점 쌍의 최단 거리. 거쳐 갈 점을 하나씩 늘린다 verify 합승 택시 요금 (코드)
28 최소 신장 트리 모든 점을 가장 싸게 잇는 나무. 싼 선부터 사이클 없이 고른다 verify 지형 이동 (코드)
29 트리 순회와 이진 탐색 트리 전위·중위·후위 순회. 왼쪽은 작고 오른쪽은 큰 나무 impl 길 찾기 게임 (코드), 표현 가능한 이진트리 (코드)

떠올려 보기: BFS, DFS, 다익스트라, 플로이드–워셜, 최소 신장 트리를 쓰는 상황과 복잡도를 표로 그려 본다.

6단원 · 동적 계획법

읽기 전에
  1. 피보나치 수를 재귀로 그대로 구하면 왜 느리고, 어떻게 빠르게 할까? → 동적 계획법
  2. 식 1 − 5 − 3에서 괄호를 어떻게 쳐야 가장 클까? 부분식의 무엇을 기억해야 할까? → 구간 DP
  3. 트리에서 자식의 답만 알면 부모의 답을 알 수 있는 문제의 예는? → 트리 DP
번호 개념 한 줄 개념 코드 연습
30 동적 계획법 작은 문제의 답을 표에 적어 두고 큰 문제에서 꺼내 쓴다 (무거움) fig1 · plot · verify 코딩 테스트 공부 (코드), 도둑질 (코드), 올바른 괄호의 갯수 (코드), 단어 퍼즐 (코드), 튜브의 소개팅 (코드), 네오의 귀걸이 (코드), 동적 계획법 예제 사다리
31 구간 DP 구간 [i, j]의 답을 더 짧은 구간의 답으로 만든다 verify 사칙연산 (코드)
32 트리 DP 자식의 답으로 부모의 답을 만든다. 아래에서 위로 verify 매출 하락 최소화 (코드)

떠올려 보기: DP 문제를 풀 때 정하는 네 가지(상태, 점화식, 시작값, 계산 순서)를 한 예로 적어 본다.

7단원 · 고급 기법

읽기 전에
  1. 겹치는 직사각형들의 전체 넓이를 한 번 훑어서 구할 수 있을까? → 세그먼트 트리와 스위핑
  2. 학생과 과제를 한 명당 하나씩 최대한 많이 짝지으려면? → 이분 매칭
  3. 세 점이 시계 방향으로 도는지 반시계 방향으로 도는지 곱셈 몇 번으로 알 수 있을까? → 계산 기하 기초
번호 개념 한 줄 개념 코드 연습
33 세그먼트 트리와 스위핑 구간을 반씩 나눈 나무로 구간 질의와 갱신을 O(log n)에. 선을 한쪽으로 쓸며 사건을 처리 verify 직사각형의 넓이 (코드)
34 이분 매칭 두 편 사이에서 겹치지 않게 가장 많은 짝을 짓는다 verify 신비로운 유적 탐험 (코드)
35 계산 기하 기초 외적의 부호로 왼쪽·오른쪽을 판정한다(CCW). 교차와 포함 판정 fig1 · plot · verify IU와 콘의 보드게임 (코드)

떠올려 보기: 세그먼트 트리, 이분 매칭, CCW가 각각 어떤 질문에 답하는지 한 줄씩 적어 본다.

8단원 · 수학과 잇기

읽기 전에
  1. 이분 탐색 코드가 맞다는 것을 수학적 귀납법으로 보이려면, 무엇을 ‘기저’와 ‘귀납 단계’로 잡아야 할까? → 수학적 귀납법 ↔ 루프 불변식
  2. 배열 [a, b, c]의 누적 합을 행렬 곱 한 번으로 쓸 수 있을까? 차분은? → 누적 합 ↔ 아래삼각행렬
  3. 배열로 만든 힙에서 13번 칸이 뿌리에서 어떤 길로 내려간 칸인지 2진수로 읽을 수 있을까? → 트리 칸 번호 ↔ 2진법 자릿수
번호 개념 한 줄 개념 코드 연습
36 격자 회전 ↔ 선형변환 격자 뒤집기와 전치는 선형변환이다. 반사 두 번이 회전이고, 순서를 바꾸면 방향이 바뀐다 fig1 · plot · verify —
37 누적 합 ↔ 아래삼각행렬 누적 합은 아래삼각 1 행렬을 곱하는 일, 차분은 그 역행렬을 곱하는 일이다 verify —
38 수학적 귀납법 ↔ 루프 불변식 초기화·유지·종료는 기저·귀납 단계·결론이다 verify —
39 매개변수 탐색 ↔ 사잇값 정리 참과 거짓이 바뀌는 경계를 반씩 좁힌다. 연속이면 근, 단조면 경계를 찾는다 fig1 · plot · verify —
40 추이 폐포 ↔ 플로이드–워셜 경유점을 하나씩 늘리는 같은 표 채우기. 또는·그리고를 min·+로 바꾼다 verify —
41 위상 정렬 ↔ 동적 계획법의 계산 순서 표를 채우는 순서는 칸 사이 의존 관계의 위상 정렬이다 verify —
42 트리 칸 번호 ↔ 2진법 자릿수 배열로 만든 나무에서 칸 번호의 비트가 뿌리에서 그 칸까지의 길이다 verify —

떠올려 보기: 브리지 문서 일곱 개에서 알고리즘 쪽과 수학 쪽의 짝을 하나씩 떠올려 표로 적어 본다.

다른 과목과의 연결

알고리즘 문서가 기대는 공학수학 개념이다. 괄호 안은 그 개념을 링크한 알고리즘 문서 수다.

공학수학 과목 개념 (문서 수)
대학수학 진법과 자릿수 (17), 로그 (9), 수열과 합의 기호 (8), 등비급수 (8), 거듭제곱과 지수법칙 (3), 거듭제곱함수와 지수함수 비교 (3), 함수의 변환과 합성 (2), 역함수 (2), 로그함수와 로그 스케일 (2), 복소수의 극형식과 오일러 공식 (2), 함수 (1), 지수함수 (1), 삼각함수 항등식 (1), 역삼각함수 (1), 사인 법칙과 코사인 법칙 (1), 극좌표와 매개변수 곡선 (1)
이산수학 집합 (14), 순열과 조합 (14), 재귀적 정의와 구조적 귀납법 (12), 나눗셈과 합동 (12), 수학적 귀납법 (11), 셈의 기본 법칙 (11), 트리 (11), 동치관계와 분할 (10), 부분순서와 위상 정렬 (10), 경로와 연결성 (9), 포함-배제 원리 (5), 선형 점화식 (5), 비둘기집 원리 (4), 이분 그래프와 그래프 색칠 (4), 추론 규칙과 증명 방법 (3), 불 대수와 논리 회로 (3), 함수의 성질과 집합의 크기 (3), 관계와 그 성질 (3), 합의 계산과 어림 (3), 최대공약수와 유클리드 호제법 (3), 그래프의 기초 (3), 명제와 논리 연산 (2), 순열·조합·중복조합 비교 (2), 이항정리 (2), 생성함수 (2), 분할 정복 점화식과 마스터 정리 (2), 모듈러 역원과 중국인의 나머지 정리 (2), 논리적 동치와 정규형 (1), 술어와 한정기호 (1), 중복을 허용하는 셈 (1), 점근 표기 (1), py (1), 소수와 산술의 기본정리 (1), 페르마 소정리와 오일러 정리 (1)
미분적분학 연속과 사잇값 정리 (6), 합 ↔ 적분 (5), 미적분의 기본정리 (4), 연쇄 법칙 ↔ 역전파 (4), 정적분과 리만 합 (2), 중적분과 변수변환 (2), 극한 (1), 수열의 극한과 e (1), 선형 근사와 뉴턴 방법 (1), 급수의 수렴 (1), 경사 하강법 (1), 볼록 함수와 볼록 최적화 (1), 푸리에 변환과 합성곱 (1)
선형대수학 행렬 곱셈과 전치 (6), 선형변환 (4), 벡터 (3), 행렬과 행렬-벡터 곱 (3), 역행렬 (3), 행렬식 (3), 가우스 소거법 (2), LU 분해 (1), 부분공간, 기저와 차원 (1), 랭크와 네 부분공간 (1), 덧셈정리 ↔ 복소수 곱 ↔ 회전 행렬 (1), 선형 점화식 ↔ 행렬 거듭제곱 (1), 대칭행렬과 스펙트럼 정리 (1), 노름과 조건수 (1)
확률과 통계 기술통계 (5), 엔트로피 (5), 확률변수와 분포 (3), 인접행렬 거듭제곱 ↔ 마르코프 전이 (3), 해싱과 무작위 알고리즘의 확률 (3), 독립 (2), 기하분포 (2), 결합분포와 조건부 기댓값 (2), 확률의 공리와 계산 (1), 조건부 확률 (1), 균등분포와 지수분포 (1), 마르코프 연쇄 (1), PageRank (1), 몬테카를로 방법 (1)

프로그래머스 문제 목록

레벨별로 모은 문제 90개다. 카카오·PCCP 기출을 먼저 넣고, 모자라면 많이 푼 문제로 채웠다. 목록은 풀 문제를 고를 때, 위 표는 개념별로 모아 풀 때 쓴다.

레벨 문서 문제 수 풀이
1 프로그래머스 Level 1 20 20개
2 프로그래머스 Level 2 20 20개
3 프로그래머스 Level 3 20 20개
4 프로그래머스 Level 4 20 20개
5 프로그래머스 Level 5 10 10개

흐름

화살표는 선수관계다. 점선 테두리는 아직 문서가 없는 개념이다.

graph LR
  n1["01 파이썬 기본 문법"]
  n2["02 시간 복잡도로 방법 고르기"]
  n3["03 리스트와 문자열"]
  n4["04 딕셔너리와 집합"]
  n5["05 정렬과 정렬 기준"]
  n6["06 문자열 파싱과 정규 표현식"]
  n7["07 시간·날짜 계산"]
  n8["08 구현과 시뮬레이션"]
  n9["09 비트 연산과 비트마스크"]
  n10["10 스택"]
  n11["11 큐와 덱"]
  n12["12 힙과 우선순위 큐"]
  n13["13 연결 리스트"]
  n14["14 트라이"]
  n15["15 유니온 파인드"]
  n16["16 완전탐색"]
  n17["17 재귀와 백트래킹"]
  n18["18 투 포인터와 슬라이딩 윈도"]
  n19["19 누적 합과 차분 배열"]
  n20["20 이분 탐색"]
  n21["21 매개변수 탐색"]
  n22["22 그리디"]
  n23["23 그래프 표현"]
  n24["24 너비 우선 탐색(BFS)"]
  n25["25 깊이 우선 탐색(DFS)"]
  n26["26 다익스트라"]
  n27["27 플로이드–워셜"]
  n28["28 최소 신장 트리"]
  n29["29 트리 순회와 이진 탐색 트리"]
  n30["30 동적 계획법"]
  n31["31 구간 DP"]
  n32["32 트리 DP"]
  n33["33 세그먼트 트리와 스위핑"]
  n34["34 이분 매칭"]
  n35["35 계산 기하 기초"]
  n36["36 격자 회전 ↔ 선형변환"]
  n37["37 누적 합 ↔ 아래삼각행렬"]
  n38["38 수학적 귀납법 ↔ 루프 불변식"]
  n39["39 매개변수 탐색 ↔ 사잇값 정리"]
  n40["40 추이 폐포 ↔ 플로이드–워셜"]
  n41["41 위상 정렬 ↔ 동적 계획법의 계산 순서"]
  n42["42 트리 칸 번호 ↔ 2진법 자릿수"]
  n1 --> n2
  n1 --> n3
  n3 --> n4
  n2 --> n4
  n3 --> n5
  n2 --> n5
  n3 --> n6
  n1 --> n7
  n3 --> n8
  n1 --> n9
  n3 --> n10
  n3 --> n11
  n2 --> n11
  n3 --> n12
  n2 --> n12
  n3 --> n13
  n4 --> n14
  n3 --> n15
  n2 --> n16
  n16 --> n17
  n10 --> n17
  n3 --> n18
  n2 --> n18
  n3 --> n19
  n5 --> n20
  n20 --> n21
  n5 --> n22
  n4 --> n23
  n11 --> n24
  n23 --> n24
  n17 --> n25
  n23 --> n25
  n12 --> n26
  n24 --> n26
  n23 --> n27
  n15 --> n28
  n5 --> n28
  n23 --> n28
  n17 --> n29
  n17 --> n30
  n30 --> n31
  n30 --> n32
  n25 --> n32
  n29 --> n32
  n19 --> n33
  n17 --> n33
  n5 --> n33
  n25 --> n34
  n1 --> n35
  n8 --> n36
  n19 --> n37
  n20 --> n38
  n21 --> n39
  n27 --> n40
  n30 --> n41
  n12 --> n42
  n33 --> n42