03-06 학습&숙제

03-06 학습! 그래프 2단계! 🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐

그래프 🟥

BFS 방문처리의 중요성🟧

가중치 없는 그래프의 최단거리를 구할 때
BFS 를 cur을 떨구고 방문처리하고 next들을 큐에 넣을텐데 여기서 방문처리를 해주지 않는다면 어떻게 될까?
불필요한 연산이 이루어질 수 있음

그래프에서 bfs로 최단거리를 탐색할 때 방문 처리를 어떻게 하는지가 매우 중요!

인접 리스트로 BFS 구현 연습 필요🟨

강사님 수업 🟩

DFS -> BACKTRACKING -> 터짐

그렇다면 DP로 가야한다!

많이 나오는 바텀 업
어려운 테이블라이저 탑 다운

Arrays.BynarySearch (arr, i);🫢

1. 정렬 되어있어야 함
2. i가 있는 위치가 반환 됨
3. 없는 값을 찾으라고 하면 원래 있어야 할 위치가 3이라면 -4 가 나온다 생각해보면 위치가 0부터 시작이라서 0이 없으면 -1 이 나와야 함
4. dp -> lis 를 풀기 위해 이걸 알아야 함 (for에 dp)
5. kadane 전체 배열에서의 최대 부분합
6. 배열에 원소를 찾고 어디에 있어야 할 지 위치도 알려주는 아주 좋은 기술!😎

문제들 🟦

SWEA 달란트
SWEA 창용 마을
하나로
백준 최단경로
백준 일감호에 다리놓기
친구 네트워크

숙제 🟪

SQL-D 시험 대비!