분류 전체보기

알고리즘 - 집합 커버 문제(Set Cover)

집합 F에서 선택하는 집합들의 수를 최소화하는 문제 신도시를 계획하는데 있어서 학교 배치의 예) 10개의 마을이 신도시에 만들어질 계획이다. 조건이 만족되어야 한다. 조건 1. 학교는 마을에 위치해야 한다. 조건 2. 등교 거리는 걸어서 15분 이내이어야 한다. 2번 마을에 학교를 만들면 1, 2, 3, 4 ,5 마을이 커버된다. 6번 마을에 학교를 만들면 5, 6, 7, 9, 19 마을이 커버된다. 최소 학교의 수 = 2개 전체 마을의 수 U = {1, 2,3 ,4, 5, 6, 7, 8, 9 ,19} 한 마을에 배치했을때 커버되는 마을의 집합 S1 = {1, 2, 3, 8} S2 = {1, 2, 3, 4, 8} S3 = {1, 2, 3, 4} S4 = {2, 3, 4, 5, 7, 8} S5 = {4, ..

알고리즘 - 부분 배낭 문제(Fractional Knapsack)

문제 n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제. 물건의 전체를 넣지 못한다면 물건을 부분적으로 담는 것을 허용된다. 해결 방법 단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣는다. 만일 물건을 통째로 배낭에 넣을 수 없으면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다. 수행 과정 배낭의 최대 용량 = 40 단위 무게당 가치로 정렬 물건 가치 무게 단위 그램당 가치 백금 60만원 10g 6만원 금 75만원 15g 5만원 은 10만원 25g 4천원 주석 1만원 10g 1천원 백금을 통째로 담는다. 배낭의 무게 = 10/40 가치 = 60만원 금을 통째로 담는다. 배낭의 ..

알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path)탐색 알고리즘이다. 흔히 최소비용으로 선로 또는 파이크 네트워크, 인공위성 GPS 소프트웨어에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이 떄 음의 간선을 포함할 수 없는데 현실 세계엔 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 좋은 알고리즘이라고 한다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져 있기 떄문이다. 하나의 최단거리를 구할 때 직전까지 구했던 최단거리를 이용한다. 1. 출발 노드를 정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3...

알고리즘 - 프림 알고리즘(Prim Algorithm)

최소 비용 신장 트리를 구하는 알고리즘이다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 생성하여 최소 비용 신장 트리를 구한다. 프림 알고리즘은 임의의 정점을 선택하며 가중치가 적은 노드를 선택해서 연결해주고 가중치를 업데이트 하는 과정을 반복해준다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 구하는 반면 프림 알고리즘은 정점을 기준으로 최소 비용 신장 트리를 구한다. 노드 0을 선택한다. 노드 0을 선택하고 연결된 모든 노드의 거리를 살펴본다. 직접 이어지지 않은 노드의 거리는 inf(무한대)가 된다. 따라서 0과 연결된 1, 2, 3에 각각 4, 6, 5가 할당된다. 그 후 거리가 가장 짧은 노드를 선택한다. 1번 노드의 거리가 4므로 거리가 가장 짧으니 1번 노드가 선택된다. 그 후 1번 노드와..

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘이다. 최소 신장 트리를 만들기 위한 알고리즘이다. 1. 모든 간선들을 오름차순으로 정렬한다. 2. 가중치가 가장 적은 간선을 추가한다. 3. 추가된 간선이 사이클을 만들면 삭제한다. 2~3번의 동작을 반복한다. 시간복잡도: O(m log m)

운영체제(OS) - 페이지 교체(Page Replacement)

프로세스를 사용하기 위해선 메모리에 올려야 한다. 그럼 언제 메모리에 가져다 놓는가? - Demand fetch(필요로 할 때 가져온다) - Anticipatory fetch(예상해서 가져온다) 메모리 빈 공간중 어디에 가져다 놓는가? - First-fit(첫 번째로 빈공간), Best-fit(필요한 공간과 크기가 비슷한 공간), Worst-fit(best의 반대, 가변 파티션이 가능한 조건에서) 교체가 발생할 때 무엇을 교체할 것인가? - 교체전략을 말한다. 디스크에서 데이터를 갖고 왔는데 메모리에 빈자리가 없을 경우 메모리를 점유하고 있는 것 중에서 누군가를 교체시켜야 한다. 이게 바로 replacement 문제이다. 메모리에서 쫓겨날것은 앞으로 잘 사용되지 않을 프로그램이 쫓겨나야 한다. 페이지 교..

운영체제(OS) - 가상메모리(Virtual Memory)

Overlay vs Virtual Memory Overlay 프로그램의 실행간에 메모리 관리를 프로그램이 직접한다. 어떤 데이터는 필요 없으니까 메모리에서 지우고, 필요한 데이터는 메모리로 가져오면서 필요한 부분씩 쪼개서 실행하는것. 게임이라면 게임이 메모리 관리를 직접하는데, 직접하게 만들기 위해선 프로그래머가 직접 개발 당시에 코딩한다. 게임을 만들 때 프로그래머가 직접 설계한다. 운영체제가 메모리 관리를 하지 않는다 Virtual Memory 프로그래머가 메모리 관리를 하지 않고 운영체제가 한다. 운영체제가 알아서 어떤 부분을 가져오고, 지운다. 하지만 한계점이 존재한다. 성능상의 최적화가 안될 수 있고 제대로 동작하지 않으면 성능이 안좋을 수 있다. MMU(Memory Management Unit..

운영체제(OS) - 메모리 관리(Basic Memory Management)

Real Memory(Real Storage) 실제 메모리(주 기억장치)라고도 한다. 메모리는 CPU와 상호작용을 통해 CPU는 메인메모리에 주소로 접근하면 CPU는 메모리에서 해당 주소에 위치한데이터를 가져온다. 주소의 개수 128M의 Ram이 있을 경우 M(메가바이트) = 2의 20승 128 = 2의 7승 2^20 * 2^7 = 2^27만큼의 주소 개수가 사용된다. 재배치 문제 a와 b는 개별 프로그램의 메모리구조이며 각 메모리마다 0~16380의 메모리 영역을 차지한다.. a를 실행하면 0번이 실행되고 24번으로 점프한 후 나머지가 실행되고 끝난다. b는 28번으로 점프해서CMP(비교)를 실행하고 프로그램이 끝난다. 이렇게 작성된 프로그램을 한개의 메모리에 적재를 시킨다. a가 낮은 주소 영역(흑색..

운영체제(OS) - 세마포어(Semaphore)와 뮤텍스(Mutex)

프로세스간 메시지를 전송하거나, 공유메모리를 통해 특정 데이터를 공유하게 되는 경우 문제가 발생한다. 즉, 공유된 자원에 여러 개의 프로세스가 동시에 접근 하면서 문제가 발생하는 것으로써 공유된 자원 속 하나의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한해 두어야 하는데, 이를 위하여 고안된 것이 바로 세마포어(Semaphore)다. 세마포어와 뮤텍스의 차이 - 세마포어(Semaphore): 공유 자원의 데이터 혹은 임계영역(Critical region)등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌.(동기화 대상이 하나 이상) - 뮤텍스(Mutex): 공유 자원의 데이터 혹은 임계영역(Critical region)등에 하나의 Process 혹은 Thread가 접근하는 것..

운영체제(OS) - 식사하는 철학자 문제(Dining Philosophers Problem)

식사하는 철학자 문제 철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다. 1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때 까지 생각하며 대기한다. 2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다. 3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다. 4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다. 5. 다시 생각하다가 배고프면 1번으로 돌아간다. 발생할 수 있는 문제 식사하는 철학자 문제는 교착상태(Deadlock)의 대표적인 예제이..