프로그래머스에 타겟넘버라는 문제 있거든
예를들어 [1,1,1]이라는 배열을 주고, "-"나 "+"를 붙여서 나올 수 있는 조합 중 타겟넘버랑 같은 경우의 수를 찾는거거든
BFS던 DFS던 아래처럼 시작하는거라고 이해를 했어
그럼 DFS의 경우에는
이 순서로 탐색을 해보면서 결과를 내잖아
그럼 이런 결과가 나오잖아? 괄호 안에 값이 결과가 나오는 순서고 옆에가 결과라고 할 때, 타겟넘버를 3이라 할때 어차피 14번까지 가서 (8)의 결과까지 봐야해
이제 다음으로 BFS야
어차피 14번까지 가서 (8)의 결과까지 봐야해
근데 궁금한게 GPT가 이 문제를 BFS로 푸는게 더 유리하다고 하거든
도대체 왜그런건지 알려줄 수 있어?
BFS는 큐 기반이고
DFS 스택 기반이잖아
이게 이해가 안가면 설명해줌
아 그럼 DFS에서는 괄호에 숫자가 반대로 나오겠구나..근데 결국에 다 돌아봐야하는건 같은거 아니야? 멍청해보이면 미안 진짜 이해가 안돼서
흠 개념이 좀 부족하군
쉽게 설명 추가로 해줌
고마워 형 ㅠㅠ
DFS는 동굴 탐험으로 따지면 한 길따라 끝까지 간 후에, 길 막히면 다시 도될아가서 새로운 길을 가는 방식임 BFS는 그냥 모든 갈림길 추적한 후에 층에 있는 모든 갈림길 확인하고 내려가는 방식 그러니까 이 경우에 BFS가 빠른거야
아 그럼 BFS는 다음 동굴 가기전에 값을 예상해보고 아예 안들어가버릴 수도 있어서 빠른거야?
https://gall.dcinside.com/board/view/?id=programming&no=2849747&page=1
https://gall.dcinside.com/board/view/?id=programming&no=2849747&page=1
글하나 쓴다
헉 나도 이거 방금 풀었는데 ㅋㅋㅋ 나는 이 문제 보고 bfs 보다는 dfs를 먼저 생각했음. bfs는 최단거리 구할 때 더 적합하고, 더군다나 이거는 모든 경우의 수를 찾아야 되니까 dfs가 맞다고 생각했음(물론 bfs로도 풀 수 있지만). 그리고 이 문제는 numbers 크기가 20 이하이므로 2^20 < 1억 이니까 괜찮겠지만, 재귀호출시 효율성도 고려해 “가지치기”도 생각했음. i 번째 숫자를 음수로 선택하면 누적합에 i번째 수의 음수버전과 i + 1 부터 나머지를 모두 양수로 간주하고 더할 때, target 미만이면 더 이상 재귀호출 할 필요없거든. 그래서 이거를 음수 더하고 재귀호출할 때 조건문으로 걸어놓음.