생성트리Spanning Tree, 신장트리그래프의 모든 노드를 포함하는 트리최소생성트리: 가중 그래프에 대하여 연결선의 가중치의 합을 최소로 하는 생성트리네트워크나 도로망 설계 시 비용을 최소로 하거나 효율성을 최대로 하는 경로를 고려할 때 유용최소생성트리를 구하는 알고리즘: 프림 알고리즘, 크루스칼 알고리즘프림 알고리즘Prim Algorithm주어진 가중치 그래프 G에서 최소신장트리를 프림 알고리즘으로 구하는 규칙그래프에서 임의의 노드 하나를 선택선택된(연결된) 노드들과 연결된 모든 변들 중 가중치가 가장 작은 변을 선택가중치가 같은 변은 임의로 하나를 선택순환이 형성되는 경우는 그 변은 선택하지 않음그래프 G에 포함된 모든 꼭짓점의 수가 n개일 때, n-1개의 변이 연결될 때까지 2~4의 과정을 반복..
Study
컴퓨터 버스버스: CPU와 주기억장치, 외부의 입출력장치 간에 정보를 전송하기 위해 공용으로 사용하는 전기적 통로데이터 버스실질적인 정보 데이터를 전달하는 버스양방향성 버스데이터 버스폭(선들의 수) = CPU와 기억장치 사이 한 번에 전송되는 비트 수주소 버스각 장치의 주소나 기억장치 위치를 나타내는 정보들이 지나가는 버스단방향성 버스 (CPU → 기억장치 및 I/O 제어기)주소 버스의 비트수에 의해 접근 가능한 전체 기억장치 용량이 결정됨제어 버스수행될 다양한 데이터 전송 동작을 구별하기 위한 신호들이 지나가는 버스양방향성 버스버스의 형태연결되는 장치에 따라서 3가지 형태가 존재함내부 버스컴퓨터 시스템 내의 칩들 사이에 신호를 전달하는 전형적인 내부 버스외부 버스주변장치들 사이에서 신호를 전달하기 위한..
네트워크서로 독립된 시스템 몇 개가 적절한 영역 안에서 빠른 통신 채널을 이용하여 상호 통신할 수 있도록 지원하는 데이터 통신 시스템컴퓨터 네트워크는 1960년대 사이트 간 효율적 통신 위해 학교 연구 프로젝트로 탄생광범위한 사용자 모임 간에 하드웨어나 소프트웨어를 편리하게, 경제적 공유 지원알파넷(ARPANET): 최초로 개발된 네트워크, 1968년 처음 작동사용자가 원거리의 하드웨어나 소프트웨어 자원에 액세스 할 수 있는 기능 제공네트워크 시스템 구성하는 방법: 강결합/약결합 시스템네트워크의 구조트리 구조 네트워크회사의 컴퓨터 네트워크에 사용하는 방법네트워크의 각 노드가 트리로 구성루트 A를 제외한 각 노드는 단일 부모와 자식 몇 개를 가짐기본 비용은 일반적으로 망 구조보다는 낮음부모 고장이 나면 그..
트리루트라는 특별한 노드를 갖고 그래프를 구성하는 꼭짓점 u, v 간에 u에서 v로 가는 단순경로가 존재하는 비순환의 연결 그래프나무의 가지가 뿌리에서 뻗어나가듯이 트리는 루트를 중심으로 하나 이상의 꼭짓점(노드)들이 비선형이면서 비순환적인 경로로 연결되어 있는 형태노드: 트리인 그래프를 구성하는 꼭짓점루트: 트리인 그래프의 가장 높은 곳에 위치하는 시작 노드서브 트리: 트리인 그래프의 임의의 한 노드를 루트로 하는 트리차수: 트리인 그래프의 임의의 한 노드에 포함된 자식 노드의 개수레벨: 트리인 그래프의 루트 노드를 레벨 0으로 시작하여 자식 노드로 한 단계씩 내려갈 때마다 하나씩 증가하는 단계높이/깊이: 트리인 그래프의 최대 레벨포레스트: 트리인 그래프의 루트 노드와 가지를 제거하여 얻는 서브 트리들..
입출력장치입력: CPU가 외부에서 정보를 받아들이는 과정출력: CPU가 외부로 정보를 내보내는 과정입출력 처리: CPU가 입출력장치와 정보를 주고받는 과정입력장치문자, 기호, 소리, 동영상 정보를 컴퓨터가 이해할 수 있는 2진 코드로 변환시켜, 주기억장치에 저장하거나 CPU에 전달하는 역할을 하는 것키보드, 지시장치, 원시 데이터 입력장치키보드문자, 숫자, 특수문자 키들을 통해서 입력을 발생시키고 방향키와 기능키를 통해서 수정과 편집을 쉽게 할 수 있는 가장 널리 이용되는 입력장치기계식 키보드(스프링 방식), 멤브레인 키보드(비스프링 방식) 등1975년부터 PC에 사용되기 시작101 키보드가 가장 기본지시장치마우스: 커서의 이동이나 영역을 지정할 수 있고 아이콘을 선택하고 메뉴를 실행할 수 있는 입력장치..
그래프의 활용최단경로 문제|E|>0인 그래프 G=(V, E)에서 꼭짓점 v₁, v₂ ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제출발점(source): 경로의 시작점도착점(destination): 경로의 목적지가중치 방향 그래프가중치가 부여되지 않은 그래프: 경로의 길이(경로에 포함되는 모서리의 수)로 최단경로가중치가 부여된 경우: 가중치를 계산하여 가중치에 의해 최단거리가 결정가중치가 비용이라면 가중치의 합이 가장 작은 경로가 최단거리이고, 효과라면 가중치의 합이 큰 경로가 최단거리다익스트라 알고리즘그래프 G=(V, E)가 있을 때, V={v₁, v₂, ... , vₙ}이고 시작점이 v₁라고 가정했을 때 다익스트라 알고리즘에 사용되는 기호와 가정C[vᵢ, vⱼ]: 꼭짓점 vᵢ에서 vⱼ로 가는 가중치를..
