포시코딩

Memory Management 7번 챕터의 memory management에서 다룬 메모리 관리는 물리적인 메모리 관리 해당 챕터의 주요한 내용은 '주소 변환' 어떤 프로세스가 논리적인 주소를 가지고 있고 CPU가 논리적인 주소를 주면 물리적인 메모리 주소로 변환해서 메모리 참조를 함 주소 변환에 있어서 운영체제 역할은 없다. 모두 하드웨어가 해줘야 하는 역할 ex) MMU 어떤 프로세스가 CPU로 메모리 접근을 하는데 주소 변환을 할 때마다 운영체제의 개입이 있다면 CPU가 운영체제로 넘어가야 하고 주소 변환 후 다시 CPU가 프로세스한테 넘어오는 과정 자체가 말이 안됨 메모리 접근이 아니라 I/O 장치 접근 할 때 운영체제 개입 필요 이후 배울 Virtual Memory에서 운영체제가 중요한 역할을..

키워드 multilevel paging, valid-invalid bit, protection bit, inverted page table, shared page, segmentation Multilevel Paging and Performance Address space가 더 커지면 다단계 페이지 테이블이 필요 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요 TLB를 통해 메모리 접근 시간을 줄일 수 있음 4단계 페이지 테이블을 사용하는 경우 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고 TLB hit ratio가 98%인 경우 effective memory access time = 0.98 ..

키워드 paging, segmentation, page table, TLB, two-level page table Paging, Segmentation 간단 요약 Paging 기법 하나의 프로그램을 구성하는 주소 공간을 같은 크기의 페이지로 잘라 페이지 단위로 물리적인 메모리에 올려놓거나 할 수 있다. 페이징 기법을 사용하면 hole들의 크기가 균열하지 않아 발생하는 문제나, hole들을 한군데로 밀어넣는 방법을 사용할 필요가 없어진다. 물리적인 메모리에서 비어있는 위치가 있다는건 페이지 프레임이 비어있는 것이기 때문에 프로그램의 어떤 페이지든지 아무데나 들어갈 수 있기 때문 Segmentation 기법 프로그램의 주소 공간을 같은 크기가 아닌 의미 있는 단위로 자르는 방법 때문에 크기가 균일하지 않다...

개요 알고리즘 문제를 풀다보면 결과값에 대해 소수점 n 자리까지 출력하라는 조건을 볼 수 있는데 round 등을 사용하지 않고 간단하게 print()를 사용해 출력하는 방법을 알아보자 방법 # 소수점 3번째까지 출력해야 할 때 result = 3.14159 print('%0.3f' % result) # 3.142 위 방법을 통해 간단히 원하는 결과를 얻을 수 있다.

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net

01 타일(피보나치 수열) https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmic..

키워드 physical memory, contiguous allocation, noncontiguous allocation, fixed partition, variable partition, hole, compaction Allocation of Physical Memory (=물리적인 메모리 관리 방법) 메모리는 일반적으로 두 영역으로 나눠 사용 interrupt vector와 함께 낮은 주소 영역: 운영체제 커널(운영체제 상주 영역) 높은 주소 영역: 사용자 프로세스 영역 사용자 프로세스 영역의 할당 방법 Contiguous Allocation 연속 할당 프로그램이 메모리에 올라갈 때 통째로 올라가는 방법 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것 Fixed partition al..

위상 정렬이란? 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘 최소힙인 heapq를 통해 위상 정렬 알고리즘을 구현할 수 있다. 시간복잡도 O(V+E) V: 노드(=Vertex) E: 간선(=Edge) 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 코드 import heapq N, M = map(int, input().split()) arr = [[] for _ in rang..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net

전위 순회(pre-order) 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회(in-order) 왼쪽 자식 -> 루트 -> 오른쪽 자식 x축 기준 왼쪽부터 출력 후위 순회(post-order) 왼쪽 자식 -> 오른쪽 자식 -> 루트 연습 문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 코드 위에서 설명한 각 순회별 루트, 왼쪽 노드, 오른쪽 노드 방문 순서를 생각해 재귀를 통해 구현해내면 아주 쉽게 구현할 수 있다. class..