Data Structure & Algorithm/Data Structure

[Data Structure] Monotonic Stack

Monotonic Stack이라는 구조에 대해 알아봅시다.오늘 LeetCode의 Daily Question이 Monotonic Stack을 활용하는 문제이기 때문에 제대로 한번 알아보려고 합니다. 특징Monotonic의 사전적 의미를 찾아봅시다.단조로운 Stack? 무슨 의미일까요?2번 의미처럼 값이 증가 혹은 감소하는 단방향 변화만 존재하는 Stack을 의미합니다.// General StackBottom [4,3,12,5,6,1,31,7,13] Top// Monotonic Increasing StackBottom [1,3,4,5,6,7,12,13,31] Top// Monotonic Decreasing StackBottom [31,13,12,7,6,5,4,3,1] Top 그럼 Stack에 값을 추가할 때..

[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)입니다.- ..

[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 ..