알고리즘 (1) 썸네일형 리스트형 [Algorithm] DFS란? 개념 및 푸는 방법(프로그래머스 타겟 넘버) / golang 코딩테스트에서 가장 많이 나오는 문제가 바로 DFS이다. (BFS보다 더 많이 나옴) DFS 개념: 깊이 우선 탐색으로 인접한 노드 중 하나를 골라서 탐색을 하고, 또 그 노드의 인접한 노드 중 하나를 골라서 탐색해나감. 1 2 3 4 5 이런식으로 그래프가 있으면 1->2->4->5->3 순서로 탐색이 진행된다. 이 때, 1의 인접 노드는 2와 3이 있는데 이 순서는 문제에 주어진 기준에 따라 변경할 수 있다. 푸는 방법: 앞에서 DFS 개념을 설명할 때 인접한 노드 중 하나를 골라서 탐색하고, 또 그 노드 중 하나를 골라서 탐색해 나가는 방법이라고 했는데, 사실 이 개념 설명에 힌트가 있다. 바로 문장 자체가 반복된다는 점인데, 이 반복에서 재귀를 떠올릴 수 있다. 재귀는 stack이 기반이므로 당연.. 이전 1 다음