최단 경로 • 조건 – 간선 가중치가 있는 유향 그래프 – 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다 • 즉, 무향 간선 (u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정하면 된다 • 두 정점 사이의 최단경로 – 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로 – 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다 • 단일 시작점 최단경로 – 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다 다익스트라 알고리즘 : 음의 가중치를 허용하지 않는 최단경로 벨만-포드 알고리즘 : 음의 가중치를 허용하는 최단경로 싸이클이 없는 그래프의 최단경로 • 모든 쌍 최단경로 – 모든 정점 쌍 사이의 최단경로를 모두 구한다 플로이..

상호 배타적 집합의 처리 ※ 교집합은 다루지 않는다. • 지원할 연산 – Make-Set(x): 원소 x로만 이루어진 집합을 만든다 – Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다 – Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합 연결 리스트를 이용하는 방법과 트리를 이용하는 방법 연결리스트를 이용한 집합 처리 • 같은 집합의 원소들은 하나의 연결 리스트로 관리한다 • 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다 Weight를 고려한 Union • 연결 리스트로 된 두 집합을 합칠 때 작은 집합을 큰 집합의 뒤에 붙인다 – 대표 원소를 가리키는 포인터 갱신 작업을 최소화하기 위한 것 [예시] 다음의 상호배타적 집합이 연결리스트로 완성되기까지의 ..

해시 테이블 해시 테이블 원소가 저장될 자리가 원소의 값에 의해 단 한번의 계산으로 결정되는 자료구조 (검색 트리와 상반) 평균 상수 시간에 삽입, 삭제, 검색 매우 빠른 응답을 요하는 응용에 유용 - 예 : 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록 시스템 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다 해시함수 • 입력 원소가 해시 테이블에 고루 저장되어야 한다 • 계산이 간단해야 한다 • 여러 가지 방법이 있으나 가장 대표적인 것은 나누기 방법과 곱하기 방법이다 나누기 방법 Division Method – h(x) = x mod m – m: 해시 테이블 사이즈. 대개 소수임. 곱하기 방법 Multiplication Method – h(x) = (xA mod 1) *..

검색 알고리즘 기타 개념 > 레코드record – 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 – e.g., 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연소득, 가족 상황 등의 정보 포함 > 필드field – 레코드에서 각각의 정보를 나타내는 부분 – e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분 > 검색키search key 또는 키key – 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 – 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다 > 검색트리search tree – 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 – 이를 통해 해당 레코드가 저장된 위치를 알 수..