본문 바로가기

CS/알고리즘3

이진 탐색 트리 Binary search trees(BST)이진 트리의 한 종류각 노드에 대해, 해당 노드의 왼쪽 서브트리에 있는 모든 값은 노드의 값보다 작고,오른쪽 서브트리에 있는 모든 값은 노드의 값보다 크다는 특성을 가지고 있음 이진 탐색 트리를 사용하면, 검색, 추가 및 제거와 같은 작업을 평균적으로 O(log n) 시간 안에 수행할 수 있음위 트리에서 20이 존재하는지 확인해보자루트부터 시작하여 20은 23보다 작음. -> 오른쪽 서브트리 무시 가능20 > 8 -> 왼쪽 서브트리 무시 가능20 > 17 -> 왼쪽 서브트리 무시 가능오른쪽으로 이동하며, 값 찾음이 과정의 평균 시간 복잡도는 O(log n)최악의 경우, 오른쪽 자식이 없는 편향된 트리에서는 O(n)이 소요 알아두면 좋은 점BST에서 왼쪽을 우선으.. 2024. 8. 6.
이진 트리 유형 (BFS) BFSDFS에서는 깊이를 우선시했지만, 너비 우선 탐색(BFS)에서는 너비를 우선시 함노드의 깊이는 루트부터 해당 노드까지의 거리임. 따라서 DFS에서는 리프 노드에 도달할 때까지 탐색했음반면, BFS에서는 다음 깊이로 이동하기 전에 같은 레벨에 있는 모든 노드를 먼저 탐색함예를 들어, 위 트리를 BFS하면 0, 1, 2, 3, 4, 5, 6, 7, 8 순서로 노드를 탐색함DFS는 재귀를 사용했지만, BFS는 반복문을 사용함 BFS와 DFS를 언제 사용할까?많은 문제는 모든 노드를 방문하는 것이 중요하기 때문에 DFS, BFS 어떤 것을 사용해도 크게 문제되지 않음DFS는 재귀를 사용하기 때문에 코드가 간결하고, 구현이 쉬움하지만 노드를 레벨에 따라 처리하고자 하는 문제에서는 BFS의 사용이 더 적절한 .. 2024. 8. 6.
이진 트리 유형 (DFS) 이 유형을 파악하기 전에 이진 트리가 무엇인지, 코드에서 어떻게 표현되고 있는지, 그리고 재귀에 대해서 잘 이해하고 있는지를 체크해보세요 오늘은 이진 트리를 순회하는 방법에 대해 알아볼 것입니다. 트리를 순회하는 것은 트리 내의 요소에 접근하는 방법이고, 이는 트리 관련 문제를 해결하는데에 있어 필수적입니다. 기존 LinkedList에서의 요소 순회func getSum(_ head: ListNode?) -> Int { var ans = 0 var current = head while current != nil { ans += current!.val current!.next } return ans} head부터 시작하여 연결 리스트의 모든 .. 2024. 7. 31.