본문 바로가기

IT/Algorithm16

Window Sliding Technique 알고리즘 기법 중 윈도우 슬라이딩(Window Sliding)에 대해 알아보려고 한다. 말 그대로 윈도우 슬라이딩은 윈도우를 움직이는 것이다. 즉, k 크기의 윈도우를 먼 쪽으로 움직인다. (물론 윈도우를 움직이는 방식은 문제를 어떤 식으로 정의하는지에 따라 달라질 수 있다.) 한 예를 들어보면,Array[] = {5, 2, -1, 0, 3}, 윈도우 크기 k = 3라면, 인덱스 0번 부터 연속되는 3개를 포함하는 윈도우를 오른쪽으로 한 칸씩 움직이게 되며 인덱스 2번이 마지막이 된다. (슬라이딩 윈도우 정의를 위한 단순 예시) 그러므로 해당 기법을 정리하면 아래와 같이 간단하다.1. 윈도우 크기를 정한다.2. 윈도우 크기 만큼 인덱스 0번 부터 마지막 까지 움직이다. (고정된 크기의 윈도우에 항상 값이.. 2019. 6. 22.
Trie Trie에 대해 알아보려고 한다. Trie를 간단히 설명하면 문자열을 저장하는 트리 기반의 자료 구조이다. 자세한 내용을 알아보기 전에 코드를 살펴면서 어떤 것인지 알아보도록 하자. 그림 1. Trie 그림 1을 보면 트리의 노드 마다 각각의 문자가 담겨있는 것을 확인 할 수 있다. 이는 Trie는 문자열을 문자로 하나씩 쪼개서 자식 노드로 만든다. 그러므로 그림 1을 다시 살펴보면..- geer- geeks- geekt- geez총 4개의 문자열이 있음을 알 수 있다. (추가로, 문자열의 각 인덱스가 노드의 깊이인 것 또한 확인 할 수 있다.)그런데 특이하게도 루트 노드는 특정한 문자로 표현되지 않는다. 곰곰이 생각해보면 쉽게 알 수 있는데 예를 들어 'G' 문자로 루트 노드를 시작하면 Trie에서는 .. 2019. 6. 11.
Topological Sorting 위상 정렬이라고 불리는 Topological Sorting 에 대해 알아보려고 한다. Topological Sorting은 Directed Acyclic Graph (DAG)를 사용하여 Vertices를 순서 있게 나열하는 것이다. (즉, DAG 형태가 아니라면 해당 정렬은 사용할 수 없다.) 그림 1. DAG 그런데 기본 구조인 그래프의 특성상 정렬 방법은 여러개가 될 수 있다.그림 1을 보면 (5, 4, 2, 3, 1, 0), (4, 5, 2, 3, 1, 0) 이렇게 2개가 될 수 있다. 이는 시작점은 항상 들어오는 부분이 없는 (in-degree가 0) 정점이 되어야 한다. 이를 바탕으로 그림 1을 보면 In-degree가 0인 부분은 2개(5, 4) 이다. Topological Sorting의 구.. 2019. 6. 10.
Segment Tree Segment Tree는 Tree의 일종으로 각 노드에 특정 범위에 대한 정보가 담겨있다. (범위를 Interval, Segment 등으로 표현한다.) Tree의 응용은 당연스럽게 기존의 방식으로는 시간 복잡도가 높기 때문이다. 한 가지 예를 든다면, [1,2,3,4,5]의 트리에서 (배열로 구성된 트리) 2~4 사이의 합을 알고 싶다면 어떻게 해야 할까?누구나 접근할 수 있는 쉬운 방법은 전체를 다 훑어보는 것이다. 그렇다면 O(n) 정도의 시간 복잡도가 나온다. 그런데 만약 부분합과 같이 각 노드에 미리 합쳐진 값이 존재한다면 O(1)과 같이 상수의 시간 복잡도로 범위 값을 찾을 수 있다. 이렇듯 Segment Tree는 범위에 대한 정보를 미리 저장함으로써 다음 계산시에 사용할 수 있도록 한다. 때.. 2019. 6. 7.

티스토리툴바