Computer Science
-
리눅스 쉘은 어떻게 동작하는가 (brief explanation)Computer Science 2022. 11. 26. 21:53
Overview 개발하면서 자주 사용하게 되는 Shell 프로그램에는 Computer Science의 근간을 이루는 Process, Fork, I/O Redirection, File, Pipe, Signal 등의 중요한 개념들이 모두 포함되며, 이들의 논리적인 상호작용을 통해 사용자의 입력을 수행하고 결과를 출력합니다. 이들 각각의 요소와 Shell 프로그램의 코드를 하나씩 살펴보는 것은 하나의 포스팅에서 다 다루기 어려울 정도로 내용이 많기 때문에 이번 포스팅에서는 Shell 프로그램의 구체적인 구현 사항을 살펴보기보다는 Shell 프로그램이 동작하는 전반적인 그림에 대한 간략한 소개를 하려고 합니다. Shell을 이해하기 위해서는 앞서 언급했던 여러 Computer Science의 핵심 개념들을 이해..
-
[Process Synchronization] OverviewComputer Science/Operating System 2021. 4. 3. 16:29
Background 현대의 컴퓨터 프로세스들은 다중 코어, 다중 프로세스, 다중 스레드 방식 등을 통해 여러 명령들(instruction lines)이 병행하게, 혹은 병렬로 실행될 수 있습니다. 하나의 CPU에서 스케줄링 없이 각각의 프로세스를 sychronized 한 방식으로 처리한다면 아무런 문제가 없겠지만, 이러한 방식은 답답한 UX를 만들고, 프로그램의 성능을 떨어뜨리는 결과를 가져옵니다. (최신의 노트북은 적어도 4개~8개의 CPU 코어를 가지고 있습니다.) 이렇게 여러 개의 코어에서 여러 프로세스들이 스케줄되어 실행되기 때문에 현대의 컴퓨터는 우수한 성능을 낼 수 있지만, Process Scheduling, Shared Memory 등등 여러 가지 복잡한 사항들을 고려해야 합니다. 이번 포스..
-
[백준 2188 | 포드-풀커슨] 축사 배정Computer Science/Problem Solving (PS) 2020. 7. 8. 00:09
풀이 소와 축사와의 관계를 네트워크 그래프로 정의하는 것이 핵심이 되는 문제였습니다. 가장 많은 축사가 채워지는 것을 Source와 Dest간의 최대 유량을 결정하는 문제로 바꾸어주면 포드-풀커슨 알고리즘을 통해 이 문제를 쉽게 해결할 수 있습니다. 아래 그림과 같이 Source에서 모든 Cow로 가는 간선이 있다고 하겠습니다. (아래 그림에서의 모든 간선의 가중치는 1이 됩니다.) Cow는 선호하는 Cage로 간선을 그릴 수 있으며 Source로부터 들어오는 Cow의 유량은 1이 되므로 여러 Cage로 가는 간선이 있다고 해도 결국에는 하나의 Cage밖에 선택할 수 없게 됩니다. 모든 Cage는 각각 Dest로 가는 가중치 1짜리 간선이 있습니다. 이 그래프에 따르면 가장 많은 우리가 채워지는 경우 =..
-
[백준 6086 | 포드 풀커슨] 최대 유량Computer Science/Problem Solving (PS) 2020. 7. 7. 23:16
풀이 네트워크 유량과 관련된 기본적인 문제로, BFS를 사용하는 포드-풀커슨 알고리즘을 사용하여 구현하였습니다. 포드-풀커슨 알고리즘을 사용하여 이 문제를 해결 할 때의 주의점은, 파이프가 양쪽 모두로 물을 흘려보낼 수 있으므로, 파이프 하나를 양방향 간선으로 취급해야 한다는 점과, 동일한 파이프가 2개 이상 주어질 수 있다는 점입니다. 즉, A->B로 가는 용량 5짜리 파이프와 용량 2짜리 파이프가 동시에 입력될 수 있는데, 둘 중 어느 하나를 선택하는 것이 아니라 두 용량 모두를 더한 것이 A->B로 가는 파이프의 최종 용량이라는 것입니다. 소스 코드 (JAVA) import java.util.*; import java.io.*; /* @sckimynwa */ public class BOJ_6086 ..
-
최소 신장 트리 (MST)Computer Science/Algorithm 2020. 6. 27. 17:02
Overview 최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다. 이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 ..
-
[백준 1647 | MST] 도시 분할 계획Computer Science/Problem Solving (PS) 2020. 6. 27. 15:46
풀이 이전 포스팅에서 다루었던 최소 스패닝 트리 문제를 아주 간단하게 응용하여 풀 수 있는 문제입니다. 최소 스패닝 트리를 이전과 마찬가지로 구하고 나서, 최소 스패닝 트리를 잇는 가장 가중치가 큰 간선을 제외하면 가장 작은 비용으로 두 마을을 나누어줄 수 있습니다. 따라서 최소 스패닝 트리를 생성할 때에 추가되는 간선의 가중치 중, 가장 큰 값을 저장해두었다가 트리의 생성 비용에서 제거해주면 됩니다. 소스 코드(JAVA) import java.util.*; import java.io.*; public class Kruskal { public static int[] parent; public static ArrayList edgeList; public static void main(String[] arg..
-
[백준 1197 | MST] 최소 스패닝 트리Computer Science/Problem Solving (PS) 2020. 6. 27. 15:40
풀이 최소 스패닝 트리를 구하는 데에는 크게 2가지 알고리즘 (크루스칼 알고리즘, 프림 알고리즘)이 알려져 있습니다. 위 문제는 최소 스패닝 트리의 가중치 값을 묻는 기본적인 문제이기 때문에, 개인적으로 구현하기 편했던 크루스칼 알고리즘을 사용하였습니다. 크루스칼 알고리즘을 사용하기 위해서는 먼저 상호 배타적 집합 (Disjoint Set)을 먼저 구현해야 합니다. 크루스칼 알고리즘은 프림 알고리즘 과는 다르게, 간선을 가중치 순으로 먼저 정렬한 후에, 가중치가 작은 간선부터 이어 나가면서, 해당하는 간선의 두 정점이 이미 같은 트리에 속해 있는지를 판단해야 합니다. 예를 들어, 1과 2를 잇는 가중치 1인 간선을 추가하려고 할 때, 1과 2를 이어주는 경로가 이미 존재한다면 해당 간선을 추가해서는 안된..
-
[Network 용어] 스위치 스패닝 트리 프로토콜 (STP)Computer Science/Network 2020. 6. 25. 00:25
Overview 스위치(브릿지)에 관한 지난 포스팅 에서 스위치의 정의와 특징에 대해 살펴보았습니다. (스위치와 브릿지는 거의 같은 기능을 수행하므로 편의상 이 글에서는 스위치로 통일하겠습니다.) 스위치는 서로 다른 네트워크 장비들을 연결해주는 허브와 같은 기능을 합니다. 다만, 콜리전 도메인을 나누어 주지 못하는 허브와는 다르게 스위치는 서로 다른 네트워크 장비들의 콜리전 도메인을 나누어서, 서로 다른 포트에 연결된 네트워크들 끼리 딜레이 없이 통신이 가능하도록 도와줍니다. (스위치는 브로드캐스트 도메인은 나누어주지 못합니다. 이 기능은 라우터가 수행합니다.) Network Looping 스위치를 통해 네트워크를 설계할 때 가장 주의 해야 할 사항중의 하나가 바로 루핑(Looping)입니다. 루핑이란,..