Trie
leetcode.com/problems/implement-trie-prefix-tree/ ['app', 'apple', 'appear', 'ape', 'boat', 'bear', 'korea', 'korean'] 위와 같은 문자열들의 배열이 있다고 해보자. 위 문자열 안에 특정 문자열, 예를 들면 'ape'가 있는지 찾아보려면 어떻게 해야 할까? 배열 자료구조를 그대로 쓴다면, 처음부터 하나하나 비교해보는 방법밖에 없을 것이다. 전체 문자열의 갯수를 n, 타겟이 되는 특정 문자열의 길이를 m이라 한다면 시간 복잡도는 O(nm)이 된다. 하지만 이보다 명백하게 나은 방법이 있다. 사람이 저 위의 문자열들 중에서 'ape'가 있는지 찾는다면, 우선 'a'로 시작하는 문자들만을 찾을 것이고, 그 다음은 'p'..
1. Insertion 일단 search로 insert해야 할 노드의 위치를 찾아본다. 이 노드가 어떤 상태냐에 따라 다음의 세 가지 경우로 나누어 생각해 볼 수 있다. 1. 노드에 키값이 한 개일때 2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한 개일때 3. 노드에 키값이 두 개고, 그 부모 노드의 키값도 두 개일때 ❗️노드가 루트고 키값이 두개인 경우, '노드에 키값이 두 개고, 그 부모 노드의 키값이 0개일때' 라고 할 수 있으나 이런 경우는 발생하지 않는다. 1. 노드에 키값이 한 개일때 이 경우에는 그냥 그 노드에 넣어주면 끝난다. 예를 들어, 30 / \ 10 35 에 40을 넣으면 30 / \ 10 35,40 이 되고 끝난다. 2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한..
binary search tree를 다른 곳에 저장했다가, 원할때 다시 불러와야 하는 상황을 상상해보자. 예를 들면... 노트북에 랜섬웨어가 들어와서 공장초기화를 해야 하는데 이 binary search tree는 남겨두고 싶어서 usb에 넣어놨다가 복원 후 가져와야 한다든지.. 아무튼 그런 상황에서 binary search tree를 저장하고 불러오는 방법은 두 가지로 생각해볼 수 있다. 1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원 2. binary serach tree내 키들을 정렬된 상태로 저장한 후 더 balanced된 상태로 복원 각각을 자세히 살펴보자. 1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원 형태 그대로 저장한다는..
다익스트라 알고리즘은 그리디 알고리즘이며, 그리디 알고리즘이 최적해를 보장하는 몇 안되는 경우 중 하나이다. 다익스트라 알고리즘은 그래프와 시작 버텍스를 인풋으로 받아 시작 버텍스로부터 이를 제외한 모든 버텍스들로 가는 최단 경로로 구성된 spanning tree를 구성한다. 이 과정에서 시작 버텍스를 subgraph로 두고 이 subgraph를 점점 확장시킨다. 다익스트라 알고리즘은 또한 모든 노드에 대해 시작 노드로부터의 거리, 즉 distance를 저장한 테이블이 필요하다. subgraph를 확장시킬 때마다 그 인접한 노드의 distance를 줄일 수 있는지 확인하고 줄인다. 이를 relaxation이라 한다. 의사코드 def djikstra_algorithm(G, s): S = {s} # dist..
Prim algorithm 의사코드 def prim_algorithm(v): mark v as visited and include it in the m.s.t while there are unvisited verticies: find a least-cost edge(x, u) from a visited vertex x to unvisited vertex u mark u as visited add the vertex u and the edge (x, u) to the m.s.t # if needed, relax u 프림 알고리즘은 weighted graph에서 minimum spanning tree (weight 합이 가장 작은 spanning tree)를 찾기 위한 알고리즘으로, 그리디 알고리즘이 최적인..
DFS def DFS(v): mark v as visited # by array or something for unvisited_vertex in unvisted_vertices_adjacent_to_v: DFS(v) 위 재귀 구조는 함수 호출 스택을 쌓게 된다. 따라서 이 코드를 그대로 스택으로 구현할 수도 있다. 2021/03/13 추가) 코딩테스트 문제 풀 때는 실질적으로 이런 구조로 짜는게 편하다 def DFS(level, node, record): # 1. record record
graph: G = (V, E) 정점(vertex, node) - 어떤 대상물이나 개념 간선(edge) - 관계 subgraph adjacent path cycle simple path: 노드가 중복되지 않는 path simple cycle: 시작점이자 끝점인 노드 외에 어떤 노드도 중복되지 않는 cycle(다른 중복되는 노드가 있다면 그 노드가 subcycle의 시작점이자 끝점이 됨. 즉 simple cycle은 subcycle이 없음) connected cycle: 어떤 두 노드를 잡아도 그 사이에 path가 있는 그래프 complete cycle: 모든 노드 사이에 간선이 있는 그래프 directed graph(digraph) undicrected graph adjacency multigraph: ..