다락방

1005 ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net #include using namespace std; int t,n,k,w; int main() { cin >> t; for (int i = 0; i > n >> k..

17130 토끼가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17130 17130번: 토끼가 정보섬에 올라온 이유 첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반 www.acmicpc.net #include using namespace std; int n, m, startY ,ans = 0; string s; int dp[1001][1001] = { 0, }; char _map[1001][1001]; bool check = false; void move() { for (int j = startY; ..

퀴즈 1. 페이지 테이블 접근 시 TLB가 어떻게 페이지 테이블의 성능을 향상시키는지 설명하고, TLB miss가 발생하면 시스템이 어떤 과정을 거쳐 메모리에 접근하는지 설명하세요. TLB는 자주 사용되는 주소 변환 정보를 빠르게 참조할 수 있도록 하는 캐시 메모리이다. TLB에 원하는 주소 변환 정보가 있으면, 페이지 테이블을 참조하지 않고 바로 물리적 주소를 얻을 수 있어 성능이 향상된다. TLB miss일 대 시스템은 페이지 테이블을 조회하여 물리적 주소를 찾고, 이 정보를 TLB에 업데이트 한다. 2. 페이징 기법을 사용하는 메모리 관리 시스템에서, 페이지 프레임 수를 늘리는데도 page fault가 발생하는 빈도가 오히려 늘어나는 경우가 있습니다. 이를 Belady의 역설이라고 하는데, 이런 현..

1504 특정한 최단 경로 #include using namespace std; int INF = 98765432; vector vec[802]; int dist[803]; void bfs(int a) { memset(dist, INF, sizeof(dist)); priority_queue queue; queue.push(make_pair(0, a)); dist[a] = 0; while (!queue.empty()) { int sum_distance = queue.top().first; int x = queue.top().second; queue.pop(); if (dist[x] < sum_distance) continue; for (int i = 0; i ncost) { queue.push({ ncos..

운영체제 멀티 프로세서 스케줄링(Multi Processor Scheduling) 8.1 배경 : 멀티프로세서 구조 단일 CPU 시스템에는 하드웨어 캐시 계층이 존재한다. 캐시는 지역성(locality)에 기반한다. 지역성에는 시간지역성(temporal locality)과 공간지역성(spartial locality)의 두 종류가 있다. 시간적 지역성의 기본아이디어는 데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것이다. 멀티프로세서 시스템에서 캐시를 사용하는 것은 훨씬 더 복잡하다. 캐시일관성(cache coherence) 문제가 생길 수 있다. 기본적인 해결책은 하드웨어에 의해 제공된다. 하드웨어는 메모리 주소를 계속 감시하고 항상 ‘올바른’ 순서로 처리되도록 시스템을 관리한다. 특히, 여..

15886 내 선물을 받아줘 2 #include using namespace std; vector adj(1001); int visited[1001]; string move_s; void dfs(int x) { if (visited[x]) return; visited[x] = 1; if (move_s[x] == 'E') dfs(x+1); else dfs(x - 1); } int main() { int block, ans = 0; cin >> block >>move_s; for (int i = 0; i < move_s.size(); ++i) { if (!visited[i] && move_s[i] == 'E') { dfs(i); ++ans; } } cout

10451 순열 사이클 #include using namespace std; vector adj(1001); int visited[1001]; void dfs(int x) { visited[x] = 1; if (!visited[adj[x]]) { dfs(adj[x]); } } int main() { int test_case, node, max = 0, check; cin >> test_case; for (int i = 0; i > node; memset(visited, 0, sizeof(visited)); for (int j = 1; j > tmp; adj[j] = tmp; } check = 0; for (int j = 1; j

운영체제 5. 스케줄링 : 개요 5.1 워크로드에 대한 가정 프로세스가 동작하는 일련의 행위를 워크로드(Work load)라 한다. 워크로드에 대한 이해도가 높을수록 그에 최적화된 스케줄링 정책을 정교하게 개발할 수 있다. 우리는 시스템에서 실행 중인 프로세스 혹은 작업(job)에 대해 다음과 같은 가정을 한다 모든 작업은 같은 시간동안 실행된다. 모든 작업은 동시에 도착한다. 작업은 일단 시작하면 최종적으로 종료될 때 까지 실행된다. 모든 작업은 CPU만 사용한다.(즉, 입출력을 수행하지 않는다.) 각 작업의 실행시간은 사전에 알려져 있다. 5.2 스케줄링 평가 항목 스케줄링 정책의 평가를 위해 스케줄링 평가항목(Scheduling metric)을 결정해야 한다. 반환시간은 (turnaround tim..

3182 한동이는 공부가 하기 싫어! #include using namespace std; vector adj(1001); int visited[1001]; int ans; void dfs(int x) { visited[x] = 1; if (!visited[adj[x]]) { dfs(adj[x]); } } int main() { int test_case, max = 0, check, ans; cin >> test_case; for (int i = 1; i > tmp; adj[i] = tmp; } for (int i = 1; i

운영체제 3. 제한적 직접 실행 원리(Limited Direct Execution) CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록 물리적인 CPU를 공유한다. 이러한 가상화 기법을 구현하기 위해서는 두 가지 문제를 해결해야 한다. 성능저하 제어문제 제어권을 유지하면서 성능 저하가 없도록 하는 것이 운영체제를 구축하는데 핵심적인 도전 과제이다. 3.1 기본원리 : 제한적 직접 실행 운영체제 개발자들은 프로그램을 빠르게 실행하기 위하여 제한적 직접 실행이라는 기법을 개발했다. 운영체제가 프로그램을 실행하기 시작할 때 프로세스 목록에 해당 프로세스 항목을 만들고 메모리를 할당하면 프로그램 코드를 디스크에서 탑재하고 진입점을 찾아 그 지점으로 분기하여 사용자 코드를 실행하기..