Data Structure & Algorithm

[Data Structure] Heap

오늘 알아볼 데이터 구조는 Heap(힙) 입니다. Heap 또한 이전 시간에 알아본 Trie 처럼 기본 구조는 Tree(트리) 형태입니다.Heap의 경우 모든 노드가 두개의 자식노드만 갖는 Complete Binary Tree(완전이진트리)입니다.주로 최대값, 최소값을 구하는 연산에 주로 사용됩니다.특징- 모든 부모 Node와 자식 Node 간의 Key 값은 항상 대소관계를 갖습니다.- 대소관계에 따라 부모 Node의 Key 값이 자식 Node보다 큰 Heap을 Max Heap(최대 힙),반대로 자식 Node의 Key 값이 부모 Node보다 큰 Heap을 Min Heap(최소 힙)이라고 합니다.- 검색 및 삽입 Time Complexity는 Binary Tree의 속성에 따라 O(logN)입니다.- ..

[Algorithm] Dynamic Programming(DP; 동적계획법)

오늘은 알고리즘 기법 중 Dynamic Programming에 대해 알아보도록 하겠습니다. 동적 프로그래밍, 다이나믹 프로그래밍, DP, 동적 계획법 등 다양한 이름으로 불립니다.알고리즘의 핵심은 문제를 작은 하위 문제들로 나누고 하위 문제들의 값을 캐싱하고 활용하여 큰 문제를 해결한다는 점입니다. 접근법DP는 두 가지 접근법이 존재합니다.1. 탑다운(Top-Down) 방식: 재귀와 캐싱2. 바텀업(Bottom-Up) 방식: 반복문을 통한 DP DP의 활용 예제로는 피보나치(Fibonacci) 함수 구현이 있습니다.탑다운(Top-Down) 방식var cache = [Int: Int]()func fibonacci(_ n: Int) -> Int { if let result = cache[n] { ret..

[Data Structure] Trie

오늘은 Trie(트라이) 구조에 대해서 알아보고자 합니다. Trie는 기본적으로 Tree(트리) 형태의 자료 구조입니다.접두사 트리(Prefix Tree)라고도 하며, 주로 문자열 데이터를 다룰 때 사용됩니다.특징- Node의 구조에 따라 다르지만, 특이한 점은 자식 Node가 이전 노드(부모 Node)의 값을 일부분을 공유- 각 Node는 하나의 문자(or 접두어)를 저장합니다.- 문자열의 끝을 나타내기 위한 Leaf Node 플래그를 사용합니다.- Trie의 Root Node는 공백 문자 또는 빈 값을 저장합니다.- 검색 및 삽입 Time Complexity는 문자열의 길이에 비례하여 O(M)입니다.(M = 문자열의 길이)구현1. TrieNode 구조체 정의class TrieNode { var ..