그래프의 활용최단경로 문제|E|>0인 그래프 G=(V, E)에서 꼭짓점 v₁, v₂ ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제출발점(source): 경로의 시작점도착점(destination): 경로의 목적지가중치 방향 그래프가중치가 부여되지 않은 그래프: 경로의 길이(경로에 포함되는 모서리의 수)로 최단경로가중치가 부여된 경우: 가중치를 계산하여 가중치에 의해 최단거리가 결정가중치가 비용이라면 가중치의 합이 가장 작은 경로가 최단거리이고, 효과라면 가중치의 합이 큰 경로가 최단거리다익스트라 알고리즘그래프 G=(V, E)가 있을 때, V={v₁, v₂, ... , vₙ}이고 시작점이 v₁라고 가정했을 때 다익스트라 알고리즘에 사용되는 기호와 가정C[vᵢ, vⱼ]: 꼭짓점 vᵢ에서 vⱼ로 가는 가중치를..
BURROW
파일 시스템사용자가 직접 파일을 보관하는 대신 파일 관리자를 두어 저장 장치의 관리를 맡기는 시스템파일 관리자가 파일 테이블을 사용하여 파일 관리사용자가 특정 파일에 접근하려면 파일 관리자로부터 파일에 접근할 수 있는 권한(키)을 획득해야 함파일 시스템의 사용 목적컴퓨터 시스템의 편리한 사용정보를 저장하고 관리하는 시스템논리적이고 일관성 있는 정보 저장 체계저장 장치의 물리적 특성을 고려하여 논리적으로 저장해야 함파일 시스템의 요구사항대량의 정보를 파일로 저장 가능파일로 저장된 정보가 사용 중에는 파괴 불가하나 이상의 프로세스가 공동 사용 가능파일 시스템의 성능 평가구분특징소멸성파일의 추가나 삭제의 빈도수 (정해진 시간 안에)활성율주어진 시간에 접근할 수 있어야 함크기저장된 정보량파일 시스템의 기능파일 ..
보조기억장치주기억장치의 저장 용량 부족을 보완하며, 비휘발성 특징을 이용해 데이터를 반영구적으로 저장하는 기억장치하드 디스크, 플로피 디스크, CD, DVD, 플래시 기억장치 등기억장치의 계층적 구조에서 가장 하위 단계에 위치동작 속도는 저속이고 가격이 저렴하지만 많은 양의 데이터 저장 가능2가지 연결 방식IDE: 병렬 케이블을 이용하여 1개 채널에 2개씩 장치 연결 가능(Master, Slave)SATA: 비교적 빠른 직렬연결을 이용하여 연결(3~6 Gbit/s)CPU, ROM, RAM, 보조기억장치의 관계컴퓨터 전원을 켜면 CPU는 자동적으로 ROM에 저장된 프로그램들을 실행시켜서 부팅을 수행완전하게 부팅이 되면, 사용자는 보조기억장치에 저장된 응용 프로그램을 실행시켜서 주기억장치의 RAM에 프로그램..
탐색탐색: 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업맵, 딕셔너리: 탐색을 위한 자료구조, 엔트리 또는 키를 가진 레코드의 집합엔트리키: 영어 단어와 같은 레코드를 구분할 수 있는 탐색키값: 단어의 의미와 같이 탐색키와 관련된 값맵 ADT데이터: 키를 가진 레코드(엔트리)의 집합연산search(key): 탐색기 key를 가진 레코드를 찾아 반환insert(entry): 주어진 entry를 맵에 삽입delete(key): 탐색기 key를 가진 레코드를 찾아 삭제맵을 구현하는 방법리스트 이용: 정렬 / 비정렬 (가장 간단한 구현 방법)이진 탐색 트리 이용: 탐색 성능을 향상 시키고자 하는 경우해싱 구조 이용: 맵을 구현하기 가장 좋은 방법순차 탐색Sequential Search정렬되지 않은 배열에 ..
그래프공집합이 아닌 꼭짓점(node)의 집합 V와 서로 다른 꼭짓점의 쌍(vᵢ, vⱼ)을 연결하는 모서리(edge)의 집합 E로 구성된 구조G = (V, E)V = {v₁, v₂, ... , vₙ}E = {e₁, e₂, ... , eₙ} = {(vᵢ, vⱼ), ... }G = (V, E) : 그래프 G는 꼭짓점 집합 V와 모서리 집합 E로 구성그래프 G = (V, E)에서 꼭짓점 u와 v를 연결한 모서리 e가 있을 때, 꼭짓점 u와 v는 서로 인접(adjacent)하고, 모서리 e는 꼭짓점 u와 v에 근접(incident)함루프: 인접하는 꼭짓점이 하나인 모서리 e다중 그래프: 그래프 G = (V, E)에서 두 꼭짓점 사이에 두 개 이상의 모서리가 있는 그래프방향 그래프: 화살표로 모서리를 표현해 인접하..
디스크디스크 드라이버: 구동 모터, 액세스 암 이동장치, 입출력 헤드 부분의 기계적인 부분을 담당프로세서: 컴퓨터의 논리적인 상호작용, 즉 데이터의 위치(디스크 주소)와 버퍼, 판독, 기록 등을 관리디스크 제어기: 디스크 드라이버의 인터페이스 역할프로세서에서 명령을 받아 디스크 드라이버 동작디스크 드라이버는 탐색, 기록, 판독 등 명령 수행디스크의 정보: 드라이버 번호, 표면 번호, 트랙 번호(디스크 주소)로 참조트랙원형 평판 표면에 데이터를 저장할 수 있는 동심원자기장의 간섭/ 헤드를 정렬을 위해 공간을 두어 트랙 구분실린더동일한 동심원으로 구성된 모든 트랙동일한 위치에 있는 모든 트랙의 집합을 의미섹터트랙을 부채꼴 모양으로 나눈 조각을 의미트랙 내의 정보는 블록을 구성블록이 하드웨어적으로 크기가 고정..
