개념공부/알고리즘13 Monotonic Stack, 단조 스택이란? Monotonic Stack (단조 스택) Monotonic Stack은 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 의미한다. Monotonic Stack 그 자체로 유용함은 없지만, 정렬되어 있지 않은 배열을 Monotonic Stack으로 만드는 과정 혹은 Monotonic Stack에 새로운 원소가 입력되었을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다. 이를 사용해 풀 수 있는 문제들이 있는데, 대표적인 문제는 Find Next Greatest Number 이다. Brute Force로도 풀 수 있지만 Time Complexity : O(n^2)이므로 입력 배열의 원소 개수가 많을 수록 불리하다. 이때 Monotonic Stack을 만드는 과정에서의 정보를 이.. 2023. 7. 24. Backtracking Algorithm Method 백트래킹 알고리즘은 모든 솔루션을 탐색해볼 수 있는 방법이다. 탐색 과정은 Tree 자료 구조를 DFS(depth first order)로 탐색하는 것과 동일하다. Tree 자료 구조를 기준으로 Partial Candidates는 tree의 Node로 표현되고, 1 depth 마다 부모 노드의 partial candidates에서 자식 Node의 값이 추가된다. 수많은 솔루션에서 정답만 찾아야 한다면, 백트래킹은 다음과 같이 동작한다. DFS와 같이 root node에서 부터 tree를 재귀적으로 순회한다. 각 노드에서 알고리즘은 노드가 valid solution인지 체크한다. 만약 solution이 아니라면 스킵한다. 정답이라면 저장한다. 특정 Depth에서의 노드 값들의 배열을 저장해야 .. 2023. 3. 9. Binary Tree Traversal, Binary Tree Leetcode의 문제를 풀려고 설명을 읽던 중 inorder traversal 이란 단어에서 막혔다. 몇몇 Tree 문제를 풀었는데도, 처음 보는 단어가 튀어 나와 공부할게 생겼다. traversal이란 Binary Tree 자료 구조의 모든 노드를 방문할 수 있는 방법이다. 선형 자료 구조 (연결 리스트, 스택, 큐 등)은 순차적으로 접근하지만 Tree 자료 구조의 접근 방식은 다르다. 보통 Tree에서는 Depth First Search (DFS), Breadth Frist Search (BFS)를 사용해 노드 순회 및 탐색이 가능하다. Binary Tree인 경우 위 두 방법과 함께 Recursion 방법을 사용해 순회 및 탐색이 가능하다. DFS로 Tree를 순회할 경우, Queue를 활용하면 .. 2023. 3. 7. 이진 검색 알고리즘 (Binary Search Algorithm) 이진 검색 알고리즘 (Binary Search Algorithm) 오름차순 (혹은 내림차순)으로 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘 시작과 마지막 범위 내에서 중간의 값을 임의로 선택하여 찾고자 하는 값과 비교 중간 값이 찾는 값 대비 작다면, 시작 범위를 중간 값으로 설정 중간 값이 찾는 값 대비 크다면, 마지막 범위를 중간 값으로 설정 장점 특정 값을 찾기 위해 배열의 모든 인덱스를 모두 탐색하는 것 대비, 탐색 범위를 절반씩 줄여나가기 때문에 속도가 빠르다. 단점 배열이 정렬되어 있어야 한다. 정렬을 위한 연산이 소요 된다. 적용 문제 예시 배열 내에서 Target 값과 가까운 3개의 원소를 찾는 문제 모든 원소를 탐색하면 O(n^3)의 Time Complexity인데, 이진 탐색 알고.. 2023. 1. 26. Trie 자료 구조 우리나라 발음으로 트리에 인줄 알았는데, 트라이 라고 함 ㅎㅎ. Trie 자료 구조 Trie 자료 구조는 string으로 인덱싱 할 수 있는 Look Up 자료 구조의 형태이다. 이는 사전식 순서로 데이터를 저장하거나 string을 탐색하는데 효율적인 방식으로 문장이나 단어 예측 및 자동 완성, 스펠 체크 등에 사용된다. Trie 자료 구조는 Tree 형태의 자료 구조로 digital tree, prefix tree 라고도 불린다. 주로 string을 저장하는데 사용되며 Tree Node는 각 character를 저장한다. 모든 자식 노드는 공통된 prefix string의 부모 노드들을 가지고, root 노드는 empty string이다. (이렇게 prefix로 접근해 데이터를 접근하는 방식이 메모리를.. 2023. 1. 25. Dijkstras Algorithm (다익스트라 알고리즘) FunctionAlgorithm for finding the shortest paths between nodes in a graph It fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in a graph It uses a data structure for storing and querying partial solutions sorted by distance from the "source" node (Queue, prioirty - Queue in C++) Time Complexityprioirty queue - $$ \Theta ((\left| V \right| + \le.. 2023. 1. 15. 이전 1 2 3 다음
