bdfgdfg

시스템 프로그래밍이란? ● 시스템(컴퓨터 시스템)의 범위 - 하드웨어 + 운영체제 ● 시스템 프로그래밍 - 컴퓨터 시스템을 활용하는 소프트웨어 - Windows 운영체제 자체의 기능을 활용하는 프로그래밍 ● 응용 소프트웨어 개발과의 차이점 - 시스템 프로그래밍은 모든 응용 프로그램에 포함되는 요소 컴퓨터 시스템의 주요 구성요소 ● CPU, 캐시 - 컴퓨터 하드웨어 구조 ● 운영체제 - 메인 메모리 -> 메모리 관리 기법 - 하드디스크 -> 파일 I/O(다양한 I/O포함) 컴퓨터 하드웨어 구성 간단히 위의 구성을 설명해봄녀. ● CPU(Central Processing Unit, 중앙처리장치) - 컴퓨터 프로그램의 연산이 이루어지는 곳. ● 메인 메모리(Main Memory) - 램(RAM) - 메인 메모..

크루스칼과 같은 최소 스패닝 트리를 구하는 알고리즘. 크루스칼 알고리즘은 탐욕(greedy)적인 방법으로 작은 가중치의 간선만을 선택해서 사이클이 발생하지 않는다는 가정하에 간선을 붙여줬다. 프림 알고리즘의 특징은 하나의 시작점(어느 정점이든 상관x)으로 구성된 트리에 간선을 하나씩 수집하며 진행한다. 네모가 쳐진 정점을 기준으로 15와 35라는 간선을 선택할 수 있는데. 당연히 15가 더 적은 가중치를 가진 간선이니 15를 선택한다. 이제 그 다음 정점을 확인해보면 5,10이라는 가중치를 가진 간선들. 더 작은 5 간선을 선택하고. 10이라는 간선을 확인했을때. 시작정점을 기준으로 15 + 10 = 25이니. 35보다 작다는것을 알 수 있음. 그러므로 35는 선택이 불필요. 이런식으로 나머지 간선도 선..

Union-find : 합치기-찾기. 이 알고리즘은 예로들어 어떤 배열에서. 어떤 인덱스에 접근해보았더니 그 원소가 가진 값이 이 인덱스의 부모. 즉 나와 연결고리를 찾는 과정. -> 최고 부모가 누구인지(Find). 혹은 내가 원한다면 다른 원소와의 연결고리를 합치는(Union) 알고리즘. 이 구조를 단순히 배열만을 이용한다면 찾는과정은 바로 찾을 수 있겠지만, 합치기 과정에서 모든 배열을 순회하면서. 합쳐야할 원소를 찾아야 한다. 그렇기에 트리 구조를 통한 Union-Find의 표현을 본다. 트리 구조를 통한 Union-Find의 첫번째 특징은. 먼저 Union-Find를 하기전에 모든 노드가 자기자신을 가리킨다. 즉. 처음에는 자기자신이 연결된 노드간의 꼭대기. 루트노드라고 보는것. class Un..

최소 비용 신장 트리 트리는 그래프의 한 유형. 다음 그래프를 보고 정점 B에서 정점 D에 이르는 모든 경로를 찾아서 열거해본다. 이렇게 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라 한다. 그리고 위의 네 경로와 같이 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로'라 한다. 단순 경로가 아닌 예를 들어보면 B-A-C-B-A-D -> B와 A를 잇는 간선이 두 번 포함됨. 그렇다면 A-B-C-A는 단순 경로가 일까? 단순 경로가 맞다. A정점이 두 번 등장하지만 중복된 간선이 포함되지 않기 때문이다. 이렇게 단순 경로이면서 시작과 끝이 같은 경로를 가리켜 '사이클'이라 한다. 간단히 말해 사이클은 어느 정점에서 다른 경로를 통해 다시 돌아올 수 있다면 사이클이라 한..