파일 시스템과 저장 장치 1) 파일과 저장 장치 파일 : 정보를 저장하고 관리하는 논리적 단위 컴퓨터 시스템 관점에서 정보를 저장하는 컨테이너 → 0과 1로 이루어진 데이터 덩어리로 영구 저장 장치나 일시 저장 장치에 저장 운영체제는 파일 생성, 기록, 읽기 모든 과정을 통제 2) 디스크 장치 #1 디스크 매체 정보가 저장되는 원형 판 : 플래터 플래터 한 면당 하나의 헤드를 가지며 플래터에서 정보를 읽고 저장하는 장치 #2 디스크 제어 모듈 프로세서 : 디스크 메체 모듈 제어, 물리적인 디스크 액세스 진행 디스크 캐시 : 호스트와 디스크 매체 모듈 사이의 중간 버퍼 역할 3) 섹터/트랙/실린더/블록 #1 섹터 디스크에 정보가 저장되는 최소 단위 #2 트랙 플래터에 정보가 저장되는 하나의 동심원 여러 개..
문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로..
물리 메모리의 한계 1) 주소 공간과 물리 메모리 컴퓨터에 설치할 수 있는 물리 메모리의 한계 → cpu 주소 버스에 따라 최대 물리 메모리 크기가 정해져 있음 → 현실적인 크기와 비용으로 인해 8~32GB의 메모리 사용 2) 물리 메모리의 한계 설치된 물리 메모리보다 큰 프로세스를 실행시킬 수 있는가? 프로세스들을 합친 크기가 설치된 물리 메모리보다 클 때 이들을 실행시킬 수 있는가? → 프로세스 전체가 물리 메모리에 적재 되어야 실행 가능한가? → 당장 실행에 필요한 프로세스의 일부 메모리만 적재한 채 실행시킬 수 없는가? 가상 메모리 개념 1) 가상 메모리 물리 메모리 크기 한계 극복 물리 메모리를 디스크 공간을 확장하는 기법 → 프로세스나 사용자가 프로세스를 실행하기에 충분히 큰 메모리가 있다고 ..
문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다. 케빈 베이..
데이터 압축 어떤 형태의 파일이라도 내부는 0과 1의 바이너리로 구성 이를 이용하여 적절한 알고리즘을 사용하면 크기를 줄일 수 있음 복원이 가능한 압축 → 비손실 압축 원래대로 복원 불가능한 압축 → 손실 압축 #1 비손실 압축 보관 및 이동에 용이하도록 파일 크기를 줄이는 데 사용 파일 사용을 위해서는 데이터의 무결성을 보장하여 해당 압축을 해제 대표적인 비손실 알고리즘 : Run-Length, Lempel-Ziv, Huffman → ZIP, RAR도 해당 알고리즘을 기반으로 압축을 적용한것 #2 손실 압축 압축률을 높이기 위해 파일에 의도적인 손상을 주는 압축 주로 멀티미디어 파일에서 사용하며 특성상 원본으로 되돌릴 수 없음 사람은 알아차리지 못하는 수준의 데이터 손상을 입힘 원본과는 분명히 차이가 ..
페이징 메모리 관리 1) 페이지와 프레임 프로세스의 주소 공간을 0번지부터 동일한 크기의 페이지로 나눔 물리 메모리 역시 페이지 크기로 나누어 프레임으로 부름 프로세스 구성 요소에 상관없이 고정 크기로 분할 페이지 크기는 운영체제마다 다르게 설정가능 페이지에 대응되는 프레임 번호를 저장하는 페이지 테이블 존재 2) 페이징 기법 프로세스 주소공간과 물리 메모리를 페이지 단위로 분할하고, 프로세스의 각 페이지를 물리 메모리의 프레임에 분산 할당하고 관리하는 기법 프로세스마다 페이지 테이블이 있으며 논리 주소의 물리 주소 변환은 MMU에 의해 이루어짐 물리 메모리의 빈 프레임 리스트 관리 필요 → 프레임 할당 알고리즘 내부 단편화가 발생하나 세그먼테이션보다 우수함 3) 페이징의 우수성 구현이 용이함 - 고정 ..
문제 입력 출력 첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다. 문제 풀이 해당 문제는 너비 우선 탐색으로 풀이를 진행한다 자세한 설명은 코드의 주석으로 설명 코드 #include #include using namespace std; const int MAX = 601; int M, N; // 가로 세로 bool visit[MAX][MAX]; // 방문여부 char input[MAX][MAX]; // 입력받는 문자 확인 int dy[] = { 1,-1,0,0 }; int dx[] = { 0,0,1,-1 }; int ans; // 만날 수 있는 사람의 숫자 queue q; void BFS() { while (!q.empty()) { int x = q..
문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 풀이 방법 0으로 시작하는 숫자가 있으며, ‘-’ 연산자를 만난 후의 모든 숫자를 뺀 값이 최소값이 ..
메모리 계층 구조와 메모리 핵심 관리 1) 메모리 계층 구조 메모리는 컴퓨터 시스템 여러 곳에 계층적으로 존재 cpu 레지스터 - cpu 캐시 - 메인 메모리 - 보조기억장치 보조기억장치로 갈수록 용량 증가, 가격 저렴, 속도 저하가 있음 메모리 계층화의 목적 : CPU의 메모리 엑세스 시간을 줄여 빠른 프로그램 실행 CPU 레지스터 L1/L2 캐시 L3 캐시 메인 메모리 보조기억장치 용도 몇 개의 명령과 데이터 저장 한 코어에서 실행되는 명령과 데이터 저장 멀티 코어에 의해 공유, 명령과 데이터 저장 실행 중인 전체 프로세스들의 코드와 입출력 중인 파일 블록 저장 파일이나 데이터베이스, 메모리에 적재된 프로세스의 코드와 데이터 일시 저장 용량 바이트 단위 KB 단위 MB 단위 GB 단위 TB 단위 타입..
문제 입출력 풀이 DFS - 깊이 우선 탐색 BFS - 너비 우선 탐색 #include #include using namespace std; int N, M, V; // 정점개수, 간선개수, 시작정점 int map[1001][1001]; // 인접 그래프 bool visited[1001]; // 방문 여부 queue q; void reset() { for (int i = 1; i > a >> b; map[a][b] = 1; map[b][a] = 1; } reset(); DFS(V); cout
내 블로그 - 관리자 홈 전환 |
Q
Q
|
---|---|
새 글 쓰기 |
W
W
|
글 수정 (권한 있는 경우) |
E
E
|
---|---|
댓글 영역으로 이동 |
C
C
|
이 페이지의 URL 복사 |
S
S
|
---|---|
맨 위로 이동 |
T
T
|
티스토리 홈 이동 |
H
H
|
단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.