Introduction to Algorithms

[DanKim0213]

Introduction to Algorithms

• Intro
• BFS vs DFS
• Sliding window vs Two pointer vs Prefix sum
• Disjoint Set vs Topological Sorting
• Binary Search
• DP

[DanKim0213]

BFS vs DFS

Some coding problems must be solved by BFS or DFS, not both. Which algorithm is decided by the coding problems' features.

TL;DR; BFS doesn't need to go back while DFS needs to since DFS is dependent on your past decisions.

BFS

숨바꼭질, 아기상어, 캐슬디펜스, 토마토

DFS

감시, 빵집

[DanKim0213]

Disjoint Set vs Topological Sorting

Disjoint Set:

• https://www.acmicpc.net/problem/20040
• https://www.acmicpc.net/problem/4195
• https://www.acmicpc.net/problem/10775

공항 (10775)

4 // G 6 // P 2 // 2 -> 1 2 // 2 -> 1 -> 0 3 // 3 -> 2 3 // 쭈욱 부모를 따라가보니 0이네? 리턴 4 4

따라서 3

[DanKim0213]

Two pointers vs Sliding window vs Prefix sum

투-포인터-슬라이딩-윈도우-구간-합-알고리즘

[DanKim0213]

Binary Search vs Parametric Search

• 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다.
• 모든 배열을 살펴보면서 mid (a.k.a. answer)를 업데이트하기 때문에 최소값/최댓값을 구할 수 있다.
• 매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다.
• 매개 변수 탐색은 대상군들에게서 적절한 균형(최댓값 또는 최솟값)을 찾는 문제가 많다. 왜냐하면 적절한 균형을 찾는 과정이 범위 내 가능한 값들을 시도하면서 범위를 좁혀가야하기 때문에.

Binary Search vs Parametric Search