Union-Find Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다! 구현 1. 초기화 다음과 같이 모든 값이 자기 자신을 가리키도록 초기화해준다! 모든 값이 자기 집합의 대표값?이 되는 것이다. 처음에는 각 집합의 원소가 하나니까 어찌보면 당연한 일이다. int root[1000001]; for(int i=1; i>n>>m; for(int i=0; ioper>>a>>b; if(oper == 0) union_(a, b); else if(find_(a)==find_(b)) cout

스케줄링 OS는 CPU 등의 자원을 프로세스에 적절히 배정함으로써 시스템의 성능을 개선할 수 있음 프로세스가 작업을 수행하려면 스케줄러로부터 cpu를 할당 받아야 함 프로세스 실행 = (CPU 실행 + I/O 대기) 의 사이클 = CPU - I/O Burst Cycle CPU Scheduling = CPU 를 잘 사용하기 위해 프로세스를 잘 배정하기 ! 프로세스를 스케줄링하기 위한 Queue 프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재함 Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합 Device Queue : Device I/O 작업을 대기하고 있는 프로세스의..

메모리 구조 코드 영역: 실행할 프로그램의 코드 데이터 영역: 전역 변수, 정적 변수 (프로그램 시작과 동시에 할당, 프로그램이 종료되어야 소멸) 힙 영역: 사용자의 동적 할당 스택 영역: 지역 변수, 매개 변수 (함수 호출 시 ! 함수 호출이 완료되면 사라짐) 프로세스 (Process) : 메모리에 올라와 실행되고 있는 프로그램 (OS는 모든 프로그램을 프로세스 형태로 실행함) OS로 부터 독립된 영역을 할당 받음 (통신을 위해서는 IPC: Inter-Process Communication 사용) 프로세스는 최소 한개의 쓰레드 (메인 쓰레드)를 가짐 new(생성), running(실행), waiting(I/O, event wait, waiting-> ready), ready(by interrupt), ..

운영체제 (Operating System) : 하드웨어를 관리하고, 컴퓨터 시스템의 자원들을 효율적으로 관리하며, 응용 프로그램과 하드웨어 간의 인터페이스로써 다른 응용 프로그램이 유용한 작업을 할 수 있도록 환경을 제공하는 프로그램 운영체제의 역할 1. 프로세스 관리 2. 저장장치 관리 1차 저장장치(Main Memory) 프로세스에 할당하는 메모리 영역의 할당과 해제 메인 메모리의 효율적 활용을 위한 가상 메모리 기능 2차 저장장치(HDD, NAND Flash Memory 등) 파일 형식의 데이터 저장 파일 데이터 관리를 위한 파일 시스템을 OS에서 관리 ( FAT, NTFS, EXT2, JFS, XFS 등 ) 3. 네트워킹 : 응용 프로그램이 네트워크를 사용하려면 운영체제에서 네트워크 프로토콜을 지..