문제 해결로 배우는 알고리즘
알고리즘 공부는 같은 문제를 여러 방법으로 풀어 보고, 각 방법이 왜 맞는지, 얼마나 많은 일을 하는지 비교하는 연습입니다. 작은 정답을 먼저 만들고 더 나은 풀이로 고쳐 가는 과정을 배웁니다.
- 대상: Python의 변수, 조건문, 반복문, 함수를 읽을 수 있는 분.
- 먼저 알면 좋은 것: 배열, 스택, 큐, 트리, 그래프. 낯설다면 자료구조 강좌부터 읽으세요.
- 구성: 문제, 풀이 아이디어, 작은 예제, 연산 비용, 확인 문제와 해설. 모든 수업을 무료로 읽을 수 있습니다.
- 목표: 풀이의 전제와 반례를 설명하고, 입력 크기에 맞는 전략을 고릅니다.
외울 이름보다 세 가지 질문에 집중해 보세요. 후보를 빠뜨리지 않았나? 같은 계산을 반복하나? 지금 한 선택이 나중에도 맞나?
강좌 목차
- 01 문제를 정확하게 적기입력과 출력, 경계 조건부터 정하고 작은 예제로 확인합니다.
- 02 연산량으로 비교하기반복문의 횟수를 세고 시간과 추가 공간을 구분합니다.
- 03 모든 후보를 살펴보는 완전 탐색가장 단순한 정답부터 만들고 후보가 늘어나는 속도를 봅니다.
- 04 나누고 합치는 분할 정복합병 정렬로 작은 문제의 답을 합치는 과정을 봅니다.
- 05 지금 좋은 선택을 하는 탐욕법탐욕법이 맞는 문제와 반례가 생기는 문제를 비교합니다.
- 06 계산 결과를 기억하는 동적 계획법상태와 점화식을 정해 같은 작은 문제를 다시 풀지 않습니다.
- 07 넣을까 말까, 배낭 문제한 번만 쓸 수 있는 물건을 용량 안에서 고릅니다.
- 08 두 문자열의 공통 순서 찾기최장 공통 부분 수열로 두 입력을 함께 다루는 DP를 익힙니다.
- 09 가능성 없는 길에서 돌아오기선택을 쌓고 되돌리며 조건에 맞지 않는 가지를 자릅니다.
- 10 더 좋은 답이 없는 가지를 자르기현재 최선의 답과 낙관적인 한계를 비교합니다.
- 11 다익스트라로 최단 거리 구하기우선순위 큐와 거리 갱신을 연결해 봅니다.
- 12 문자열에서 패턴 찾기한 칸씩 비교하는 방법과 비교 결과를 재사용하는 방법을 봅니다.
- 13 나머지로 줄이는 정수 문제최대공약수와 소수 검사에서 후보를 줄이는 근거를 찾습니다.
- 14 점과 방향을 다루는 기하 알고리즘가까운 점과 회전 방향을 작은 계산으로 판단합니다.
- 15 어려운 문제와 근사해정답 확인과 정답 찾기의 차이, 해법의 보장 범위를 배웁니다.
- 16 큰 데이터를 다루는 방법병렬 처리와 외부 저장 장치에서 달라지는 비용을 봅니다.