트라이(trie)는 prefix tree 라고도 하며,
정렬된 트리 데이터 구조체로서 associative array을 저장하는데 사용되며,
키들은 보통 문자열이다.
활용분야: 문자열 검색, 단어사전...
비트벡터(bit vector, bit array, bitmap, bitset, bitstring 이라고도 함)
개별적인 비트(boolean values)들을 저장하는 array data structure이다.
블룸필터(Bloom filter)는 1970년도에 Burton H. Bloom이 고안한 것으로
공간 효율적인 probabilistic data structure이며
구성요소가 집합의 구성원인지 점검하는데 사용된다.
False positive들이 가능하며, false negative들은 불가능하다.
요소들은 집합에 추가될 수 있으나 제거는 되지 않는다.
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
1-1 최단 경로 찾기 같은 문제는 전통적으로
1) 그래프를 트리로 어떻게 바꾸느냐 (spanning tree) + 2) 트리 안에서 원하는 노드를 어떻게 찾느냐 (tree search)
의 문제입니다. 거의 모든 CS 문제가 그렇지만 문제만 정확히 정의하고 나면 완벽한 자료구조의 문제죠.
먼저, 우리가 일생생활에서 지하철을 이용하는 사례를 정리해 보면,
1. 지하철 출발역으로 들어선다.
2. 지하철 노선도에서 출발역과 목적지역을 확인한다.
3. 이동하는 경우의 수를 따져보고, 최단경로를 찾는다.
4. 가장 최적의 최단경로를 선택, 이동하여 목적지역에 하차한다.
우리는 지능적인 뇌을 활용하여 위의 2번과 3번을 아주 쉽게 처리하지만,
컴퓨터는 논리연산(boolean)을 단순히 반복처리만 하기 때문에,
처리대상을 자료구조화 하여야 합니다.
일단, 위의 2번은 그래프로 자료구조화할 수 있을것 같습니다.
그래프로 지하철 노선의 노드수를 아래의 루프처럼 계산해 보면,
지하철 노선종류(1호선~9호선): n = 9;
지하철역 개수(추정개수): m = 300;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
따라서, 지하철 노선의 노드수 = n x m = 2700;
위의 값은 제가 예를들어 본 추론값이며, 숫자보다는 접근방식에 의미가 있습니다.
또한, 갈아타는 지하철역이 있어서, 이동하는 경우의 수를 단순한 루프로
처리한다면, 중첩되는 for 루프의 수는 아래와 같이 증가할 수 있습니다.
지하철 노선을 그래프로 표현하기에는 좋지만,
그래프는 이동의 방향성이 너무 많기 때문에,
3번의 최단경로를 찾기 위해서는,
이동의 방향을 정하여 효율적으로 탐색할 수 있는 트리구조로 변환합니다.
즉, 그래프(이동하는 경우의 수) --> 최단경로탐색(트리)
트리는 Root와 Left, Right를 탐색하는 순서에 따라서,
PreOrder, InOrder, PostOrder등으로 정해져 있고,
for (i = 0; i < n; i++)
for (j = 0; j < m; j *= i)
위의 루프 형태로 탐색되기 때문에, 탐색효율 = O(n) = n x log(m);
로 계산될 수 있습니다. 따라서, 최단경로는 이값이 가장작은 것을 찾아보면 될것입니다.
저는 추론에 의한 접근방식에 의미를 두었기 때문에 잘못된 점이 있을 수 있습니다.
단순히, 그래프와 트리의 특성에 대해서만 언급했으므로,
최단경로를 찾기위한 효율적인 자료구조(그래프와 트리응용, 혹은 새로운 개념의 자료구조)
가 있을것이며, 이것을 연구하고 고민하는 것은 의미있는 일이라고 생각합니다.
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
Skip list 같은 확률적인 자료 구조들이 재밌습니다. (확률적이라고 썼지만 bloom filter 같이 일정 확률 이하로 오답을 내 놓는 게 아니라 complexity guarantee가 난수 생성기에 의존한다는 뜻입니다.) Skip list 같은 건 balanced binary search tree(red-black 등)랑 비교해도 괜찮은 것 같은데 비교적 최근에 나왔기 때문인지 학과 과정에서는 잘 안 보이는 것 같아요.
몇가지
셋, 맵, 디큐, 우선순위 큐, 해시, 벡터, 힙, 트라이, 비트 벡터, 블룸 필터 등이 떠오르네요.
10여년전...
학교 다닐때,
자료구조 수업을 들을때는 이걸 배워서 어디에 사용하는지 몰랐는데,
(응용할줄 몰랐고, 하찮게 생각했어요.)
그런데,
이게 엄청 중요한 것이라고 새롭게 깨닫고 있습니다.
말씀하신,
셋, 맵, 디큐, 우선순위 큐, 해시, 벡터, 힙, 트라이, 비트 벡터, 블룸 필터 중에서
디큐, 우선순위 큐 --> 큐
해시 --> 검색
힙 --> 트리 쪽으로 연관되는듯 하네요.
그런데,
셋, 맵, 벡터, 트라이, 비트 벡터, 블룸 필터는 저는 처음 듣는 것이라서,
이것이 언급되어 있는 참고서적을 추천해 주실 수 있는지요?
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
위키백과
셋(set), 맵(map), 벡터(vector)는 자바 Collections에 들어 있으니 그걸 참고하시구요, 나머지는 위키백과 글들이 괜찮습니다.
트라이 http://en.wikipedia.org/wiki/Trie
비트 벡터 http://en.wikipedia.org/wiki/Bit_vector
블룸 필터 http://en.wikipedia.org/wiki/Bloom_filter
위의 위키백과를 참조해서, 앞부분만 요약해 봅니다.
트라이(trie)는 prefix tree 라고도 하며,
정렬된 트리 데이터 구조체로서 associative array을 저장하는데 사용되며,
키들은 보통 문자열이다.
활용분야: 문자열 검색, 단어사전...
비트벡터(bit vector, bit array, bitmap, bitset, bitstring 이라고도 함)
개별적인 비트(boolean values)들을 저장하는 array data structure이다.
블룸필터(Bloom filter)는 1970년도에 Burton H. Bloom이 고안한 것으로
공간 효율적인 probabilistic data structure이며
구성요소가 집합의 구성원인지 점검하는데 사용된다.
False positive들이 가능하며, false negative들은 불가능하다.
요소들은 집합에 추가될 수 있으나 제거는 되지 않는다.
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
Set(집합)은 중학교
Set(집합)은 중학교 수학시간에 배웠을겁니다.
--------------------------------------------------------------------------------
http://blog.sumin.us
Nearest neighbor search 를
Nearest neighbor search 를 구현하면서 본 자료구조입니다.
VP-tree
Kd-tree
Locality sensitive hash
--------------------------------------------------------------------------------
http://blog.sumin.us
...
세상에는 생각보다 꽤 쿨한 자료구조가 많습니다.
http://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-cool-data-structures
지하철 최단 경로를 찾기 위한 알고리즘은..
예전에도 생각해봤는데..
지하철 최단 경로 찾기 같은건..
자료구조가 해결해 줄수 있나요..
그냥 단순히 경로 횟수로만.. 계산해서요
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
============================================================
선한 인간이냐 악한 인간이냐는 그사람의 의지에 달렸다. -에픽테토스-
의지 노력 기다림은 성공의 주춧돌이다. -파스퇴르-
============================================================
최단 경로 찾는 것은
최단 경로 찾는 것은 시간의 문제라서 어렵죠.
시간이 상관없다면 찾는 건 기본 탐색 알고리즘으로도 찾을 수 있습니다.
또, 경로에 쓰이는 자료구조는 알고리즘에 관계없이 graph죠.
------------------------------
How many legs does a dog have?
------------------------------
How many legs does a dog have?
당연하죠
1-1 최단 경로 찾기 같은 문제는 전통적으로
1) 그래프를 트리로 어떻게 바꾸느냐 (spanning tree) + 2) 트리 안에서 원하는 노드를 어떻게 찾느냐 (tree search)
의 문제입니다. 거의 모든 CS 문제가 그렇지만 문제만 정확히 정의하고 나면 완벽한 자료구조의 문제죠.
최단경로 찾기, 좋은 사례인것 같습니다.
저도 생각해 봤는데, 단순한 문제가 아닌듯 하네요.
먼저, 우리가 일생생활에서 지하철을 이용하는 사례를 정리해 보면,
1. 지하철 출발역으로 들어선다.
2. 지하철 노선도에서 출발역과 목적지역을 확인한다.
3. 이동하는 경우의 수를 따져보고, 최단경로를 찾는다.
4. 가장 최적의 최단경로를 선택, 이동하여 목적지역에 하차한다.
우리는 지능적인 뇌을 활용하여 위의 2번과 3번을 아주 쉽게 처리하지만,
컴퓨터는 논리연산(boolean)을 단순히 반복처리만 하기 때문에,
처리대상을 자료구조화 하여야 합니다.
일단, 위의 2번은 그래프로 자료구조화할 수 있을것 같습니다.
그래프로 지하철 노선의 노드수를 아래의 루프처럼 계산해 보면,
지하철 노선종류(1호선~9호선): n = 9;
지하철역 개수(추정개수): m = 300;
따라서, 지하철 노선의 노드수 = n x m = 2700;
위의 값은 제가 예를들어 본 추론값이며, 숫자보다는 접근방식에 의미가 있습니다.
또한, 갈아타는 지하철역이 있어서, 이동하는 경우의 수를 단순한 루프로
처리한다면, 중첩되는 for 루프의 수는 아래와 같이 증가할 수 있습니다.
for (n) for (n) for (n) ...위에서, n은 반복회수, k을 루프개수(for문 수)라 하면,
알고리즘 효율성,루프회수 = O(n) = n의 k승;
지하철 노선을 그래프로 표현하기에는 좋지만,
그래프는 이동의 방향성이 너무 많기 때문에,
3번의 최단경로를 찾기 위해서는,
이동의 방향을 정하여 효율적으로 탐색할 수 있는 트리구조로 변환합니다.
즉, 그래프(이동하는 경우의 수) --> 최단경로탐색(트리)
트리는 Root와 Left, Right를 탐색하는 순서에 따라서,
PreOrder, InOrder, PostOrder등으로 정해져 있고,
위의 루프 형태로 탐색되기 때문에, 탐색효율 = O(n) = n x log(m);
로 계산될 수 있습니다. 따라서, 최단경로는 이값이 가장작은 것을 찾아보면 될것입니다.
저는 추론에 의한 접근방식에 의미를 두었기 때문에 잘못된 점이 있을 수 있습니다.
단순히, 그래프와 트리의 특성에 대해서만 언급했으므로,
최단경로를 찾기위한 효율적인 자료구조(그래프와 트리응용, 혹은 새로운 개념의 자료구조)
가 있을것이며, 이것을 연구하고 고민하는 것은 의미있는 일이라고 생각합니다.
From:
*알지비 (메신저: rgbi3307(at)nate.com)
*학창시절 마이크로마우스를 만들었고, 10년동안 IT관련 개발자로 일하고 있음.
*틈틈히 커널연구회(http://www.kernel.kr/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
skip list 같은
Skip list 같은 확률적인 자료 구조들이 재밌습니다. (확률적이라고 썼지만 bloom filter 같이 일정 확률 이하로 오답을 내 놓는 게 아니라 complexity guarantee가 난수 생성기에 의존한다는 뜻입니다.) Skip list 같은 건 balanced binary search tree(red-black 등)랑 비교해도 괜찮은 것 같은데 비교적 최근에 나왔기 때문인지 학과 과정에서는 잘 안 보이는 것 같아요.
표기
표기