programmer life guidance 101

> 트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 래딕스 트리(radix tree) 나 접두사 트리(prefix tree)라고도 한다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것이다. 우리는 문자열 검색을 개선하기 위해 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있다. 트라이라는 명칭은 Retrieval에서 유래한다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득ㅇ ㅣ디ㅗㄴ다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리할까? 아래 그림은 문자열 집합 ..

> 스택(STACK)이란? 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저..