본문 바로가기

CS9

이진 탐색 트리 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.
Queue Queue한쪽 끝(rear)에서 데이터의 삽입(enqueue)이 일어나고, 반대쪽 끝(front)에서 삭제(dequeue)가 일어나는 선형 자료구조그런 구조이기 때문에 FIFO의 형태로 동작 시간 복잡도rear나 front 외, 원소들의 확인 및 변경은 원칙적으로 불가능연산의 시간 복잡도Rear나 front에 원소 추가(enqueue), 제거(dequeue)O(1)Rear나 front의 원소 확인O(1) 구현배열이나 연결리스트 등으로 구현 가능구현struct Queue { private var array: [T?] = [] private var frontIndex = 0 var front: T? { guard frontIndex T? { guard fr.. 2024. 7. 24.
Stack 유형 - 문자열 문자열 문제스택을 사용하는 문자열 문제는 자주 나옵니다. 일반적인 문자열 문제는 문자열을 순회하면서, 문자를 스택에 넣고, 각 반복에서 현재 문자와 스택의 맨 위 문자를 비교하는 것이 있습니다. 스택은 가장 마지막 문자를 가지고 있기 때문에 문자열 매칭에 유용합니다.  예제 1주어진 문자열 s는 (, ), {, }, [, ] 만 포함합니다.입력 문자열이 유효한지 판단하세요.문자열이 유효하려면 모든 여는 괄호가 동일한 유형의 닫는 괄호에 의해 올바른 순서로 닫혀야 하며, 각 닫는 괄호는 정확히 하나의 여는 괄호를 닫아야 합니다.예를 들어, s = ( { } ) 는 유효하지만, s = ( ] 는 유효하지 않습니다. 방법올바른 순서는 이전의 여는 괄호가 무엇이었는지에 의해 결정됩니다. 닫는 괄호가 나타날 때마.. 2024. 7. 23.
Stack Stack한 쪽 끝에서만 데이터의 추가(push)와 삭제(pop)가 일어나는 선형 자료구조이러한 구조로 인해 Last In First Out의 형태로 동작 시간복잡도최상단 원소를 제외한 나머지 원소들의 접근 및 변경은 원칙적으로 불가능추가 (Push)O(1)제거 (Pop)O(1)최상단 원소 확인 (Top)O(1) 구현배열이나 연결리스트 등으로 구현이 가능ex) 배열을 이용한 구현struct Stack { private var array: [T] = [] var size: Int { array.count } var isEmpty: Boot { array.isEmpty } var top: T? { array.last } mutating func push(_ newEl.. 2024. 7. 23.

티스토리툴바