분류 전체보기 (174) 썸네일형 리스트형 [ 운영체제 ] 프로세스의 상태, Context Switch 프로세스는 커널의 PCB에 의해 관리된다. PCB 안에는 프로세스에 관한 정보들이 저장되어 있는데, '상태' 정보가 그 중 하나다. 상태의 종류를 알아보기 전에 상태 정보를 저장하는 이유를 한번 생각해보자. 우리는 운영체제를 배우면서 늘 두 가지 사실을 기억하고 있어야 한다. 1. CPU는 한 가지 일(프로세스)만 처리할 수 있다! 2. 컴퓨터는 고철 덩어리에 불과하다(근데 반도체를 곁들인). 마법처럼 짠! 하는 일은 없다. 물론 요즘에는 성능이 좋은 CPU가 많이 나와서 여러 개의 프로세스를 동시에 처리할 수 있지만 사실 그것도 여러개의 CPU를 하나의 CPU처럼 보이게 만들어 놓은 것에 불과하다. 하나의 칩에는 한 가지 일만 수행할 수 있다. 이러한 문제 때문에 '상태' 정보가 필요하다. CPU를 최.. [ 백준 2293 ] 동전1(C++) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 정답률이 높아서 좀 당황했던 문제다. 다들 천잰가...? Dp 문제다. 점화식만 잘 세우면 되는데 항상 이게 어렵다. 우선 점화식부터 알아보자. dp[make] = dp[make] + dp[make - use] dp[i] : 동전 i를 만드는 모든 경우의 수 dp[0] = 1 은 고정 이 점화식을 가지고 고민을 해보자. 점화식의 의미를 이해하는 것이 핵심이다. 아래 예시를 보면 이해하는 데 도움이 .. [ 백준 3085 ] 사탕 게임 (C++) https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 제한 시간이 1초로 널널해서 모든 경우의 수를 다 고려해줬다. 모든 칸에 대해 가로/세로 다 swap 해주고 그때의 연속 사탕 수를 확인했다. 코드에서 check() 함수는 최대 연속 사탕수를 반환해주는 함수다. 유의할 점은 swap 해주고 다시 원위치 시켜줘야 하므로 다시 swap을 해줘야 한다. #include #include using namespace std; int N; char map[50][50]; int check() { int Max = 0; char now; int cnt; // 1. 가로 for.. [ 백준 2552 ] 줄 세우기 (C++) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬을 사용하면 간단하게 풀 수 있는 문제다. 위상정렬에 대한 상세한 내용은 알고리즘 파트에서 확인할 수 있다. 링크 바로가기! #include #include #include using namespace std; int N, M; int inDgree[32001] = {0, }; vector graph(32001); void topology_sor.. [ 백준 1197 ] 최소 스패닝 트리 (C++) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 제목에서 친절하게 어떤 문제인지 알려주고 있다. 나는 크루스칼 알고리즘으로 문제를 풀었다. 크루스칼 알고리즘은 알고리즘 파트에서 확인할 수 있으며 코드 구성도 거의 동일하다. 링크 바로가기! #include #include #include using namespace std; class Edge { public: int distance; int .. [ 백준 1916 ] 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 모든 비용이 0 이상이고, 최소비용을 구하기 때문에 다익스트라로 해결할 수 있다. 알면 쉽고, 모르면 어려운 문제라고 생각한다. 다익스트라의 구현 방법은 세 가지가 있는데, 나는 가장 비효율적인 방법으로 풀었다. 시간복잡도는 O(N^2)다. 가장 비효율적인 방법으로 푼 이유는 다른 두 방법을 몰랐기 때문이다. 다익스트라에 대한 설명은 알고리즘 파트에서 볼 수 있다.. [ 백준 1806 ] 부분합 (C++) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N .. [ 백준 1700 ] 멀티탭 스케줄링 (C++) https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제를 읽고 'DFS로 풀면 되겠구나'라고 생각해서 무지성 코딩을 했는데 시간 초과가 났다. 반례들은 다 통과하기 때문에 정답을 도출하는 것에는 문제가 없는 코드라고 생각한다. 다만 모든 경우의 수를 따지기 때문에 비효율적일 뿐... 우선 버리기는 아까우니깐 DFS 코드를 살펴보자. 알고리즘은 아래와 같다. (정답 코드는 아래쪽에 있음) 함수 형태: void DFS(int input[], int .. 이전 1 ··· 13 14 15 16 17 18 19 ··· 22 다음
