최단경로 알고리즘정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로간선의 가중치는 비용, 거리, 시간 등최단 경로를 위한 그래프 표현: 간선이 없으면 가중치를 무한대로 처리Dijkstra의 최단 경로 알고리즘시작 정점 v에서 모든 다른 정점까지의 최단 경로 찾음시작 정점 v: 최단 경로 탐색의 시작 정점집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합dist 배열: S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열매 단계에서 최소 distance인 정점을 S에 추가S에 속하지 않은 정점들 중에서 dist가 가장 작은 정점을 S에 추가추가 후 남은 정점들의 dist를 갱신, 이 과정 반복dist[w] = min(dist[w], dis..
BURROW
가중치 그래프Weighted Graph간선에 가중치가 할당된 그래프G =(V, E, w)w: 비용, 가중치, 길이경로 p의 길이: 경로상의 모든 간선의 합인접 행렬을 이용한 표현 ABCDEFGA029 10 B29016 15C 16012 F 12022 18E 2202725F10 270 G 15 1825 02차원 배열 → 파이썬: 리스트의 리스트vertex = ['A', 'B', ... , 'G']weight = [[None, 29, ... , None], [29, None, ... , 15], ... [None, 15, ... , None]]graph = (vertex, weight) # 전체 그래프: 튜플 사용인접 행렬에서의 가중치의 합 계산def ..
부울연산부울대수(Boolean Algebra) / 논리대수(Logic Algebra): 0 또는 1을 입력 받아 0 또는 1을 출력하는 회로의 논리 계산을 형식화한 것부울값(Boolean Value): 디지털 신호, 0 또는 1부울변수(Boolean Variable): 부울값 0 또는 1을 받는 변수부울함수(Boolean Function): n개의 부울변수와 부울 연산자로 구성되는 식부울보수(Boolean Complement): 부울변수의 값을 반전시키는 단항연산자부울합(Boolean Addition): 부울변수의 값을 더하는 이항 연산자로 부울변수의 값 중 하나만이라도 1이면 그 결과가 1부울곱(Boolean Multiplication): 부울변수의 값을 곱하는 이항 연산자로 부울변수의 값 중 하나만이..
운영체제의 역할응용 프로그램이 요청하는 메모리를 허가하고, 분배응용 프로그램이 요청하는 CPU 시간을 제공응용 프로그램이 요청하는 IO Devices 사용을 허가/제어유닉스 시스템의 호출 인터페이스운영체제 각 기능을 사용할 수 있도록 시스템 콜이라는 명령(함수)을 제공API 내부에는 시스템 콜을 호출하는 형태로 만들어짐프로세스 호출하나의 프로세스가 다른 프로세스의 메모리, 데이터, 함수 호출은 기본적으로 불가능운영체제는 IPC(Inter Process Communication)를 제공함프로세스가 운영체제의 함수를 호출하는 목적시스템 자원 접근운영체제의 함수를 시스템 콜을 불러 서비스주로 시스템 호출을 직접 사용이 아닌 상위 수준의 응용 프로그램 인터페이스(API)를 통해 프로그램에서 액세스WIN32 AP..
유닉스 프로세스의 종류사용자 프로세스: 단말기와 사용자와 관련된 프로세스커널 프로세스: 커널 모드에서 실행, 프로세스 0데몬 프로세스: 다른 사용자와 전혀 관련 없지만, 전역 함수와 같이 네트워크 제어/관리 등 시스템 지원하는 프로세스유닉스 프로세스의 구조프로세스 테이블정보를 프로세스마다 유지하고, 항상 메인 메모리에 상주함프로세스 상태 필드(준비 상태, 실행 상태, 수면 상태 등), 사용자 영역 포인터, 프로세스 식별자(ID 또는 PID), 사용자 식별자(ID 또는 UID), 프로세스 크기, 이벤트 디스크립터, 스케줄링 매개변수 항목 등공유 코드가 있는 프로세스에서 텍스트 테이블을 유지하여 공유 코드의 메인 메모리 주소(디스크 주소)와 이 코드를 사용하는 프로세스 수 추적 카운터 등 정보 포함각 프로세..
탄생과 발전 과정1969년 미국의 통신회사인 AT&T 산하의 벨 연구소에서 켄 톰슨과 데니스 리치가 개발처음에는 어셈블리어로 개발했다가 C 언어로 다시 만들어 고급 언어로 작성한 최초의 운영체제가 됨데니스 리치가 연구했던 멀틱스는 당시 복잡하고 거대한 구조 때문에 실패했으나 새로운 유닉스를 만드는 데 지대한 영향을 미침유닉스라는 이름도 multics에 기반유닉스 개발 얼마 후 소스 코드 공개된 후, 대학교나 기업에서는 이를 이용한 연구를 진행하여 다양한 기능 추가이후 각각 AT&T의 상업용 유닉스(시스템 V)와 버클리대학교의 BSD(Berkeley Software Distribution)로 분리되어 발전BSD버클리대학교의 프로그래머들이 상당 부분 수정특히 네트워크 기능 추가한 점은 가장 주목할 만함BSD..
