강의 자료들

목차

01. 완전 탐색

탐색, 정렬

1. 이진 탐색

2. lower_bound, upper_bound

   • 정렬된 자료에서 [a, b] 구간의 자료의 개수 구하기

3. 정렬

   • 카운팅 정렬
   • 병합 정렬(배열)
   • 퀵정렬(Hoare partition)
   • 퀵정렬(Lomuto partition)

완전 탐색

1. 간단한 중첩 for와 재귀 호출 이해

   • 중첩된 for
   • 재귀

2. Baby_gin

   • for문 중첩해서 순열/조합 생성해서 해결
   • 카운팅을 이용해서 해결

3. 3개 요소들의 부분 집합 생성

   • 바이너리 카운팅
   • for문 중첩
   • 재귀 호출 + bit 배열

4. 3개 요소들의 순열 생성

   • for문 중첩
   • 재귀 호출 + 요소들 인덱스 나열(array)
   • 재귀 호출 + 요소들 인덱스 나열(bit op)

5. 3개에서 2개 뽑는 조합 생성

   • for문 중첩
   • 재귀 호출

---

연습 문제

1. 프로젝트 분배
2. 숫자 교환

추가

추가 문제

Brute-Force

1. 덩치
2. 체스판 다시 칠하기

3. 일곱 난쟁이

   • 부분 집합

4. 로또

   • 조합

분할 정복

1. 숫자 카드

   • 이분 탐색

2. 쿼드 트리

3. 버블 소트

   • 병합 정렬 + counting inversion

4. 입국 심사

   • 최적화 문제 -> 결정 문제 + 이분 탐색
   • lower_bound 탐색

02. 그래프

예제 코드

1. 그래프 탐색

   • DFS 반복
   • DFS 재귀
   • BFS + 배열로 구현한 큐
   • BFS + 라이브러리 큐 사용

2. Disjoint-Set

   • 기본 연산 구현
   • 경로 압축, 랭크에 의한 union

3. 위상 정렬
4. 최소 신장 트리
5. 최단 경로
6. 싸이클 판정

---

연습 문제

1. 최소 신장 트리
2. 도깨비 언덕
3. 위상 정렬

추가

추가 문제

목록

1. DFS와 BFS

2. 미로 탐색

   • BFS

3. 네트워크 연결

   • 최소 신장 트리

4. 줄세우기

   • 위상 정렬

5. 음악 프로그램

   • 위상 정렬 + 싸이클 판정

6. 최단 경로

   • DFS, BFS, Dijkstra

7. 친구 네트워크

   • Disjoint-Set 사용
   • 입력으로 주어지는 이름 문자열을 정수 값을 부여, HashMap을 사용해서 문제를 해결할 수 있다.

03. 백트래킹(Backtracking)

예제 코드

1. 부분 집합 생성

   • 바이너리 카운팅
   • DFS
   • BFS

2. 순열 생성

   • 이미 선택한 요소들을 체크해서 순열 생성
   • 1부터 시작하는 순열 생성
   • 교환을 통한 생성
   • 중복 순열 생성

3. 조합 생성

   • 재귀적 정의로 생성
   • 요소를 순차적으로 선택하면서 생성
   • 중복 조합

4. 동전 교환

5. 배낭 문제

   • 부분 집합 생성
   • 재귀적 정의

6. N-Queen 문제

   • 순열 생성 + 가지 치기

---

연습 문제

1. 병원 짓기
2. 방 배정
3. 모든 정점 경유 최단 거리

추가

추가 문제

목록

1. n-Queen

   • 순열 + 가지치기

2. 알파벳

   • DFS(탐색할 수 없어서 되돌아가는 경로의 방문 정보를 지운다).

3. 나이트의 이동

   • BFS(최단 경로)

4. 외판원 순회2

   • 순열(현재까지 발견한 가장 좋은 해에 기반해서 가지치기)

5. 교환

04. 동적 계획법

예제 코드

1. 피보나치 수

2. 동전 교환

   • 재귀
   • 재귀 + 메모
   • 반복

3. 배낭 문제

   • 재귀
   • 재귀 + 메모
   • 반복

4. 행렬 경로 문제

   • 재귀 + 메모
   • 반복

5. Floyd-Warshall

6. TSP + DP

   • Day3 백트래킹 모든 정점 경유 최단 거리 문제

7. 이항 계수

---

연습 문제

1. 색종이 이어 붙이기
2. 행동 패턴 유사성
3. 행렬곱

추가

추가 문제

목록

1. 이친수

   • long 자료형 사용

2. 2xN 타일링

   • 모듈러 합동

3. RGB 거리
4. 동전2
5. 공통 부분 문자열

6. 키순서

   • 플로이드-워샬
   • 순뱡향/역방향 DFS 탐색

7. 외판원 순회

   • 비트 마스크를 활용한 메모이제이션

05. 트리

예제 코드

1. 트리 순회하기

   • 전위/중위/후위 순회하기
   • 트리의 높이
   • 트리의 크기(노드 수)

2. 이진 탐색 트리
3. 힙(Binary Heap)
4. 인덱스 트리(Index Tree)

5. 구간 트리(Segement Tree)

   1. 구간 나누기
   2. 구간합 트리 생성/쿼리
   3. 단일 값 갱신하기
   4. 구간 갱신

---

연습 문제

1. 공통조상, 서브 트리의 높이와 너비

추가

추가 문제

목록

1. 트리 순회

2. 트리의 높이와 너비

   • 주의 :루트가 1번 노드가 아닐 수 있다.

3. 최소 공통 조상(LCA, Lowest Common Ancestor)

   • 주의 : 입력으로 제공되는 간선(u,v) 정보에서 먼저 입력되는 u가 반드시 부모가 아닐 수 있다.
   • 무향 그래프 형태로 저장해서 1번(루트)를 시작점으로 너비우선 탐색을 수행해서 정점들의 부모를 찾는다.

4. 구간합 구하기
5. 구간 최소값

06. 문자열

예제 코드

1. 패턴 매칭

   • Brute-force
   • KMP

2. 접미어 배열

   • \(O(N^2)\) : 단순한 방법:
   • \(O(\log N)\)

3. 아호-코라식

---

추가

추가 문제

목록

1. 찾기

   • KMP

99. 자료구조 라이브러리

정렬

1. Array
2. Comparator
3. Comparable
4. binary Search

---

자료 구조

1. Stack
2. Queue
3. LinkedList
4. Vector
5. TreeSet
6. Prioirty Queue
7. HashMap

---

연습 문제

추가 문제

목록

1. 소트 인사이드
2. 단어 정렬
3. 보물
4. 전화 번호 목록 만들기
5. 빈도 정렬
6. 회사에 있는 사람
7. 괄호
8. 프린터큐