CS/Algorithm
[프로그래머스] 2개 이하로 다른 비트
코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 한 개 혹은 두 개의 비트만 바꿔서 현재 숫자보다 큰 값중 최솟값을 찾는 문제입니다. 현재 숫자의 모든 비트가 1인 경우와 0이 한 개라도 존재하는 경우로 나눠서 생각하면 됩니다. 그 이유는 아래와 같습니다. 1) 모든 비트가 1이라면 이보다 큰 수를 만들기 위해서는 무조건 앞에 1비트를 붙이고, 그 다음에 1비트를 0으로 바꿔주는게 최선이겠죠. 2) 비트 중에 하나라도 0이 있다면 그 비트를 1로 바꾸는 순간 현재 숫자보다는 커지는 값이 됩니다. 따라서 되도록 작은 주소값에 있는 0비트를 1비트로 바꾸고, 만약 그 뒤로 1비트가 나타난다면 그 비트도 0으로 바꾸면 총 2개의 비트를 바꾸고 최적값을 찾을 수 있습니다. 이를 코드로..
CS/Algorithm
[프로그래머스] 괄호 회전하기
코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 올바른 괄호 문자열인지 확인하는 함수는 스택을 이용하여 작성했고, 메인 solution 함수에서는 문자열을 회전하면서 올바른 괄호열 때 answer를 1씩 증가시키도록 했습니다. [풀이] # 올바른 괄호 문자열인지 확인하는 함수 def isValidBusket(str): stack = [] for s in str: if len(stack) == 0: stack.append(s) else: # 스택 마지막 원소가 여는 괄호이면서 현재 문자는 닫는 괄호 if stack[-1] in bucketDict and s not in bucketDict: # 두 괄호가 매치되지 않으면 False if s != bucketDict[stack[-1]]: r..
CS/Algorithm
[프로그래머스(Programmers)] 게임 맵 최단거리
https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr BFS로 풀 수 있는 전형적인 문제입니다. 최단거리를 구해야하기 때문에 너비 우선 탐색을 진행해주고 도착점에서 결과값이 1이면 거리가 갱신되지 못한 것이므로 -1을 리턴하고, 그 외에는 도착점의 값을 리턴해주면 됩니다. [풀이] from collections import deque dx, dy = [1,-1,..
CS/Algorithm
[프로그래머스] 쿼드압축 후 개수 세기
https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr - 백준에 있는 쿼드트리 압축 문제와 거의 똑같은 문제다. 각 구간의 시작점과 길이를 생각하는 것이 포인트인데, 이 문제에서는 2의 거듭 제곱수 형태를 하고 있으므로 재귀 호..
CS/OS
[운영체제/OS] 디스크 구조와 I/O 작업 스케줄링
💡0. 들어가면서 이전 포스팅까지 OS의 메모리 관리 기법에 대해 살펴봤습니다. 험난한 길이었습니다. 이번 시간부터는 OS가 어떻게 디스크를 탐색하는지에 대해 공부해보려고 하는데요. 먼저 구글에 '하드디스크'라고 검색해보면 아래와 같은 사진들을 보실 수 있습니다. 그렇다면 우리의 OS는 어떤 방식으로 디스크의 데이터를 읽고 저장할 수 있을까요? 📒 1. 디스크의 구조 아래는 일반적인 디스크의 구조입니다. 디스크는 크게 Cylinder, Platter, Track, Sector, Head로 구성되어 있습니다. Cylinder는 우리말로 원통이고 Platter는 평평한 원판을 의미하죠? 그래서 N장의 Platter를 겹쳐놓은 것을 Cylinder라고 하며, 각 Platter에 대해 Head가 존재하는 구조라..
CS/OS
[운영체제/OS] 프레임 할당(Frame allocation)과 Page fault 관련 기타 이슈들
📒 1. 프레임의 할당 이전의 많은 포스팅에서 가상 메모리의 관리는 애초에 물리적 메모리가 가상 메모리보다 훨씬 작기 때문에 필요한 개념이라고 말씀드렸는데요. 따라서 각 프로세스는 자신이 필요로 하는 "최소한의" 페이지만 사용하는 것이 합리적이라고 볼 수 있습니다. 그렇다면 각 프로세스는 얼마만큼의 프레임을 할당받아야 감당할만큼(?)의 페이지 폴트를 일으키면서 전체 프로세스가 원활하게 돌아갈 수 있을까요? 이 역시 명확한 기준은 없지만 크게 두 가지 방법이 존재합니다. ✅ 1) Local Replacement 이 방법은 프레임을 어떤 프로세스에게 고정 할당(Fixed Allocation)하는 개념에서 시작합니다. 애초에 프로세스 별로 할당된 프레임의 크기가 고정되어 있기 때문에, 페이지 폴트가 발생하면 ..
CS/OS
[운영체제/OS] 여러가지 페이지 교체 정책에 대해
0. 들어가면서 지난 시간에 가상 메모리의 기본적인 개념에 대해 공부했고, 한정된 물리 메모리에 많은 양의 논리 메모리를 로드하기 위한 디맨드 페이징(Demand Paging) 전략에 대해 살펴봤습니다. 디맨드 페이징(Demand Paging)은 필요한 페이지만 물리 메모리에 올려두고, 물리 메모리에 가용한 공간이 없으면 스와핑(Swapping)을 통해 페이지를 교체하는 컨셉을 가진 방법이었습니다. [운영체제/OS] 메모리 관리 - 디맨드 페이징(Demand Paging)과 Page Fault Issue 💡 1. 리마인드 가상 메모리는 Virtual 또는 Logical Memory라고 부르는데, 이전에 메모리 관리를 공부하면서 사용해왔던 개념입니다. 멀티프로세싱 환경에서 각 프로세스는 자신의 가상 메모리..
CS/OS
[운영체제/OS] 메모리 관리 - 디맨드 페이징과 페이지 부재(Page Fault) Issue
💡 1. Remind 가상 메모리는 Virtual 또는 Logical Memory라고 부르는데, 이전에 메모리 관리를 공부하면서 사용해왔던 개념입니다. 멀티프로세싱 환경에서 각 프로세스는 자신의 가상 메모리 공간을 갖고 있고, 런타임에 물리적 메모리 공간에 올려서 사용하는 것이었죠. 가상 메모리 사용의 가장 핵심적인 목표는 프로그래머가 물리적 메모리 공간에 대해 신경쓰지 않고, 논리적 메모리에 대해서만 고민하게 하는 것입니다. 이를 위해 모든 가상 메모리는 통째로 물리적 메모리에 올려지는 것이 아니라, 공유 가능한 부분은 공유하고 / 실제 사용하는 영역만 물리 메모리에 올려집니다. 이를 통해 엄청나게 많고 커다란 프로세스들을 한정된 물리적 메모리 공간 안에서 돌아갈 수 있는 것이죠. 다시 말해, "RAM..
CS/OS
[운영체제/OS] 메모리 관리 - 세그멘테이션(Segmentation)과 페이징 기법
💡 0. 들어가면서 지난 글에서는 메모리 관리 기법 중 페이징 기법에 대해 공부했습니다. 페이징 기법은 논리적 메모리를 페이지 단위로 쪼개고, 물리적 메모리를 프레임 단위로 쪼개서 이를 대응하는 방식으로 연속적이지 않은 주소 공간의 매핑이 가능했습니다. 하지만 페이징 기법에서는 메모리 접근에 대한 오버헤드 문제와 커다란 페이지 테이블을 관리하는 메모리 이슈가 존재했고, 이를 해결하기 위한 TLB 레지스터와 Multi-level paging 등의 개념에 대해서 다루게 되었습니다. [운영체제/OS] 메모리 관리 - 페이징(Paging) 기법 📖 0. 들어가면서 지난 포스팅에서 공부한 Partitioning, Buddy system 등의 메모리 관리 기법은 프로세스의 논리적인 메모리 주소를 물리적인 메인 메모..
CS/OS
[운영체제/OS] 메모리 관리 - 페이징(Paging) 기법
📖 0. 들어가면서 지난 포스팅에서 공부한 Partitioning, Buddy system 등의 메모리 관리 기법은 프로세스의 논리적인 메모리 주소를 물리적인 메인 메모리에 연속적인 Mapping을 전제했습니다. [운영체제/OS] 메모리 관리 - 파티셔닝(Partitioning)과 버디 시스템(Buddy system) 이번 포스팅에서는 메모리 관리를 실전(?) 방법들에 대해서 공부하려고 합니다. 단, 지금부터 소개하는 방법들은 기본적으로 프로세스의 크기만큼 물리 메모리에 충분한 공간이 있음을 가정합 studyandwrite.tistory.com 하지만 지금부터 알아 볼 페이징(Paging) 기법은 물리적인 주소가 연속적이지 않은 상황에서도 매핑이 가능합니다. 어떤 방식인지 구체적으로 알아보도록 하겠습니다..
