유진's 공부로그

트라이 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다. 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 ..

1. (정적)배열 : 연속된, 정해진 크기의 메모리 공간을 할당. 같은 타입의 원소만을 담을 수 있음. (정해진 크기의 메모리 공간을 할당하고, 이를 원소 타입, 원소 개수에 맞춰서 분할하기 때문) 또한 한 번 생성한 배열은 크기 변경이 불가능하다. 배열의 장점은 어느 위치에나 O(1)에 조회가 가능하다는 점이다. (배열 시작 주소 + 원소 타입에 따른 바이트 크기 * 원소 인덱스)로 해당 배열 원소 값의 주소 계산 및 메모리 접근이 가능하기 때문. (배열 원소 개수에 독립적) 그러나, 원소의 삭제나 삽입 등의 작업은 최악의 경우 O(n)의 시간복잡도를 갖는다. 예를 들어 원소의 가장 첫번째 원소를 삭제한다고 가정하면 나머지 모든 원소를 하나씩 override해야 하기 때문에 (당겨와야 하기 때문에) n..

그래프 : 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 정의 그래프 G는 (V,E)로 표시하며, 이때 V는 정점 vertex의 집합을 E는 간선 edge의 집합을 의미함. - vertex (정점) : 여러 가지 특성을 가질 수 있는 객체를 의미함. 노드(node)라고도 함. - edge (간선) : 정점들 간의 관계를 의미. link라고도 함. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B..