복습노트 복습노트

What is a Process? 우리는 보통 디스크에 있는 것을 프로그램이라 하고 이 프로그램이 메모리에 load 되면 process 라고 합니다. 여기서 process는 job, task 모두 동일하게 사용하겠습니다. 프로세스는 code(=text), data, stack, heap 과 program counter를 포함합니다. Process State new : 프로세스가 처음에 생성되었을 때 ready : 프로세스가 CPU에 할당되기를 기다릴 때 running : 프로세스가 할당되어 실행될 때 waiting : 프로세스가 event를 기다릴 때 terminated : 프로세스가 실행을 끝냈을 때 Process Control Block (PCB) 각각의 process는 자신의 정보 묶음 block인..

운영체제 란?? user computer 와 computer hardware 를 매개하는 프로그램입니다. 운영체제의 역할은 크게 2가지로 나뉘는데 사용자 관점(User View) 와 시스템 관점 (System View)로 나뉠 수 있습니다. User View 사용자가 컴퓨터를 쉽게 이해하고 또한 컴퓨터의 자원 사용(Resource utilization)을 신경쓰지 않게 도웁니다. 즉, 사용자에게 편의를 제공해줍니다. System View 시스템 관점에서 운영체제를 보면 자원 할당자(Resource Allocator) 입니다. 자원을 사용하는데 발생되는 충돌(conflict)을 효율적이고 공평하게 배분합니다. 또한 운영체제는 컴퓨터 자원들을 관리하는 제어 프로그램(Control Program)으로서 동작합..

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net n * m 행렬이 주어지면 바이러스가 퍼지지 않게 3개의 벽을세워 최대의 안전지대를 형성하는 것이 문제입니다. 행렬값 0은 안전지대, 1은 벽, 2는 바이러스공간입니다. 바이러스는 상하좌우로 계속 해서 퍼집니다. 예를들어 다음과 같은 행렬이 주어졌다면 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 이제 벽을 3개 세워 바이러스를 최대로 막아줘야..

문제 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 과 유사한 문제입니다. 대신 최소 시간의 경우의 수를 세는 조건이 추가되었습니다. 예를들어 5에서 17로 간다고 하면 1. (5 -> 10 -> 9 -> 18 -> 17) 2. (5 -> 4 -> 8 -> 16 -> 17) 총 2가지가 존재합니다. 처음에 재귀함수를 구현하여 해결하려 했지만 구현하지 못했습니다. 그 다음 bfs로 접근해 보았습니다. cin >> n >> k; queue q; q.pus..

문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net n개의 노드와 m개의 간선 정보가 주어지면 1~n 번 노드 각 노드 기준으로 나머지 노드로 가는 최소비용을 구하면 되는 문제입니다. 단순히 생각하면 1~n 번 각각 다익스트라를 실행해서 구할 수 있습니다. 하지만 플로이드-와샬 알고리즘을 사용하면 좀더 빠르게 구할 수 있습니다. 플로이드-와샬 알고리즘은 모든 정점에대해서 최소비용을 구할 수 있습니다. 다익스트라는 시작점을 기준으로 구하지만 플로이드-와샬은 모두 구할 수 있다는 장점이 있습니다. 플로이드-와샬은..

문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net n개의 수열을 입력받아 가장 긴 바이토닉 수열의 길이를 출력하면 되는 문제입니다. 바이토닉 수열이란 오름차순으로 증가하다가 내림차순으로 감소하는 수열을 말합니다. 예를 들어 {1, 2, 5, 4, 3} 은 바이토닉 수열입니다. 해당 문제를 보면 이 문제와 매우 유사하다는 것을 알 수 있습니다. 다만 증가하는 것만이 아닌 감소하는 부분까지 생각해줘야 합니다. 위와 같은 배열이 있다고 가정해 봅시다. 여기서 dp 를 활용해 이전 문제에서 풀었던 방식을 사용해 가장 긴 증가하는 수열..

문제 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net n * n 행령이 주어지면 b번곱한 행렬을 출력하는 문제입니다 행렬이 너무 커질 수 있으므로 행렬이 모든 값은 1000으로 나눈 나머지입니다. 딱 보면 백준 1629 문제와 매우 유사합니다. 분할 정복으로 접근하면 될것 같습니다. 여기서 막혔던 것은 분할정복으로 이차원 배열을 return 하는 것이 까다로웠습니다. int arr[6][6]; int result[6][6]; cin >> n >> b; for (int i = 0; i < n; i++) { for (int j ..

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열 주어지고 폭발 문자열이 주어집니다. 주어진 문자열에서 폭발 문자열이 발견되면 폭파됩니다. 예를들어 주어진 문자열이 mirkovC4nizCC44 위와 같고 폭발 문자열이 C4 라면 마지막에는 mirkovniz 남습니다. 처음에 이 문제를 발견했을 때 생각했던게 먼저 KMP 알고리즘으로 문자열과 폭발 문자열이 같은 부분을 찾고 문자열을 폭발 문자열을 빼고 합치는 과정이 번거로웠습니다. 힌트를 얻고 보니 "스택" 자료구조를 사용해 해결하였습..