1. 그래프 탐색 (search) 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색이라고 한다 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 2. 깊이 우선 탐색 (Depth-first search, DFS) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 이다. 따라갈 간선이 없으면 마지막에 따라왔던 간선을 따라 뒤 돌아간다. 위 그림들은 정점의 번호가 작은것을 먼저 탐색하는 dfs의 예시이다. 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 ..

알고리즘 문제해결전략2 그래프파트 1. 그래프 그래프는 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조이다. 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 트리와는 다르게 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있다. 2. 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 3. 그래프의 종류 간선에 추가적인 속성을 부여 존재할 수 있는 간선이나 정점의 형태에 제약 가능 여러 속성을 함께 가지는 그..

1. 트라이 문자열은 두 변수를 비교하는데 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그러므로 이진 검색 트리에서 문자열을 찾는데에 O(mlgn) 의 시간이 걸릴 수 있다. 이와 같은 문제점을 해결하기 위해 고안된 문자열의 특화 자료 구조가 바로 트라이(trie) 이다. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로 검색 수행시 O(M)의 시간이 걸린다. - 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. - 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다. - 트라이의 루트는 항상 길이 0 인 문자열에 대응된다. - 깊이가 깊어질 수록 대응되는 문자열의 길이는 1 씩 증가한다. 트라이에서 중요한..

1. 상호 배타적 집합 상호 배타적 집합을 표현할 때 유니온-파인드(union-find) 자료구조를 쓴다. 이 자료구조는 독특한 트리이다. 전체 집합을 공통 원소가 없는 여러 개의 부분 집합으로 쪼개어 나누어진 원소들(상호배타적인 부분 집합들) 에 대한 정보를 저장하고, 조작하는 자료구조가 유니온-파인드 자료구조이다. 이 자료구조의 핵심 연산은 다음과 같다. - 초기화: n 개의 원소가 있을 때 자기자신으로만 이루어진 집합들. - 합치기(union): 두 원소 a, b가 있을때 이들이 속한 두 집합을 하나로 합침 - 찾기(find): 어떤 원소 a가 주어질때 이 원소가 속한 집합을 찾는다. 2. 배열을 사용하여 상호 배타적 집합 표현하기 1차원 배열 하나를 이용하여 표현한다 belongsTo[i] = i..

(일반적인 구간트리와는 다른 자료구조, 책에서는 알고리즘 문제를 풀기위한 자료구조를 설명한다.) (일반적인 구간트리는 1차원 좌표상의 구간들을 지정하고 특정 위치를 포함하는 구간들을 찾는 자료구조임.) 1. 구간 트리(segment Tree) 구간 트리는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록한다. (일차원 배열의 특정 구간) ex) 구간의 최소치를 여러번 구하는 문제. 어떤 배열 A의 부분 구간의 최소치를 찾는데 보통 부분 구간을 순회하며 최소치를 찾는다, 이것은 O(N)의 시간이 걸린다. 반면 한번의 전처리를 통해 구간트리를 생성하면, 연산을 더 빠르게 할 수 있다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 구..

1. 우선순위 큐와 이진 힙 트리와 밀접하게 연관된 다른 자료 구조로 우선순위 큐가 있다. 이것은 순서대로 기다리고 있는 자료들을 저장하는 자료구조이다. 일반 큐와는 다른 점은 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다는 것이다. 만약 이것을 균형잡힌 트리를 사용하여 우선순위 큐를 구현하게되면 삽입 삭제 전부 lgn 시간에 수행할 수 있다. 또 이것은 힙(heap)으로도 구현할 수 있으며 이는 훨씬 단순한 구조이다. 힙은 가장 큰 원소, 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리로,(최대힙 max heap 최소힙 min heap) 삽입연산과 가장 큰 원소를 삭제하는 연산 모두 O(lgn)시간에 수행가능하다. 우선순위와 자료의 쌍을 ..