2021.06.12 정수삼각형 Solution DFS : 삼각형의 꼭대기에서부터 아래 or 오른쪽아래로 깊이우선탐색을 합니다. DFS로 탐색을 구현할 때 리턴하는 값은 다음과 같이 설정할 수 있습니다. 맨 아래인 경우 : 해당 노드의 값 맨 아래가 아닌 경우 : 해당 노드의 값 = 그 다음노드부터 맨 아래까지의 최대경로 이렇게 설정하면 결국 재귀로 구현한 깊이우선탐색의 최종 반환 값이 원하는 결과가 됩니다. DP : 위의 DFS에서 각 노드를 탐색할 때, 이미 탐색한 적이 있는 경우 메모이제이션 을 활용할 수 있습니다. 해당 노드부터 맨 아래까지의 경로 중 최댓값을 DP 배열에 저장하고, 이미 탐색한 적이 있는 경우 (DP 배열이 초기값이 아닌경우) 에는 메모이제이션 해둔 값을 반환하도록 합니다. Sou..

2021.06.12 퇴사 Solution DFS : 특정 일자에 상담이 가능한지 그 뒤(다음 깊이탐색)로 상담이 가능한지를 재귀적으로 깊이우선탐색합니다. 재귀함수는 다음과 같이 구현할 수 있습니다. 기저조건 : N+1일째 이상을 탐색할 경우 퇴사이므로 0을 리턴합니다. 재귀함수 정의 : 특정 날짜를 입력받아 퇴사할때까지 상담으로 받을 수 있는 금액의 최댓값을 반환하는 함수 해당 날짜의 고객을 상담할 수 있는지 확인합니다. 상담할 수 있다면 금액을 초기값으로 설정하고, 다음 탐색할 노드들을 탐색하고 그 중 최댓값을 더해 반환합니다. DP : 특정 날짜에부터 퇴사일까지 받을 수 있는 최댓값을 메모이제이션합니다. 재귀함수에서 DP에 기록이 되어있다면 반환하도록 하여, 중복된 탐색을 제거할 수 있습니다. Sou..