11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 이미 11375번 열혈강호 문제를 통해 이분 매칭을 알았기 때문에 이분 매칭을 사용해야겠다는 것은 금방 알 수 있었다. 하지만 이번 문제는 한 직원이 최대 2개의 일을 할 수 있다. 이걸 어떻게 처리해야 하나, 그냥 한 직원당 dfs를 두 번 돌리면 되나?라고 생각했는데... 맞다! 그냥 dfs 두 번 돌리면 된다 bool dfs(int worker) { visited[worker] = true; for (int job : jobs[worker]) { ..
전체 글
학부 운영체제 과목 수업 중 일부를 정리한 내용 OS, Process, Scheduling, Virtual Memory, Threads 내용 포함 1. OS 하드웨어와 응용 프로그램 사이의 인터페이스, 중재자 역할. CPU, 메모리, I/O 장치, 저장장치 등의 하드웨어 자원들을 관리하고 프로그램들이 상호작용할 수 있도록 한다. 시스템이 정확하고, 효율적으로 작동하도록 한다. Virtualization(가상화) OS는 물리적인 자원(CPU, 메모리, 저장장치)를 가상의 형태로 만든다. e.g. CPU의 가상화 CPU의 가상화로 우리는 많은 프로그램이 동시에 실행되는 것처럼 인식한다. System call kernel이 주요 기능들을 user program이 사용할 수 있도록 안전하게 노출시키는 수단 혹은..
2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 무식하게 경우의 수를 다 세어보려다가 시간 초과 곰곰이 생각해 보다가 DP인 것 같아서 DP로 접근 로또에서 나올 수 있는 최대 숫자 2000, 뽑는 수의 개수 최대 10개 경우의 수를 DP로 구하기 위해 DP[i][j] = 숫자 j개를 뽑는데, 마지막 수가 i인 경우를 나타냈다. DP[10][3]이라면 숫자 3개를 뽑는데, 마지막 수가 10인 경우이다 DP[10][3]은 어떻게 구할 수 있을까? 마지막(세 번째)에 10이 와야 하므로 2번째 숫자는 5 이하의 수만 올 ..