아는 개발자 아는 개발자

알고리즘/자료구조

• 인덱스 트리

  알고리즘/자료구조 2015. 7. 7. 18:05

  일정 데이터 집합에 대하여 구간별로 특정한 데이터를 저장해둔 것을 인덱스 트리라 한다. 특정 값은 주로 최대값이나 최소값을 의미한다. 위 자료구조를 통해 주로 Min Max Tree를 만든다. 만드는데 시간이 상당히 오래 걸리며 한 번에 깔끔히 완성하는 것은 상당히 어렵다. BIT에서 해결하지 못했던 최대 최소 문제를 해결해줄 수 있는 알고리즘이긴 하지만... 구현하는데 시간이 오래걸리는 것은 아쉽다. int tree[20][100000]; void update(int height, int piv, int data){ if(height==18) return; if(tree[height][piv] < data){ tree[height][piv] = data; update(height+1, piv/2, da..

  Read More
• union find

  알고리즘/자료구조 2015. 6. 27. 11:04

  알고리즘 문제를 풀다 보면 노드들 간의 집합이 존재하는 경우가 있다. 이때 해야할 일이 크게 두 가지 있다.1. 두 노드가 같은 집합에 포함되어 있는지, 다른 집합에 있는지 확인하는 작업2. 두 집합을 병합하는 작업 사람마다 위 과정을 처리하는 방법이 모두 다르고 시간복잡도도 다르다.나 또한 무식하게 문제를 풀때는 O(n^2)이렇게 풀기도 했다. 하지만 위 작업을 최적화한 자료구조로 union find가 있다.(양교수님께서 알려주신 내용인데 당시에는 학점받기에 급급해 제대로 공부하지 못했다.) 그림파일 올리려고 했는데 귀찮아서 못올리겠다http://blog.secmem.org/521좋은 블로그가 있으니 여기를 참고하길.. void init(int n){ for(int i = 1; i

  Read More
• 오일러회로

  알고리즘/자료구조 2015. 2. 27. 15:21

  오일러 회로는 그래프의 모든 간선을 방문하고 시작점과 끝점이 같은 회로를 말한다. 우리에게는 연필로 모든 간선을 칠하고 다시 돌아오는 것으로 친숙하다. 별표그릴때를 생각해보면. 이 회로를 만들기 위한 조건은 각 정점들마다 나가고 들어오는 간선의 수가 같아야 한다(무방향의 그래프는 정점과 연결된 간선의 수가 짝수개여야 한다) 정말 간단히 생각하면 된다. 어떤 정점의 나가는 간선의 수가 들어오는 간선의 수보다 적다면 그 정점으로 들어오는 간선들은 아직 방문하지 못한채 그 정점에서 나가지 못하게 된다. 위의 그림에서 정점은 2개의 나가는 간선과 3개의 들어오는 간선이 있다. 검은색 간선은 이미 방문 한 것이고 파란색 간선은 아직 방문하지 않는 것이다. 현재 위치는 정점 3인데 여기서 더이상 어느 곳으로 나갈 ..

  Read More
• 트라이

  알고리즘/자료구조 2015. 2. 27. 14:35

  요즘 운영체제에서는 단어 몇글자만 치면 자동완성 기능을 제공하는데자동완성의 기본 알고리즘이 바로 트라이다. 자동완성을 만들려면 사전에 입력한 단어들을 저장하고 빠른시간안에 탐색 할 수 있어야 한다. 하지만 문자열은 숫자로 이루어진 이진트리와 달리 원소 비교를 상수시간 내에 할 수 없으므로 특화된 자료구조가 필요하다. 이때 유용한 자료구조가 트라이다. 구조는 다음과 같다. 만약 내가 TR, THE, TRY, TREE라는 단어를 저장해두었다고 하자. 그러면 다음과 같은 트리가 형성된다. 각각의 단어의 공통된 접두사를 부모로 두는 방법이다. 하지만 공통된 접두사가 내가 입력한 단어가 아니라면 bool 값을 이용해서 표현해야한다. 그림에는 하얀색 바탕으로 표현했다. 위 자료구조의 시간 복잡도는 트리의 높이로 볼..

  Read More
• 트립(Treap)

  알고리즘/자료구조 2015. 2. 25. 11:19

  이름에서도 예측 할 수 있듯이 트립(Treap)은 Tree + Heap인 자료구조이다. 기존 이진 트리는 어떻게 내가 삽입(insert)하느냐에 따라서 트리의 높이가 O(N)이 될 수 있고 O(logN)이 될수도 있는 문제점이 있다. 트리구조의 기본적인 목표는 최대한 높이를 낮추어 탐색의 시간을 빠르게 하는 것이 목적인데 높이가 O(N)되면 선형 구조와 다를바가 없어진다. 즉 균형의 문제가 발생한다. 균형의 문제를 해결하기위한 자료구조로는 AVL Tree와 Red Black Tree가 있는데 이것들은 구현하기가 어렵다. 그래서 간단히 Heap의 성질을 이용해서 구현한것이 Treap이다. 방법은 다음과 같다. 1. 삽입할 노드들에게 난수값으로 우선순위를 부여한다.2. 노드가 어떤 subtree의 루트가 될..

  Read More
• 접미사배열

  알고리즘/자료구조 2015. 2. 24. 21:23

  문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.예를 들면 Algorithm이면 접미사들로는m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데이것들을 사전 순데로 정리해서 Algorithmgorithmhmithmmorithmrithm으로 나타낸 것이다. 어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다 하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.우리가 어떤 문자열을 찾는다면처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N) 위 처럼 정리해두면 O(N*logN)이 걸린다. 단순하면서도 ..

  Read More
• KMP 알고리즘

  알고리즘/자료구조 2015. 2. 24. 18:38

  예전에 KMP는 왜 KMP인가라는 문제를 보고 KMP이거 뭐지 장난하는건가 싶었는데;문자열에 관한 알고리즘인걸 책을 보고 깨달았다.. 이렇게 심오하고 환상적인 알고리즘이 있었다니 ㄷㄷ KMP알고리즘은 어떤 문자에서 특정 문자열이 존재하는지 확인하는 방법이다.예를 들어 길이가 N인 문자열에서 M이라는 문자열이 있는지 없는지 확인하고 싶으면N의 모든 위치에서 M의 시작문자와 비교해보는 방법이 있다. 이 방법은 O(MN)이 든다. 하지만 KMP알고리즘은 모두 비교하지 않고 접두사 접미사의 개념을 활용해서 푼다. 예를들어 abcabce -> 문자열 Mabcabcabcd -> 문자열 N 위의 M과 N을 비교했더니 abcabcabc까지는 같고 뒤에부터 달랐다.그런데 다음 비교를 N의 두번째 문자열 부터 시작 하지 ..

  Read More
• BIT(Binary Indexed Tree)

  알고리즘/자료구조 2015. 2. 21. 21:56

  어려운거 많이 가르치기로 소문난 양교수님께서 왜 BIT를 설명 안해주셨을까이렇게 감탄스러운 자료구조가 있는 줄 몰랐다.RB Tree, AVL, 24 Tree이런거는 구현이 어려운데이거는 구현도 어렵지 않고 편리하다 간단히 소개를 하면기본적으로 어떤 data를 추가 할 때 O(1) 그리고 그 data의 총 합을 구할 때는 O(n)이 걸린다. 하지만 BIT는 추가 할때도 O(logn) 총 합을 구할 떄도 O(logn) 시간이 걸리는신기한 자료구조이다. http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길... 나는 이것을 어떻게 응용할 것인지를 생각해보면..

  Read More