TIL 2022-06-08-수

1. 학습한 내용

• 이것이 코딩테스트다 chap05 DFS/BFS (3) (4) 실전문제
• 백준 동적프로그래밍 1912번 문제

2. 알게 된 내용

DFS / BFS 실전문제에서

• dfs -> 재귀로 다음 위치에 대해 탐색

• bfs -> 이동하는 양을 dx, dy 배열에 미리 담아두어도 좋다. bfs에서는 큐를 이용해서, 레벨에 해당하는 위치들을 큐에 담아두고 큐가 빌 때까지 반복하면서 레벨 별로 탐색한다.

백준 1912번 문제에서

• 포인트
  연속적으로 선택한 수의 합이 최댓값이 되는 수를 찾는다. 즉, 메모이제이션은 이전까지 탐색했던 값(이전 배열의 누적합)과, 현재 위치의 값을 비교하여 큰 값을 저장하면 된다.

• dp배열 : 각 인덱스까지의 최댓값을 저장.

• dp배열의 최댓값을 구할 때 tip
  처음부터 아예 재귀 또는 반복문 안에 max 변수를 하나 두어서 최댓값을 갱신하는 방법이 더 효율적이다.