코딩 공부 블로그

여러가지 방법으로 해결할 수 있는 문제라서 풀어보았다. 1. Brute force 방식 무식한 힘으로 해석되는데, 완전탐색 알고리즘이다. 가능한 모든 경우의 수를 모두 탐색해 요구조건에 충족되는 결과만을 가져온다. 예외 없이 100%의 확률로 정답을 출력한다는 점이 좋은 점이다. 다른 블로그에서 빌려온 말. 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색..

- DFS(깊이 우선 탐색) 사용 public class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { return 0; } int currentVal = (root.val >= low && root.val high){ return rangeSumBST(root.left, low, high); } else { return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high); } } } Backtracking 알고리즘을 사용했다. 이것도 O(n)이다.