전체 글94 [백준/C++] #2146 다리 만들기 (Flood Fill / BFS) 문제https://www.acmicpc.net/problem/2146 알고리즘: BFS 이용한 Flood Fill 알고리즘은 쉬웠는데, 조건 때문에 조금 헤매어서 시간이 걸렸다.ㅠbfs를 섬에 번호 매길때 한번, 섬들 간 최단 거리 구할 때 한번 사용했다. 다음에는 dfs로도 풀어봐야겠다. 그리고 fill, memset 초기화 함수에 대해서도 잘 알아두자!! 코드 + 풀이1. 섬 찾아 섬을 이루는 땅들에 동일한 번호 붙이기 -> findLand() 2. 섬들간의 최단 거리 구하기 -> bfs()#include #include #include #include #define MAX 101#define INF 987654321// 2146/*섬과 섬을 잇는 짧은 다리 지도가 주어질 때, "가장 짧은 다리 .. 2024. 7. 2. [OS] NachOs 환경 세팅, 실행 0. NachOS란?"Not Another Completely Heuristic Operating System"의 약자로, 운영 체제의 원리와 동작을 이해하고 실제로 구현해 볼 수 있도록 하는 데에 사용됨. 1. Visual Box → 가상 환경 세팅https://www.virtualbox.org/wiki/Downloads Downloads – Oracle VM VirtualBoxDownload VirtualBox Here you will find links to VirtualBox binaries and its source code. VirtualBox binaries By downloading, you agree to the terms and conditions of the respective lic.. 2024. 7. 2. [OS] Disk 구조 구성 요소Spindle: 디스크 플래터(Platter)를 고정하고 회전시키는 축이다. 모든 플래터는 스핀들에 의해 동일한 속도로 회전한다.Platter: 자성 물질로 코팅된 원판 형태의 디스크이다. 디스크 드라이브에는 여러 개의 플래터가 수직으로 쌓여 있을 수 있다.Read/Write Head: 데이터를 읽고 쓰는 장치이다. 각 플래터의 양면에 하나씩 붙어 있으며, 헤드는 플래터 표면 위를 이동하면서 데이터를 액세스한다.Arm: Read/Write Head를 움직이는 기계 장치이다. 헤드가 트랙을 따라 이동할 수 있도록 돕는다.Cylinder: 같은 반지름을 갖는 모든 플래터의 트랙들의 집합이다. 이는 여러 플래터가 같은 위치에 있는 트랙을 논리적으로 묶은 개념이다.디스크 구조Track: 플래터의 .. 2024. 7. 1. [OS] File System File파일은 저장의 논리적 단위로, 바이트(Byte)의 집합을 의미한다. 운영 체제(OS) 관점에서 파일은 데이터를 저장하고 관리하는 기본 단위이다. 파일은 텍스트, 이미지, 실행 가능한 프로그램 등 다양한 형태로 존재할 수 있으며, 이러한 파일들을 체계적으로 관리하기 위해 디렉토리 구조가 사용된다.하드웨어적 관점에서는 블록(Block)이라는 최소 단위가 존재하며, 이는 디스크의 섹터(Sector)와 트랙(Track)으로 나눈 부분을 의미한다. 파일 시스템은 이러한 블록을 이용해 데이터를 효율적으로 저장하고 관리한다. 사용자 관점에서 파일 시스템의 지속성(Persistence), 사용 편의성(Ease of Use), 효율성(Efficiency), 속도(Speed), 보호(Protection)가 중요하다.. 2024. 7. 1. [OS] Memory Management Segmentation*Segment: 프로세스의 메모리를 논리적으로 나눈 단위 세그멘테이션은 프로세스를 여러 세그먼트 또는 파티션으로 나누는 메모리 관리 기법이다. 각 세그먼트는 Code(read only), Data, Bss, Stack과 같은 프로그램의 다른 부분을 나타내며, 크기가 다를 수 있다. 이 기법은 세그먼트를 비연속적으로 물리 메모리에 할당할 수 있어 연속적인 메모리 할당의 필요성을 줄인다. 다만, 각 세그먼트 내부는 연속적으로 할당되어야 한다. 세그멘테이션의 주요 장점 중 하나는 가변 크기 세그먼트를 사용하여 내부 단편화를 줄일 수 있다는 점이다. 이는 세그먼트가 동적으로 성장하거나 축소될 수 있어 내부 단편화를 최소화할 수 있음을 의미한다. 또한, 세그멘테이션은 각 세그먼트를 독립적으.. 2024. 7. 1. [OS] Program -> Process 프로그램이 실제로 실행되기 위해서는 프로세스로 변환되어야 하는데, 이는 프로그램이 단순히 저장 장치에 저장된 코드와 데이터의 정적인 형태에서 벗어나, 운영 체제가 관리할 수 있는 동적인 실행 단위로 활성화되어야 하기 때문이다. 이 과정을 자세히 살펴보면 다음과 같다. [프로그램 vs 프로세스]프로그램(Program): 디스크와 같은 저장 매체에 저장된 실행 가능한 파일로, 코드와 데이터의 정적인 형태를 가지며, 실행되지 않는 상태이다.프로세스(Process): 실행 중인 프로그램으로, 운영 체제가 메모리에 할당하고 실행을 관리하는 동적인 상태이다. 프로세스는 메모리, 실행 상태, 프로세스 ID 등 실행에 필요한 여러 자원과 정보를 포함한다. [프로세스 생성 과정]1. 프로그램의 로딩컴파일 → 어셈블 → .. 2024. 7. 1. [OS] Deadlock TerminologyDeadlock은 두 개 이상의 프로세스가 서로의 자원을 필요로 하면서 상대방의 작업 완료를 무한정 기다리는 현상이다. 이 상황에서 각 프로세스는 상대방이 필요로 하는 특정 이벤트를 제공할 수 있는데, 모든 관련 프로세스가 서로의 이벤트를 기다리면서 어느 쪽도 진행할 수 없게 되어 결국 모두 정지하게 된다.Deadlock의 필요조건에는 4가지가 있다.상호 배제 (Mutual Exclusion): 요구하는 자원이 다른 프로세스에 의해 사용 중일 경우, 해당 자원이 방출될 때까지 기다려야 한다.보유 대기 (Hold-and-Wait): 프로세스가 최소 하나 이상의 자원을 보유한 상태에서 추가 자원을 획득하기 위해 대기할 수 있다.비선점 (No Preemption): 다른 프로세스나 운영체제.. 2024. 7. 1. [OS] CPU Scheduling TerminologyCPU Scheduling은 운영체제가 시스템의 여러 프로세스들 사이에서 CPU 자원을 효율적으로 분배하기 위해 사용하는 메커니즘이다. 이는 여러 프로세스가 동시에 실행되고자 할 때, 어떤 프로세스가 CPU를 사용할지를 결정하는 과정이다. 왜 필요한가? (Policy) 실행 중인 프로세스는 CPU burst와 I/O burst를 무한히 반복한다. I/O burst로 이동할 때에는 context switch한 후 이동하는데, I/O burst가 얼마나 길어질지 모르기 때문이다. Context switch가 발생하기 이전에 운영체제는 미리 scheduler를 통해 ready queue에 있는 프로세스 중에서 다음에 실행할 프로세스를 선택한다. 어떤 기준으로 결정된 프로세스를 얼마나 길게 .. 2024. 7. 1. [OS] Synchronization TerminologySynchronization = 동기화 (≠ 병렬): 멀티스레드 환경에서 공유 데이터에 접근할 때 발생하는 문제를 해결하기 위한 메커니즘으로, atomic (indivisible) operation을 사용하여 쓰레드 간의 협력을 보장한다.왜 필요한가? (Policy)OS의 최종 목적은 Multiprogramming이다. 이를 통해 하드웨어 리소스를 최대한 효율적으로 사용함으로써 사용자가 무한대의 자원을 사용하고 있다고 느끼게끔 돕는다. 그러면 더욱이 처리 속도를 높이기 위해 동시에 여러 작업을 실행할 수 있도록 작업이 완료되기 전에 다른 작업을 수행할 수 있도록 비동기 처리하여야하는게 아닐까? 생각이 든다. 아주 타당한 생각이다. 다만, 동기화를 수행해야 하는 특수한 상황이 존재한다.. 2024. 7. 1. [백준/C++] #1168 요세푸스 문제 2 (Segment Tree) 문제https://www.acmicpc.net/problem/1158: 큐를 이용여 풀리는 가장 기본적인 요세푸스 문제 https://www.acmicpc.net/problem/1168: 세그먼트 트리를 이용하여 시간복잡도를 줄여야 하는 요세푸스 문제개념: Segment Tree 코드 + 풀이1. 큐를 이용한 풀이 (1158번): 특정 "번째"의 사람이 올 때까지 큐의 원소를 push, pop 반복한다. #include#includeusing namespace std;int n, k;queueq;int main(void){ int i; cin >> n >> k; for (i = 1; i "; return 0;} 2. 세그먼트 트리 이용한 풀이 (1168번): 요세푸스 문제의 핵심은 몇 번째에 있는 사람을.. 2024. 7. 1. 이전 1 ··· 5 6 7 8 다음
