나른한코딩_

Trie 문자열 검색 문제에 특화된 트리 형태의 자료구조. 원하는 문자열을 O(m) (m = 문자열의 길이) 시간복잡도로 찾을 수 있다. struct Trie 내의 Trie 포인터 배열을 가지고 해당 키에 맞는 포인터로 이어지는 구조. Trie는 검색 후보 문자열을 하나의 트리로 만들어서, 한번의 검색 O(m) 만으로 문자열의 존재 여부를 검색 가능하다. 주의 항상 첫번째 root 노드는 빈칸이다. 트라이 객체마다 트라이 포인터 배열을 경우의 수만큼 가져야 하므로 공간복잡도가 매우 커질 수 있다. 공간복잡도 : O(key의 경우의수 * 포인터 크기 * 전체 트라이에 존재하는 노드 수) 필수 1) 다음 두 가지를 가지고 있어야 한다. - child (자식 노드를 담는 배열) - isTerminal (어떤 ..

** 작성자가 stack / queue를 연습하면서 작성한 기록을 남긴내용입니다. 나중에 자세한 설명가 추가 내용을 작성하며 수정할 예정입니다. ** Stack - LIFO, array로 구현 - 다양한 자료형을 수용할 수 있도록 generic을 이용 - push, pop 메서드의 경우 구조체 내부에서 데이터를 수정하기 때문에 mutating 키워드를 사용. struct Stack { var stack = [T]() var isEmpty: Bool { return self.stack.isEmpty } var top: T? { return self.stack.last } mutating func push(_ item: T) { self.stack.append(item) } mutating func pop(..

오늘은 DFS와 BFS의 예제를 구현해보며 로직을 이해해보고자 합니다. DFS와 BFS를 구현하려다보니, 그래프를 먼저 구현하는 해야겠더라구요🤔 그런데 그래프를 어떻게 구현해야할지 몰라서 우선은 하드코딩으로 그래프를 생성한 후, DFS / BFS를 구현해보았습니다. 다음 글에 그래프 구현에 대한 글을 올려두겠습니다 😄 DFS와 BFS의 개념을 간단하게 소개한 후 바로 코드로 넘어가겠습니다. . . . . 그래프를 탐색하는 방법에는 크게 DFS와 BFS가 있습니다. 1. DFS (Depth-First Search) '깊이우선탐색(DFS)'은 가장 깊은 노드까지 내려단 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색을 합니다. root 노드(혹은 다른 임의의 노드)에서 시작하여 다른 branch..