CS/알고리즘 (3) 썸네일형 리스트형 [MST] N개의 핀을 두개씩 연결하기 위해서는 N-1개의 선이 필요하다. 여기서 방향이 없는 그래프 G = (V, E)가 사용되며 V는 핀의 집합, E는 핀 쌍의 가능한 연결 집합이다. 그리고 각 edge(u,v)는 E에 포함된다. 가중치(w)s는 u와v를 연결하는 데 드는 비용을 나타낸다. MST의 목표는 모든 노드를 연결할 때(비순환) 총 비용이 가장 적은 순환을 찾는 것이다.그래프 T는 비순환적이고 모든 정점을 연결하므로, 이는 하나의 트리를 형성하게 된다. 이는 그래프 G를 "포괄(spans)"하기 때문에 스패닝 트리(spanning tree)라고 부른다. T를 결정하는 문제를 우리는 최소신장 트리 문제로 부르기로 하였다.다음 그림은 연결된 그래프와 최소신장 트리 문제의 예시를 보여준다.이 챕터에서 우리는.. [Symbol Table - BST] 부모 키는 왼쪽 트리 키보다 크고 오른쪽 트리 키보다 작은 값을 만족한다는 이진트리이다. 탐색삽입키가 이미 있을 경우: 값 업데이트없을 경우: 새 노드 생성Worst Case삽입 순서에 따라 트리는 N개의 레벨을 가질수도 있다. Random순서를 랜덤하게 한다면 삽입과 검색은 평균 2 ln N 값을 가진다.평균 트리 높이는 4.311 ln N이다.하지만 Worst Case에서는 N의 높이를 가진다.Ordered Operations BSTMinimum가장 작은 키Maximum가장 큰 키Floor주어진 키보다 작거나 같은 키 중 가장 큰 키Ceiling주어진 키보다 크거나 같은 키 중 가장 작은 키Floor 방법찾으려는 키가 k일때 루트에 k가 있을 경우 k의 floor는 kk가 루트 키보다 작을 때 k의.. [Symbol Table] 컴퓨터 과학에서 심볼 테이블(symbol table)은 컴파일러나 인터프리터에서 사용되는 데이터 구조로, 프로그램 소스 코드에 사용된 각 식별자(또는 심볼, 언어 번역기에서 사용하는 심볼)에 그 선언이나 소스에서의 등장과 관련된 정보를 연결하여 저장한다.-위키피디아- 심볼 테이블의 아이디어는 각 키마다 하나의 값을 연관짓는 것이다.따라서 키-밸류 쌍의 추상화이다. 심볼 테이블의 ADT는 다음과 같다. value는 null 값이 될 수 없으며 주어진 키를 통해 해당 키에 대응하는 값을 검색할 수 있다. 중복 키 문제 해결하기사용자 정의 타입(user-defined types)을 비교하거나 해시 코드를 계산할 때의 표준 방법은 다음과 같다. 1. 참조 동등성에 대한 최적화2. null 체크3. 두 객체가 동.. 이전 1 다음
