DFS vs BFS

 유형1. Window size가 정해져 있지 않은 케이스: i, j 움직여가면서 조건에 맞는 놈 생길때마다 window size가 바뀜 Template: 크게 2가지 step으로 이뤄짐 Expand Window: for문 안에서 첫부분에 j++하는 부분 Shrink Winow: while( invalid) 문에서 i++하는 부분 세부 접근법: invalid한 상태가 무엇인지 먼저 생각해라 -> 그래야 for문 안의 while문을 먼저 짤 수 있음 invalid 발상 떠올리는법: i=0, j=0에서 시작해서 j가 한칸씩 오른쪽으로 간다. 이렇게 j를 한칸씩 움직이면서 어떨때 invalid할지 생각하기 int i = 0, j = 0, ans = 0; for (; j < N; ++j) { // CODE: use A[j] to update state which might make the window invalid for (; invalid(); ++i) { // when invalid, keep shrinking the left edge until it's valid again // CODE: update state using A[i] } ans = max(ans, j - i + 1); // the window [i, j] is the maximum window we've found thus far } return ans; 가장 정석적인 문제: ...

 유형 left = 0, right = n-1 while(left < right){ if() left++; if() right--; } 이때 two pointer를 쓰려면 sorted 된 array이어야한다 그렇지 않으면 TC상 이점이 없음 -> ex. Two Sum 문제의 경우 Sort 되지 않은 array면 hashmap으로 푸는게 two pointers로 푸는 것보다 빠름 예제: https://leetcode.com/problems/reverse-string/description/ https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/