DeFacto-Standard IT

너비 우선 탐색 알고리즘 (BFS, Breadth First Search) 트리를 조회할 때, 너비를 기반하여 우선적으로 조회한다. 하나의 노드에는 여러 개의 노드가 연결되어 있는데, 특정 노드와 근접한 노드부터 검사한다. 트리에는 깊이라는 개념이 있다. 0번 노드는 깊이가 1이며, 1, 2번 노드는 깊이가 2이다. 그 밑으로 3, 4, 5, 6번 노드는 깊이가 3이고, 그 이후는 1씩 추가된다. 너비 우선 탐색(BFS)는 깊이 우선 탐색(DFS)과 다르게, 루트 노드에 인접한 노드를 먼저 모두 검사한 후, 그 다음 서브 노드로 옮겨서 그 서브 노드에 인접한 모든 노드를 검사하는 방식으로 동작한다. BFS의 구현은 DFS에서 사용했던 Recursive Call 만을 사용해서는 구현하기 힘들다. Recur..

깊이 우선 탐색 알고리즘(DFS, Depth First Search) 트리를 조회할 때, 깊이를 기반하여 우선적으로 조회한다. 하나의 노드에는 여러 개의 노드가 연결되어 있는데, 특정 노드의 한쪽 방향의 끝까지 먼저 검색한 후 다른 방향의 노드를 검사한다. 구현은 Recursive Call 혹은 Stack을 사용한다. 위 그림에서 0번 노드시작으로, 왼쪽 노드부터 내려가면서 1. 자신 검사 2. 왼쪽 노드 검사 3. 오른쪽 노드 검사 를 반복하게 된다. 이 때, 왼쪽 또는 오른쪽의 서브노드 검사 중 서브노드의 왼쪽, 오른쪽 서브노드가 또 있으면 위 과정을 계속해서 반복하게 된다. 트리는 배열로도 표현할 수 있지만, LinkedList로 표현하는 것이 일반적이다. 각 노드는 left, right라는 서브 ..

분할 정복 알고리즘의 일부 탐색법이다. 검색해야 할 대상(arr)을 절반씩 잘라서, 찾으려는 숫자(target)의 범위를 포함하는 서브 대상에서 다시 똑같은 방법으로 찾는다. 단, 절반으로 잘라서 찾는 분할정복법의 특정 상 속도는 굉장히 빠르지만, 배열은 정렬이 되어 있어야 한다는 제약이 따른다. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 이라는 배열이 있고, 여기서 8을 찾는다고 가정해보자. left는 찾으려는 현재 배열의 가장 작은 값(가장 왼쪽 값) right는 찾으려는 현재 배열의 가장 큰 값(가장 오른쪽 값) mid는 찾으려는 현재 배열의 중간값 (가장 가운데 값) 을 뜻한다. - 1차 계산 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 현재 배열에서 le..

- 개념 계산한 결과가 이후에 또 다시 필요할 경우, 재계산하지 않고 저장해놨다가 다음 계산에 재사용하는 알고리즘. - 대표적인 문제 LeetCode - 53. Maximum Subarray