이전 프로세스 포스트들과 이어지는 포스트입니다. 이전 포스트는 여기와 여기를 참고하세요. 요약 IPC는 무엇인가요? IPC는 협력 프로세스 사이에서 다른 프로세스와 통신을 할 수 있게 하는 운영체제 모델입니다. 협력 프로세스는 정보 공유와 계산 속도 향상 등의 이유로 다른 프로세스와 통신을 해야 합니다. 하지만 프로세스는 기본적으로 ...

요약 프림 알고리즘은 그리디 알고리즘을 기본으로 하여 최소 신장 트리를 찾을 수 있는 알고리즘이다. 이 때까지 선택된 정점과 연결된 모든 간선들 중 가장 가중치가 작은 간선을 탐욕적으로 선택한다. 이 후 가장 가중치가 작은 간선의 다른 한 정점을 선택한 후 다시 이전의 과정을 반복한다. 두 정점이 모두 선택된 간선은 포함될 수 없다는 점을 기억하면 어...

요약 멀티 프로세스는 어떤 장점을 가지나요? 멀티 프로세스 환경은 여러 프로세스를 병렬로 수행할 수 있습니다. 자식 프로세스를 생성하여 부모 프로세스와 또 다른 프로세스를 생성합니다. 이 과정에서 부모 프로세스와 자식 프로세스는 분리된 자원을 사용하므로 독립성을 유지하고 모듈화할 수 있습니다. 하지만 프로세스 사이 통신 비용과 Context...

요약 위상 정렬에서 핵심은 진입차수이다. 진입차수가 0인 노드를 큐에 넣고 방문 처리한다. 큐에서 하나를 빼고 이와 연결된 주변 노드의 진입 차수를 1 감소시킨다. 다시 1, 2번 과정을 반복한다. 이러한 위상 정렬로 그래프에 사이클이 포함되어 있는지도 확인할 수 있다. 위상 정렬의 시간 복잡도는 O(V + E)이다. 서론 백준 1...

요약 프로세스는 무엇인가요? 프로세스는 프로그램이 실행되어 메모리에 적재된 상태입니다. 이러한 프로세스는 프로세스마다 독립된 메모리 영역을 가집니다. 메모리 영역을 Stack, Heap, Data, Text 영역으로 세분화할 수 있습니다. 프로세스에 관한 여러 정보는 PCB라는 객체가 가지고 있습니다. 프로세...

요약 System Call은 무엇인가요? System Call은 사용자 프로그램이 커널의 운영체제 서비스를 호출하기 위해 사용해야 하는 API입니다. System Call은 커널이 제공하는 운영체제의 서비스를 직접 사용자가 조작하는 일을 방지합니다. 이를 통해 사용자는 운영체제 서비스의 세부 구현을 알 필요 없고 운영체제 서비스를 안전하게 사...

요약 운영체제는 무엇인가요? 유저와 컴퓨터를 중개하는 프로그램으로 사용자는 운영체제로 컴퓨터를 편리하게, 효율적으로 사용할 수 있습니다. 유저와 하드웨어를 중개하기 위해 커널이라는 핵심 요소를 제공하고 있습니다. 그 외 사용자 편의를 위해 시스템 프로그램, 응용 프로그램, 미들웨어를 같이 제공합니다. 서론 운영체제가 어떤 종류가 있는지 대부...

요약 Knpasack Problem은 보통 배낭 문제로 불리며 여러 바리에이션이 존재한다. 대표적인 바리에이션인 분할 가능한 아이템을 사용한 배낭 문제는 그리디 알고리즘을 이용하여 해결할 수 있다. 하지만 분할 가능하지 않은 아이템을 사용할 경우 완전 탐색과 다이나믹 프로그래밍 중 시간 복잡도를 비교하여 선택할 수 있다. 다이나믹 프로그래밍에서 최적...

요약 LCS 문제는 두 수열의 최장 공통 부분 수열을 찾아야 한다. 이 문제는 최적화된 부분 문제를 가지고 있다. X와 Y 일부분(prefix)의 LCS를 찾은 결과는 X와 Y의 LCS를 찾을 때 재활용된다. 따라서 이는 다이나믹 프로그래밍으로 해결할 수 있다. LCS를 찾기 위해 브루트 포스를 사용하면 O(N2^N)의 시간 복잡도를 가지지만 다이나믹...

알고리즘 분류 : 자료 구조, 해시를 사용한 집합과 맵, 분리 집합 https://www.acmicpc.net/problem/4195 요약 기존의 유니온 파인드 알고리즘은 입력이 정수로 주어지는데 이번 문제는 문자열이 주어졌다. 평소 Map을 사용한 경험이 있다면 문자열을 어렵지 않게 정수로 변환할 수 있다. 문제에서 전체 사람 수가 주어지...