본문 바로가기
반응형

전체 글

 (174)
[ 운영체제 ] 가상 메모리1 - Swapping, Demand Paging, Valid bit, Page Fault 가상 메모리가 무엇일까? 물리적 주소와 논리적 주소를 이해했다면 쉽게 이해할 수 있다. 왜냐하면 메모리는 주소의 집합이기 때문이다. 가상 메모리는 가상 주소의 집합에 불과하다. 우리는 논리적 주소(가상 주소)를 'CPU 입장에서의 주소'라했고, 모든 프로세스의 가상 주소는 0부터 시작한다고 했다(여기 참고). 이렇게 모든 프로세스는 각각 독립적인 가상 주소 공간을 가지는데, 이를 가상 메모리라고 한다. 그렇다면 가상 메모리를 사용하는 이유는 무엇일까? 크게 아래 세 가지를 뽑을 수 있다. 1. 사용자 편의성 사용자는 가상 메모리만 신경쓰면 된다. 물리적 메모리로의 사상은 OS가 알아서 한다. 2. 프로세스간 메모리 보호 Base Register와 Limit Register로 프로세스는 물리적 메모리에서 ..
[ 백준 5557 ] 1학년 (C++) https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 배낭 문제를 먼저 풀어서 그런지 쉽게 풀었다. 근데 신기한건 정말 내 생각대로 풀고 정답을 봤는데 내 코드랑 똑같았다. 나도 실력이 늘었나??^^ dp 문제니깐 dp 정의부터 하자!! dp[i][j] = k i번째 숫자까지의 조합으로 j를 만들 수 있는 경우의 수가 k 가지 dfs 또는 bfs랑 거의 흡사하다. 첫번째 숫자를 기준으로 +-(다음 숫자)를 해주고 범위가 0~20 사이면 경우의..
[ 백준 12865 ] 평범한 배낭 (C++) 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.acmicpc.net 아주아주 유명한 01 배낭문제다. 알고리즘 수업을 들어본 적이 있다면 아마 유사 문제를 풀어봤을 것이다. 내 풀이도 별로 다를거 없다. 다른 사람들 풀이도 봤는데 똑같았다. dp 문제니깐 dp 정의를 먼저 하자 dp[i][j] = m : 1~i번째 물건의 조합으로 배낭의 무게가 j일때 가치합이 m 사실 이 문제는 dp 정의부터 이해..
[ 백준 12026 ] BOJ 거리 (C++) https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 정답률 보고 쉬울줄 알았는데 생각보다 잘 안 풀렸던 문제다. 우선 dp 문제이기 때문에 dp를 먼저 정의하자. dp[i] : i까지 오는데 필요한 최소 에너지 양 알고리즘은 다음과 같이 짰다. 모든 기준점에서 가능한 다음 문자를 찾고 에너지 양을 갱신해준다. 1) 모든 i에 대해, input[i]는 input[i + 1] ~ input[n]까지 가능한 문자를 찾는다. input[i] = 'B'라면 가능 문자는 'O' input[i] = 'O'라면 가능 문자..
[ 운영체제 ] 메모리 관리3 - 페이징 단점, 내부 단편화, TLB, 세그멘테이션(Segmentation) 페이징은 외부 단편화 해결 방법으로 논리적 주소의 물리적 주소 사상을 불연속적으로 하는 메모리 관리 구조를 말한다. 그런데 이 세상에 완벽한 것은 없다. 득이 있으면 실도 있는법. 이번 글에서는 페이징의 세 가지 단점에 대해 소개한다. 그리고 각 문제의 해결책까지 살펴보는 것이 목표다. 우선 목차는 아래와 같다. 1. 내부 단편화 2. 메모리에 두 번 접근하는 문제 3. 프레임 내 데이터 종류 불일치 문제 1. 내부 단편화 (Internal Fragmentation) 외부 단편화는 주소를 연속적으로 할당해서 생기는 메모리 낭비였다. 이와 반대로 내부 단편화는 주소를 불연속적으로 할당해서 생기는 메모리 낭비다. 메모리 낭비가 생기는 이유는 '고정된 프레임 크기' 때문이다. 프레임 크기는 메모리를 읽기/쓰기..
[ 백준 11058 ] 크리보드 (C++) https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net dp 정의를 먼저 하자! dp[i] = i번째 눌렀을 때 화면 출력 최대값 '전체선택 - 복사 - 붙여넣기'를 한 묶음으로 생각해야 한다. 이는 세 번의 클릭이 필요한데, 일단 한번 하고 나서는 붙여넣기만 하는게 이득이다. 아래 그림을 보자. 위 그림은 n에서 '..
[ 운영체제 ] 메모리 관리2 - 페이지 테이블의 세 가지 구조 저번 시간에 '풀리지 않은 의문점'에서 페이지 테이블은 연속적이기 때문에 페이지 테이블을 새롭게 디자인할 필요가 있다고 했었다. 따라서 오늘은 페이지 테이블의 세 가지 구조를 다룬다. 세 가지 구조는 각각 아래와 같다. 이 글의 목차로 생각하면 된다. 1. 계층적 페이지 테이블 (Hierarchical Page Table) 2. 해시형 페이지 테이블 (Hashed Page Table) 3. 역페이지 테이블 (Inverted Page Table) 1. 계층적 페이지 테이블 (Hierarchical Page Table) 우선 페이지 테이블이 연속적일 경우 어떤 문제가 발생하는지 보자. 일반적으로 페이지의 크기는 4KB(2^12 B)로 잡는다. 32 비트 주소 체계와 64비트 주소 체계인 경우 페이지 테이블의..
[ 백준 1495 ] 기타리스트 (C++) https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net dp 문제다. 처음 문제를 읽고 떠로으는 생각은 bfs였지만 시간복잡도가 대충 O(2^n)이 나와서 시간 초과를 받게 될게 뻔했다. 남은건 dp 뿐이었다. 근데 나는 dp가 너무 어렵다... 아이디어가 생각이 나지 않아 아이디어만 참고했다. 그래서 50점짜리 풀이라고 해야하나.... 이중 for문으로 풀 수 있는 문제다. 우선 이 문제의 아이디어는 다음과 같다..
반응형

티스토리툴바