1. 검색 트리 검색 트리는 링크드 리스트나 큐처럼 자료들을 담는 컨테이너지만, 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둔다. 이것은 입력이 주어진 순서에 따라 자료들을 배치하는 리스트나 큐와 다른 속성이다. 이런 속성은 원소의 추가 와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있다. 이진 검색트리는 특히 아주 널리 사용되기 때문에, 이들의 동작 원리와 장단점은 알아야한다. 대부분 이진 검색트리는 라이브러리에서 제공한다. 2. 이진 검색 트리 이진 트리(binary tree) 란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다. 따라서, 이진 트리는 자식 노드들의 배열 대신 두 개의 포인터 left 와 right를 담는 ..

1. 트리 트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 계층 관계표현 이외도 다른 구조보다 같은 연산을 더 빠르게 할 수 있다. (특히 탐색형 자료 구조) 탐색형 트리 자료구조의 유명한 이진 검색 트리는 모든 숫자에 최대 두개의 하위 숫자만 있으며 어떤 숫자에서든 왼쪽 가지를 따라 내려가면 더 작은 수를 오른쪽 가지를 따라 내려가면 더 큰 수를 만날 수 있다. 이와 같은 특별한 규칙에 의해 탐색을 lgn만에 할 수 있게 된다. 트리의 구성 요소 노드 node: 연결된 노드 간에는 상하위 관계가 있다. 간선 edge: 연결하는 선 상위 노드 parent 하위 노드 child 부모가 같은 노드 sibling 부모 노드와 그의 부모 노드들 ancestor 자식 노드와 그의 자식 노..

1. 문자열 현대의 컴퓨터의 많은 양의 데이터들은 거의 문자열이다. 때문에 문자열을 다루는 문제와 자료 구조는 전산학의 중요한 연구 주제이다. 문자열 검색 문제를 위한 kmp알고리즘과 문자열 처리의 스위스 칼이라고 할 수 있는 자료 구조 접미사 배열(suffix array)에 대해 알아보자. - 문자열 = S - 문자열의 길이 = |S| - 문자열 S의 i 번 = S[i] - 부분 문자열(substring) = S[i,..j] - 접두사(prefix) = 0번부터 특정 문자까지의 문자열 S[0..a] - 접미사(suffix) = 특정 문자에서 부터 끝까지의 문자열 S[b...] 2. 단순한 문자열의 검색 문자열이 A, B가 있을 때 문자열 A가 문자열 B의 부분 문자열로 포함하는지 확인하고 부분 문자열의..

1. 자료 구조 현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 큐와 스택, 데크가 있다. 이들은 일렬로 늘어선 자료들을 표현하는 자료 구조이다. 이 때 자료는 특정한 순서로 넣고 특정한 순서로만 꺼낼 수 있다. 그러므로 이 세 자료 구조들을 구분하는 것 또한 어느 순서로 자료를 넣고 뺄 수 있는가 이다. 이들은 다른 알고리즘을 구현하는 도구로 유용하게 사용된다. 배열과 링크드 리스트로 쉽게 구현할 수 있다. 자료 구조에 자료를 넣는 작업을 푸시(push) 자료 구조에 자료를 꺼내는 작업을 팝(pop) 이들 연산은 모두 O(1)이다. 2. 큐(queue) = FIFO 큐에서는 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다. 선입선출 속성을 가지고 있다. 3. 스택(stac..

1. 선형 자료 구조 일렬로 늘어선 같은 자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다. 배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조인 동적 배열과 연결 리스트를 선형 자료 구조라고 한다. 2. 동적 배열(dynamic array) 배열의 큰 문제 중 하나는 배열의 크기를 지정해야하며, 그 이상의 자료를 집어 넣을 수 없다는 것이다. 이와 같은 문제를 해결하기 위해 만들어진 자료구조가 동적 배열이다. 동적 배열은 자료의 개수가 변함에 따라 크기가 변경된다. 동적 배열은 일반 배열처럼 언어 차원에서 지원되는 기능이 아니라 배열을 이용해 만들어 낸 별도의 자료 구조이고, 언어의 표준 라이브러리에 대개 포함되어있다. 3. 동적 배열의 특성 - 원소들은 메모리의 연속된 위치에 저..

1. 부분 합 부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 합을 구해둔 배열이다. psum[i] = Σscores[j] (0