반응형
목적:
DFS 알고리즘의 재귀적 특성을 이해하기 위해서
문제 설명(요약):
N개의 문제에 대한 각 점수와 각 문제를 풀기 위한 시간이 주어졌을 때,
정해진 M시간 내 에서의 최대 점수를 찾는문제
해결전략:
노드를 탐색하며(L++) 주어진 입력(점수,시간)을 쓴다 안쓴다 (sum++ or sum, time ++ or time)
-> 재귀 함수로 구현
재귀함수에 대한 이해:
arr = [[점수,시간],[점수,시간],,,,,,[점수,시간]]
DFS(L+1,sum+arr[L][0],time+arr[L][1]) # 노드를 사용한다 1번
DFS(L+1,sum,time) # 노드를 사용하지 않는다 2번1번 함수를 호출 했을 때
-> 만약에 시간이 초과되면 return 후 돌아와서 2번함수 호출 (stack 자료구조)
-> 만약에 시간 초과되지 않고 깊이 우선 탐색이 끝나면 최댓값 할당
2번 함수를 호출 했을 때
-> 1번 함수가 시간 초과 났을 때 발동
-> 사용할 수있는 노드를 찾을 때 까지 탐색 찾으면 1번함수로 점수,시간을 증가 탐색 후 최댓값 할당
반응형