봉황대 in CS

플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 ) 즉, (1) 정점 a에서 정점 b로 가는 최소 비용과 (2) 정점 a에서 정점 k로 가는 비용 + 정점 k에서 정점 b로 가는 비용을 비교하여 더 적은 비용을 가지는 쪽을 취하는 것이다. N개의 노드가 있을 때, N번만큼의 단계를 반복하여 점화식에 따라 2차원 리스트를 갱신하기 때문에 동적 계획법(Dynamic Programming) 알고리즘에 속한다. ( ↔︎ 다익스트라 : 탐욕(그리디) 알고리즘 ) * 동적 계획법(Dynamic Programming, D..

문제 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 마법사 상어는 N×N 격자(1번~N번)에 파이어볼 M개를 발사한다. 격자의 행과 열 각각은 1번과 N번이 연결되어 있다. 파이어볼은 각각 위치(r행 c열), 질랑 m, 방향 d, 속력 s의 정보를 가지며, 해당 위치에서 대기하고 있다. 마법사 상어가 모든 파이어볼에게 K번의 이동을 명령한다. 파이어볼은 자신의 방향으로 속력 s칸만큼 이동하는데, 방향은 다음의 8개 칸의 방향을 의미한다. 파이어볼이 한번 이동을 할 때마다..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 프로세스는 한 프로세스에 의해 새로 생성될 수 있으며, 생성된 프로세스는 자신에 의해서(수행을 마쳤을 경우) 또는 외부의 요청에 의해서 종료한다. 프로세스 생성 프로세스는 다른 프로세스를 생성할 수 있다. 이때 프로세스를 생성하는 프로세스를 부모 프로세스라고 하며, 생성된 새로운 프로세스는 자식 프로세스라고 한다. 부모 프로세스와 자식 프로세스는 1:N 관계이기에 전체적으로 트리가 구성된다. 프로세스 각각에게는 고유 번호 즉, 프로세스 식별자(PID)가 할당된다. (보통 정수 값) 위의 트리 그림에서 root..

콜 스택 (Call Stack) 함수의 호출을 기록하는 자료구조 메모리의 스택(stack) 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다. 함수 호출 시 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 함수에서 선언된 지역 변수 등이 저장되는데 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(Stack Frame)이라고 한다. * 프레임 (Frame) : 함수 호출 시 스택 상에서 운용되는 데이터 * 프레임 포인터 (Frame Point / Stack Frame Pointer) 스택 상의 프레임 시작 주소 (스택에 push 되기 전 top에 있던 프레임의 시작 주소) 함수마다 프레임의 크기가 다르기 때문에 함수 호출이 끝난 뒤, 해당 함수가 ..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 프로세스 제어 블록 (Process Control Block, PCB) 커널 내의 프로세스 문맥 정보를 저장하는 자료 구조 프로세스의 일생 동안 해당 프로세스의 모든 정적, 동적인 정보를 가진다. 즉, 커널이 프로세스를 관리하기 위한 실체이다. 문맥 교환 시 커널 수준 문맥은 추후 복구를 위해 PCB에 저장(save), 스케줄링된 새로운 프로세스의 문맥이 적재(restore)된다. 2022.07.07 - [Computer Science/Operating System] - [Chapter 3. 프로세스] 프로세스..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 프로세스는 실행되면서 그 상태가 변한다. 프로세스의 상태는 그 프로세스의 현재 활동에 따라서 정의된다. * 어느 한순간에 한 처리기 상에서는 오직 한 프로세스만이 실행된다. * 준비 및 대기 상태에는 많은 프로세스가 해당 상태에 있을 수 있다. 생성 (new) 프로세스가 생성된 상태 즉, PCB와 메모리 상의 주소 공간(사용자 문맥)이 마련된 상태이다. 준비 (ready) CPU의 배정을 기다리는 상태 스케줄링에 의하여 선택만 된다면 언제든지 실행이 될 수 있는 상태이며, 준비 리스트 또는 준비 큐에서 기다리고..

문제 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 크기가 3×3인 배열 A가 있으며, 배열의 인덱스는 1부터 시작한다. 1초가 지날 때마다 배열에 다음 두 개의 연산 중 하나가 적용된다. 1. R 연산 : 행의 개수 ≥ 열의 개수인 경우, 배열 A의 모든 행에 대하여 정렬을 수행 2. C 연산 : 행의 개수 r and len(A[0]) > c: # 범위 확인 (런타임 에러 - Index error 발생) if A[r][c] == k: break if time == 100: time = -1 br..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 프로세스 (Process) 실행 중인 프로그램 시스템 콜을 통해 자원을 요구하는 주체 * 운영체제(시스템) 프로세스 : 운영체제가 필요에 의해 생성, 시스템 코드를 실행한다. * 사용자 프로세스 : 사용자 코드(응용 프로그램)를 실행한다. → 자원 경쟁 측면에서 둘은 동일하다. * 프로그램 그 자체는 프로세스가 아니다! [ 프로그램 ] 명령어 리스트를 내용으로 가진 저장 장치에 저장된 파일(실행 파일)을 뜻한다. → 수동적인 존재 [ 프로세스 ] 메인 메모리에 존재하며, 다음에 실행할 명령어를 지정하는 프로그램..