본문 바로가기

Computer Science36

맨땅에 헤딩하면서 배운 배낭문제(Knapsack) 유형과 접근법 정리 배낭문제란? 배낭문제는 최대 k 무게를 싣을 수 있는 배낭에 n개의 아이템 을 넣어서 최대의 가치(아이템마다 가치가 다름) 를 만들어내는 문제입니다. 이 문제는 크게 두 가지 유형으로 나눠집니다. 1. 분할 가능한 문제 (Fractional) 대표적인 문제로는 오천원권 만원권 오만원권이 있을 때 목표 금액을 만들기 위해 최소의 수의 지폐를 사용하는 문제가 있습니다. 각 지폐는 더 작은 가치의 지폐로 나눠질 수 있습니다. 이 문제는 그리디 알고리즘 을 사용합니다. 2. 분할 불가능한 문제 (0/1) 이번 포스트에서 살펴볼 내용은 불할 불가능한 문제입니다. 현재 한국에서 사용하는 화폐 단위가 아니라 랜덤한 가치의 화폐가 주어지는 경우입니다. 예를들어 3만원권 7만원권 13만원권이 주어진다면 이는 분할 불가능.. 2023. 4. 23.
[운영체제] 파일시스템이란? 파일이란? 파일은 관련이 있는 일련의 정보들의 집합 논리적인 단위입니다. 파일의 기능으로는 create, read, write, reposition(lseek), delete, open, close 등이 있습니다. Reposition 파일을 읽거나 쓸 때는 해당 파일에서 어디까지 읽거나 썼는지를 가리키는 포인터를 계속 수정하게 되는데, 특정 위치에서부터 읽거나 쓰고 싶을 때는 reposition을 통해 포인터를 옮깁니다. Open 파일을 읽거나 쓰기 위해서는 먼저 open을 해야하는데, 이때는 디스크에서 메모리로 파일의 메타데이터를 올리는 역할을 합니다. 파일의 Metadata 어떤 파일에 저장된 내용이 아닌, 파일을 관리하기 위한 각종 정보입니다. 파일 이름, 유형, 저장된 위치, 파일 사이즈, 접근 .. 2023. 3. 31.
[운영체제] Page Fault를 줄이기 위한 운영체제의 노력 Paging System의 메모리 관리에서 운영체제는 Page Fault를 줄이는 것이 중요합니다. Paging System (feat. Demand Paging) Paging System이란 어떠한 프로그램(프로세스)를 메모리에 올릴 때, 일정 크기의 Page로 나눠서 올리는 것입니다. 그리고 대부분은 Demand paging을 사용하는데, 이는 실제로 필요할 때 필요한 만큼의 Page만 메모리에 올리는 것을 의미합니다. 이렇게 함으로써 얻는 이점은 I/O 감소, 메모리 사용량 감소, 빠른 응답시간, 더 많은 사용자 수용입니다. 이런 방법을 사용하기 위해, 논리주소와 실제 메모리 주소를 mapping시켜놓은 page table에서 'Valid / Invalid bit'를 사용합니다. 이는 해당 페이지가.. 2023. 3. 29.
[운영체제] Memory Management - Segmentation Segmentation이란 Paging 기법은 같은 크기로 page를 나누는 반면, Segmentation 기법은 의미 단위마다 각각 다른 크기로 segment를 나누는 것입니다. 여기서 의미 단위는 code, data, stack 같은 것을 의미합니다. 이 방법을 통해서 얻는 장점은 하나의 segment가 동일한 목적을 가지고 있기 때문에, 프로세스 간에 공유를 하거나 segment별로 접근권한을 다르게 주는 것입니다. paging에서는 하나의 페이지에 여러 다른 기능들이 포함되기 때문에 이런 것을 하기가 어렵죠. 또한 segment의 물리 주소를 나타태는 table의 크기가 작습니다. paging에서는 page의 크기가 작기 때문에 table크기도 엄청 컸습니다. 반면, segment는 보통 5개 정.. 2023. 3. 28.
Linked List 개념을 활용한 문제 풀이 (프로그래머스, 2021 카카오 인턴십 표 편집) 아래의 문제를 LinkedList를 활용해서 풀다가 시간 초과가 발생하며 배운 점을 간단하게 기록하고자합니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 상황에는 List 내의 삽입과 제거가 빈번하게 발생하기 때문에, 당연히 LinkedList 를 활용해야겠다고 생각했지만 시간초과가 발생했습니다. 그 이유는 Java의 LinkedList 자료구조에서 삽입과 제거가 O(1)의 시간복잡도로 수행할 수 있는 것은 맞지만, 해당 위치로 이동하는데에 O(n)의 시간이 소요되기 때문입니다. 예를 들면 add(index, 추가할 자료), remove(inde.. 2023. 3. 22.
이진 트리 표현하는 방법 이진 트리를 표현하는 방법은 크게 두 가지가 있습니다. 1. 배열을 통해서 표현하는 방법 2. 포인터를 통해서 표현하는 방법 배열을 통해서 표현하기 이 방법으로 트리를 표현하게 되면, 특정 위치의 트리 값을 찾을 때 0(1)의 빠른 속도로 가능하나는 장점이 있지만, 편향된 트리 구조에서는 낭비되는 공간이 많다는 단점이 있습니다. 따라서 포화 이진 트리인 경우에는 이 방법을 활용하는 것이 좋겠습니다. 구현하는 아이디어는 간단합니다. 아래 그림처럼 루트 노드부터 한 depth씩 내려오면서 배열에 하나씩 기록하는 것입니다. 그리고 아래의 몇 가지 규칙을 기억하면 좋습니다. level별 노드의 개수 = 2^level ex) depth가 2인 level의 노드의 개수 = 2^2 = 4 만들어야할 배열의 크기 = .. 2023. 3. 18.
[운영체제] Memory Management - Paging 물리 메모리를 할당하는 방법 Contiguous allocation 이 방법은 프로세스를 분리하지 않고, 연속적인 공간에 적재하는 방법입니다. 메모리에는 여러 프로세스가 임의의 시간에 올라갔다 내려가기 때문에, 이 방법으로는 효율적으로 메모리를 관리하기 어렵습니다. Noncontiguous allocation 위의 방법과 달리, 하나의 프로세를 적절히 나눠서 물리 메모리에 할당하는 방법입니다. 위의 방법보다 더 복잡하지만 공간을 효율적으로 사용할 수 있으며 현대의 컴퓨터는 이 방법을 사용합니다. 이 방법은 다시 크게 세 가지로 나눠집니다. Paging Segmentation Paged Segmentation Paging Paging은 논리 메모리를 동일한 크기의 여러 공간(page)으로 나누고 이 페이지.. 2023. 2. 16.
[운영체제] Memory Management 1 주소의 세 가지 종류 Symbolic Address 프로그래머가 변수나 함수에 이름을 붙이는 것 Logical Address 소스 코드를 컴파일하면 논리 주소로 바뀜. 프로세스마다 독립적으로 가지는 주소 공간 모두 0번지부터 시작 다른 프로세스의 주소공간을 침범하기 어려워짐. !!CPU가 보는 주소!! Physical Address 메모리에 실제 올라가는 위치 주소 바인딩 논리 주소를 물리 주소로 바꾸는 것이 주소 바인딩입니다. 주소 바인딩을 하는 방법에는 세 가지가 있습니다. Compie time binidng 컴파일시에 고정 값으로 물리 주소를 지정하는 것입니다. 메모리 상황을 고려하지 않기 때문에 상당히 비효율적이며, 메모리에 프로세스 하나올라가는 시스템에 적합합니다. Load time bining.. 2023. 2. 15.
[운영체제] 데드락 (Deadlock) 데드락이란? 여러 프로세스들이 서로가 가진 자원을 기다리며 block된 상태입니다. 기본적으로 프로세스는 필요 자원 중 가능한 자원을 획득한 후, 나머지 자원을 획득할 때까지 기존 자원을 놓지 않고 기다리기 때문에 이러한 문제가 발생할 수 있습니다. 여기서 자원이란 I/O device, CPU와 같은 하드웨어 자원과 semaphore와 같은 소프트웨어 자원을 포함하는 개념입니다. Deadlock 발생의 4가지 조건 Mutual Exclusion 하나의 자원은 한 시점에서 오직 하나의 프로세스만 사용할 수 있고, 동시에 두 개 이상의 프로세스가 사용할 수 없습니다. No Preemption 프로세스는 자원을 스스로 내려놓을 뿐 뻇기지 않습니다. Hold and Wait 프로세스는 필요한 모든 자원을 획득할.. 2023. 2. 14.

티스토리툴바