dfs
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
2022.05.28문제 풀이 해당 문제는 subset(부분집합) 을 만들어서 전체 배열의 원소의 합을 2로 나누었을 때 부분집합 의 합과 똑같으면 YES 다르면 NO 를 출력 하는 방식으로 접근 해보았다. 먼저 부분집합을 만드는 방식에 있어서 해당 원소를 부분집합으로 포함 할지 안할지 이렇게 2진 트리로 재귀호출을 할수 있다. func SameSumSubSet(depth, sum int) { SameSumSubSet(depth+1, sum+array[depth]) SameSumSubSet(depth+1, sum) } depth 와 함께 sum 이라는 변수를 재귀호출 로 넘김으로써 depth 가 N 과 같아졌을때 총합 / 2 와 비교하기 위해서 사용한다. 첫번째 재귀 호출은 해당원소를 부분집합으로 사용하는 재귀호출이고 두번..
DFS 이론
DFS 이론
2021.09.05전위 순회(preorder) 트리의 전위 순회는 루트노트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방식이다. 코드 역시 현재 노드를 출력한 후, 왼쪽, 오른쪽 순서대로 함수를 호출한다. 중위 순회(inorder) 트리의 전위 순회는 왼쪽 서브 트리 -> 루트노트 -> 오른쪽 서브 트리 순으로 순회하는 방식이다. 코드는 왼쪽 함수 호출, 현재 노드 출력, 오른쪽 함수 호출 순서로 진행된다. 후위 순회(postorder) 트리의 전위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트노트 순으로 순회하는 방식이다. 후위 순회 또한 왼쪽 함수 호출, 오른쪽 함수 호출, 현재 노드 출력 순서로 진행된다. package main import "fmt" func dfs(v int) { if..