기록공간

문제 비어있지 않은 배열 N개의 정수를 담는 A가 주어진다. 0

파일 시스템은 순수한 소프트웨어다. 이점은 앞부분에서 다룬 CPU 가상화, 메모리 가상화 부분과 다른 점이다. CPU 가장화나 메모리 가상화에서는 하드웨어가 필요하다. (특권 모드로의 변환을 위한 명령어, 페이징을 위한 하드웨어 등이 그것이다) 파일 시스템의 종류는 매우 다양하다. 모든 파일 시스템들이 서로 다른 자료 구조를 가지고 있으며 각각은 장단점이 있다. 여기서는 간단한 파일 시스템 (Very Simple File System, vsfs)을 사용하여 개념을 소개하고, 파일 시스템에 대한 사례들을 다루며 현실에서 어떻게 동작하는지 이해해 보도록 하겠다. 생각하는 방법 파일 시스템에 대해 학습할 때, 두 가지 측면에서 접근할 것을 권장한다. 그 두 측면을 다 이해하게 되면 파일 시스템이 기본적으로 어..

문제 N개의 정수를 담는 배열 A가 주어진다. 0

문제 N개의 숫자를 원소로 가지고 배열 A가 주어진다. 여기서 (X, Y, Z) 인덱스 위치가 주어진다. (0 1일 경우 max(0, M[1 - 1]) + max(0, N[1 + 1]) Y -> 2일 경우 max(0, M[2 - 1]) + max(0, N[2 + 1]) ... Y -> 6일 경우 max(0, M[6 - 1]) + max(0, N[6 + 1]) 이 값들중 가장 큰 값이 정답이 된다. 코드는 다음과 같다. for문을 중첩하여 사용하지 않았기 때문에 시간 복잡도는 O(N)이 된다. class Info{ int sum_from_front = 0; int sum_from_back = 0; } class MaxDoubleSliceSum { public int solution(int[] A) { if..

문제 N개의 숫자가 들어있는 배열 A가 주어진다. 우선 여기서 Leader 숫자를 먼저 찾는다. Leader 숫자가 되기 위해서는 두 가지 조건 중 하나가 필요하다. 배열에서 가장 많이 중복되는 값 배열 길이의 절반 값보다 더 많이 나오는 값 이제 A를 둘로 쪼갠다. (0 = limitEquiLeft) && (RightCount >= limitEquiRight)) { ++result; } } return result; } }

이번에는 프로그램이 메모리에 적재되어 프로세스의 상태로 실행될 때, 메모리 공간에서 발생하는 일들에 대해 정리해보도록 하겠다. RAM에 할당된 프로세스 공간 프로세스는 RAM에 일부 공간을 할당받아 생성된다. 그렇게 할당받는 공간은 크게 4가지 영역으로 구성된다. 1. 코드(Code) 영역 : 실행 파일을 구성하는 명령어들이 올라가는 영역 코드가 들어가는 부분이므로 쓰기가 금지된 영역 수정될 것이 없으므로 고정(Static)된 크기를 가진다. 2. 데이터(Data) 영역 : 전역 변수들을 저장하는 영역 사실 데이터 영역은 초기화된 값이 저장되는 데이터 영역과 초기화되지 않은 값이 저장되는 bss 영역이 구분된다. 그렇게 해서 크게 5가지로 나누는 경우도 있다. 3. 힙(Heap) 영역 : 동적(Dynam..

문제 정수값을 담는 N개의 배열 A가 주어진다. A에 존재하는 정수값이 중복으로 배열 사이즈의 절반 이상 존재하는 경우 그 정수값은 Dominator가 된다. 이 Dominator를 찾고, 이 Dominator 값인 인덱스 위치 중 하나를 출력하는 문제이다. 해결 방법 중복되는 값으로 몇 개가 존재하는지 효과적으로 알 수 있도록 해시 테이블을 사용한다. 해시의 Key값에는 인덱스에 존재하는 값이 들어가고, Value값은 그 값이 존재하는 인덱스들을 담는 Vector 컨테이너가 들어간다. 배열 A를 순회돌며 해시 테이블에 Key값과 Value값을 넣어준다. 그 작업이 끝나면 해시 테이블에 들어간 값(Iterator)를 순회돌며 배열 A 사이즈의 절반이 넘어가는 Dominator가 존재하는지 찾는다. 만약 ..

문제 N개의 원소가 담긴 배열 H가 주어진다. H[0] ~ H[N-1] 까지의 원소에는 벽의 높이 값이 들어간다. 이때 H 높이들을 만족하는 벽을 쌓기 위해서 최소 몇 개의 블럭이 필요한지를 구하는 문제이다. 해결 방법 스택을 활용하여 풀 수 있는 문제였다. 스택을 사용하는 이유는 서로 같은 높이에 있는 있거나 가장 낮은 높이의 값들은 블럭을 하나로만 써야 최소한의 블럭을 만들 수 있기 때문이다. 이러한 값들을 스택에 기록해 블럭을 어떻게 만들지 결정한다. 다음과 같은 규칙으로 높이 값을 순회돌며 스택을 사용한다. (i번째 높이 값을 h라고 했을때) 1. 스택이 비어있다 => h를 push한다. 2. 스택 top의 값이 h보다 큰 경우 => pop 하고 배치 블럭 수를 1 증가시킨다. 3. 스택 top의..