봉황대 in CS

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1부터 n까지 번호가 붙어 있는 n개의 포도주가 들어있는 잔이 일렬로 놓여있다. 포도주 시식에는 두 가지 규칙이 존재한다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 최대로 마실 수 있는 포도주의 양을 구하는 것이 문제이다. 풀이 DP로 문제를 해결할 수 있다. 첫번째 시도 (..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2행 n열로 배치되어 있는 스티커 뭉탱이가 있다. 스티커의 품질은 좋지 않아서, 스티커 한 장을 떼면 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. (뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨) 모든 스티커를 붙일 수 없으니, 각 스티커에 점수를 매겨 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다. 즉, 2n개의 스티커 중 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 ..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 회전 지연 시간 최적화 초창기 디스크 접근 시간을 좌우하는 것은 대부분 탐색 시간이었다. * 탐색 시간 (seek time) : 디스크 암(arm)이 헤드를 원하는 실린더로 움직이는 데 걸리는 시간 하지만 요즘 사용하는 하드 디스크는 탐색 시간과 회전 지연 시간의 자릿수가 같은 정도로 발전되어서 회전 지연 시간 최소화로도 성능을 개선할 수 있게 되었다. 특히 한 트랙 내 여러 곳에 분산된 섹터들 중 일부만 요구하는 요청이 많을 경우 회전 지연 시간을 최적화하여 성능을 크게 개선할 수 있다. 아래는 회전 지연 시..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 자기 디스크 (Magnetic Disk) 플래터(platter) : 원형 평판 모양으로, 정보를 플래터 상에 자기적으로 기록하여 저장한다. 읽기-쓰기 헤드(read-write head)는 모든 플래터의 각 표면 바로 위에서 움직이며 헤드는 모든 헤드를 한꺼번에 이동시키는 디스크 암(disk arm)에 부착되어 있다. 디스크 암 : 읽기나 쓰기를 수행해야 하는 트랙을 찾아가는 역할 동일한 암 위치에 있는 트랙의 집합은 하나의 실린더(cylinder)를 형성한다. 플래터의 표면은 원형 트랙(track)으로 논리적으..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 가상 메모리 시스템은 파일의 추상화를 기반으로 동작한다. 즉, exe 파일을 구성하는 블록들이 프로세스의 페이지로 맵핑되어 하나의 프로세스로 나타나도록 추상화되는 것이다. * exe 파일 : 컴퓨터의 실행 파일 또한 모든 입출력 장치들은 장치 파일이라는 개념으로 일관성 있게 추상화된다. 예를 들어, 동작 센서도 특수한 형태의 파일로 생각하여 이에 대해서도 일반적인 파일에 대한 조작인 open/close 및 read/write 등의 조작을 하게 된다. 이 추상화의 실현을 위하여 파일 시스템이 존재하는 것이다. ..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 파일 (File) 운영체제는 컴퓨터 시스템을 편리하게 사용하기 위해 1. 저장된 정보에 대한 일관된 논리적 관점으로 제공하고 2. 저장 장치의 물리적 특성을 추상화하여 논리적 저장 단위, 파일을 정의한다. 파일은 보조 저장 장치에 저장되어 있는 관련 정보의 집합체이다. = 작성자와 사용자에 의해서 그 의미가 정의된 비트, 바이트, 행 또는 레코드들의 연속체 하나의 파일은 디스크 내 여러 개의 섹터로 구성되어 있다. (섹터 : PC용 하드 디스크의 경우 512 B) 메모리와 디스크 간의 입출력 전송은 블록 단위로..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 커널 메모리의 할당 (Kernel Memory Allocation) 사용자 모드에서 수행중인 프로세스가 추가적인 메모리를 요구하면 커널이 관리하는 가용 페이지 프레임에서 페이지들이 할당된다. 하지만 커널 메모리는 사용자 모드 프로세스에게 할당해주는 페이지 리스트와는 별도의 메모리 풀에서 할당받는다. 그 이유는 다음과 같다. 1. 커널은 다양한 크기의 자료구조를 위해 메모리를 할당받는데, 이때 단편화에 의한 낭비를 최소화해야 한다. 2. 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 스레싱 (Thrashing) 스레싱은 과도한 페이징 작업으로 프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상을 말한다. 운영체제는 CPU의 이용률(utilization)을 계속 감시하고 있다. 만약 CPU 이용률이 너무 낮아지면 이때 운영체제는 새로운 프로세스를 시스템에 더 추가하여 다중 프로그래밍의 정도(degree of mulitprogramming)을 높인다. 이때 전역 페이지 교체 알고리즘을 사용해서 어떤 프로세스의 페이지인지에 대한 고려 없이 교체를 수행하..