프로그래밍 공방

Trie : 트라이 빠른 패턴 매칭을 지원하기 위해 문자열들을 저장하는 트리 기반의 자료구조이다. Trie의 특징 1. Trie의 주요 질의 연산은 패턴 매칭과 접두사 매칭(prefix matching)이다. 2. Trie는 루트로부터 리프 노드들까지의 경로로써 문자열을 표현한다. 크기 d의 알파벳으로 s개의 문자열의 집합 S(전체 길이 n)를 저장하는 Trie - Trie의 모든 내부 노드는 최대 d개의 자식을 가진다. - Trie는 s개의 리프 노드들을 가진다. - Trie의 높이는 S에서 가장 긴 문자열의 길이와 같다. - Trie의 노드들의 개수는 O(n)이다. - 크기가 m인 문자열에 대한 탐색 실행시간은 O(dm)이다. Trie의 단점 Trie는 각 노드마다 실제로 다음에 올 문자가 없더라고 ..

세그먼트 트리는 특정 구간에 대해 주어지는 쿼리에 효율적으로 응답하기 위해 만들어진 자료구조이다. (구간의 합, 특정 구간에서 가장 큰 수 / 작은 수 등) 입력 배열을 리프 노드로 하고 내부 노드는 리프 노드를 병합해서 나타낸다. 주어지는 쿼리에 대해서 병합 방식은 다를 수 있다. 세그먼트 트리를 구현하는 방법은 여러 가지가 있지만 이 글에서는 구간 합에 대해서 재귀로 구현하는 방법에 대해서 정리했다. 세그먼트 트리의 구현은 크게 3가지로 나눌 수 있다. 1. 트리 생성 2. 노드 업데이트 3. 쿼리 처리 트리 생성 세그먼트 트리의 크기(배열의 길이)는 입력 배열의 크기 n에 대해서 (int) (Math.ceil(Math.log(n) / Math.log(2))) 이다. (아래 코드의 arr는 입력 배열..

Stack 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조이다. 나중에 넣은 값이 먼저 나오는 LIFO(Last In First Out / FILO) 구조를 가지고 있다. 스택의 연산 push : 스택의 가장 위에 데이터 삽입 top : 스택의 가장 위에 있는 데이터 조회 pop : 스택의 가장 위에 있는 데이터 삭제 Queue 큐는 먼저 넣은 값이 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 자료구조이다. 큐의 연산 Enqueue : 큐의 rear에 데이터를 삽입 Dequeue : 큐의 front에서 데이터를 삭제 Front : 데이터를 꺼내는 위치 Rear : 데이터를 삽입하는 위치

Array 배열은 연속된 메모리 공간에 같은 타입을 갖는 데이터를 저장하는 자료구조이다. 동일한 타입의 여러 데이터를 연속된 공간에 저장하게 되면 각각의 요소의 위치를 시작 위치에 오프셋을 더하는것 만으로 구할 수 있다. 데이터 접근 배열은 특정 순서의 데이터에 접근할 때, 해당 순서의 인덱스를 통해 바로 접근이 가능하다. 데이터 삽입, 삭제 특정 인덱스에 데이터를 삽입하거나 해당 데이터를 삭제할 때, 배열은 아래와 같은 과정이 이루어진다. 데이터 삽입 데이터 삭제 삽입 혹은 삭제하려는 위치의 뒤에 있는 모든 요소들에 대한 작업이 필요하다. Linked List 링크드 리스트는 연속되지 않은 메모리 공간에 데이터를 저장하는 선형 자료구조이다. 링크드 리스트의 데이터는 다음 데이터의 위치 혹은 이전 데이터..