1. 신장 트리 ( Spanning Tree )가중 무방향 그래프에서 모든 정점을 포함하는 트리 ( 사이클 존재X )특징모든 정점이 연결됨간선 수 = 정점 수 - 1|V| = n 이면 간선은 n-1개2. 최소 신장 트리 ( MST, Minimum Spanning Tree )최소 신장 트리란?신장 트리 중에서 가중치의 합이 가장 작은 것간선 (u, v)마다 가중치 w(u, v)를 가진 연결된 무방향 그래프 G = (V, E)에 대해서 다음을 만족하는 트리 G' = (V, E')조건간선 일부만을 선택했을 때, 선택된 간선들의 가중치 합이 최소E' ⊆ E, w(E') = min { ∑(u,v)∈E' w(u,v) }3. 최소 신장 트리를 구하는 알고리즘모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장..
1. 연속 메모리 할당메모리 크기보다 더 큰 기억공간이 필요한 프로세스는 실행 불가2. 가상 메모리메모리 크기보다 더 큰 기억공간이 필요한 프로세스도 실행할 수 있게 하는 방법실행 중인 프로세스에 의해 참조되는 주소( 가상주소 )를 메모리에서 사용하는 주소( 실주소 )와 분리전체 프로세스 중에서 현재 필요한 일부만 메모리에 적재보조기억장치에 전체 프로세스를 두고 일부만 메모리에 적재하는 방법3. 사상( mapping )프로세스 실행을 위해 가상주소를 실주소로 변환하는 과정주소 변환 기법동적 주소변환( DAT )프로세스가 실행되는 동안 사상특징인위적 연속성가상주소 공간에서 연속적인 주소가 실주소 공간에서도 연속적일 필요는 없음4. 주소변환주소변환 사상표동적 주소변환을 위한 정보를 가진 표가상 메모리의 주소..