[ 백준 ]
- 1920번 수 찾기
: 이진 탐색 이용 알고리즘. 교재 참고하여 공부 중.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
int N = Integer.parseInt(br.readLine());
int[] nums = new int[N];
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
nums[i] = Integer.parseInt(stringTokenizer.nextToken());
}
Arrays.sort(nums);
int M = Integer.parseInt(br.readLine());
stringTokenizer = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
boolean find = false;
int target = Integer.parseInt(stringTokenizer.nextToken());
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
find = true;
break;
}
}
if (find) {
System.out.println(1);
} else {
System.out.println(0);
}
}
}
}- 2343번 기타레슨
: 마지막에 left가 아닌, right로 반환했다가 틀렸다. while 조건이 깨질 때의 시작 인덱스를 반환해야 함,,
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
int[] A = new int[N];
int left = 0;
int right = 0;
stringTokenizer = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(stringTokenizer.nextToken());
if (A[i] > left) left = A[i];
right += A[i];
}
while (left <= right) {
int mid = (left + right) / 2;
int sum = 0;
int count = 0;
for (int i = 0; i < N; i++) {
if (sum + A[i] > mid) {
count++;
sum = 0;
}
sum += A[i];
}
if (sum != 0) count++;
if (count > M) left = mid + 1;
else right = mid - 1;
}
System.out.println(left);
}
}[ 혼공컴운 ]
Chapter 14. 가상메모리
- 스와핑
: 메모리에서 비사용 프로세스 일부를 보조기억장치의 스왑 영역으로 내보내고(스왑 아웃), 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법(스왑 인) - 메모리 할당 방법 : 최초 적합, 최적 적합, 최악 적합
- 외부 단편화
: 프로세스를 할당하기 어려운 작은 메모리 공간들로 인한 메모리 낭비 현상
-> 압축으로 해결 가능하나, 오버헤드 발생
-> 가상 메모리 기법 중 페이징 기법 이용 - 가상 메모리
: 실행하려는 프로세스의 일부만 메모리에 적재하여 메모리 활용하는 기법
-> 페이징, 세그멘테이션 - 페이징
: 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 잘라서 할당하는 가상 메모리 관리 기법- 페이지 테이블 : 논리적으로는 페이지가 연속적으로 적재. 각각의 프레임을 가리킴.
- 페이지 크기에 따라 내부 단편화 발생 가능
- 페이지 테이블 베이스 레지스터(PTBR) : 각 프로세스의 페이지 테이블 적재 주소 가리킴
- TLB : 페이지 테이블의 캐시 메모리(페이지 테이블 일부 저장)
-> TLB 히트의 경우 메모리 접근 수 1번 - 쓰기 시 복사 : 부모와 자식 프로세스가 동일한 페이지 테이블을 사용하다가, 쓰기 작업 시에만 해당 페이지 복사 및 수정.
-> 메모리 공간 절약, 프로세스 생성 시간 절약 - 계층적 페이징(다단계 페이지 테이블)
- 요구 페이징 : 페이지가 필요할 때만 메모리에 적재
- 페이지 교체 알고리즘
- 페이지 폴트 횟수, 페이지 참조열 필요
- FIFO
- 2차 기회 페이지 교체 알고리즘
- 최적 페이지 교체 알고리즘(앞으로의 사용빈도 낮은 페이지를 교체)
- LRU 페이지 교체 알고리즘(지금까지의 사용빈도 낮은 페이지를 교체)
- 페이지 폴트 횟수, 페이지 참조열 필요
- 스레싱 : 빈번한 페이지 교체로 인해 CPU 이용률이 저하되는 문제
-> 프레임 할당 방식과 관련- 정적 할당 방식 : 균등 할당, 비례 할당
- 동적 할당 방식 : 작업 집합 모델(일정 시간동안 참조한 페이지 수), 페이지 폴트 빈도(상한선, 하한선)
Chapter 15. 파일 시스템
- 운영체제 내부의 파일 시스템(프로그램)이 파일과 디렉터리 관리
- 운영체제가 시스템 호출 제공
- 절대경로(루트부터), 상대경로(현재 위치부터)
- 파티셔닝(논리 영역 구획), 포매팅(파일 시스템 선정) : 보조기억장치 사용하기 위해 선행
- 파일 할당 방법(블록 단위)
- 연속 할당 : 외부 단편화
- 연결 할당 : FAT(파일 할당 테이블) 파일 시스템.
- 색인 할당 : 색인 블록(i-node) 이용. 유닉스 파일 시스템.
15개의 블록 -> 직접 블록, 이중 간접 블록, 삼중 간접 블록
- 저널링 파일 시스템
: 작업 도중 컴퓨터 강제 종료(시스템 크래시)에 의한 파일 훼손 방지 기법. 로그 이용 - 마운트
: 한 저장 장치의 파일 시스템과 다른 저장 장치의 파일 시스템 연결&접근 허용
