개발자 모드

오늘은 정렬방법 중, 위상정렬에 대해서 알아보겠습니다. 위상정렬 위상 정렬(Topological Sort)는 사이클이 없는 방향 그래프에서 정점을 선형 순서로 나열하는 것입니다. 여기서 선형 순서란 일렬로 줄 세우는 것이라고 봐도 되겠습니다. 위상정렬 예제 그럼 위상정렬에 대해서 알아보기 전에!! 왜 위상정렬을 사용하는지, 어떤 경우에 사용하는지에 대해서 알아봅시다. 위와 같은 교과목 체계도가 있다고 해봅시다. 화살표는 선수과목을 의미합니다. 가령, 자료구조는 알고리즘의 선수과목인 것처럼 말이죠. 그런데 여기서 제가 어떤 순서로 들어야할지, 특정 과목부터 시작한다고 하면 무엇을 들을 수 있는지를 위상정렬을 통해서 알아볼 수 있습니다. 만약 위 교과목 체계도에서 위상정렬을 사용한다면, 많은 결과 중 아래와..

이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해서 다뤄보겠습니다. BFS란? BFS는 Breath-First Search의 줄임말로, 하나의 정점에서 시작하여 해당 정점과 이웃한 모든 정점을 방문한 뒤, 방문한 정점들의 이웃 정점을 방문하는 방식을 의미합니다. BFS의 탐색 순서를 아래의 그림을 통해 쉽게 확인하실 수 있습니다. BFS의 구현 BFS를 자바로 구현해보겠습니다. import java.util.*; public class Edge{ // 각 노드를 정의 int adjvertex; public Edge(int v){ adjvertex = v; } } public class BFS{ int N; List[] graph; private boolean[] visited; public ..

오늘은 이전 글에서 다룬 그래프에 대한 연장선으로 그래프에서 모든 정점을 탐색하는 방법 중 DFS를 다뤄보겠습니다. DFS란? DFS는 Depth-First Search의 줄임말로, 깊이를 우선으로 하여 탐색하는 방식을 의미합니다. 하나의 정점으로 시작하여, 그 정점과 이웃한 정점 중 하나를 방문합니다. 방금 방문한 정점에서 다시 이웃한 정점을 확인하고, 이웃한 정점들 중 하나를 방문합니다. 이와 같이 진행하는 방식을 DFS라고 합니다. 아래의 그림으로 확인해봅시다. 위와 같은 그래프가 있다고 가정해봅시다.(사실은 트리라고도 볼 수 있습니다.) 위 트리에서 가장 상위의 정점을 시작으로 DFS를 진행한다면 정점 내에 쓰여진 숫자 순서대로 방문합니다. DFS의 구현 자바로 구현한 DFS를 확인해보겠습니다. ..

오늘은 이전 글에서 다룬 semaphore를 어떻게 활용하는 지에 대해서 조금 더 자세히 알아보겠습니다. Semaphore는 기본적인 critical section problem을 해결하는데 사용됩니다. 이전 글에서 언급했지만, 한 번 더 확인해봅시다. 우리에게 익숙한 Producer, Consumer 문제를 예로 들어보겠습니다. semaphore counter = 0; final int BUFFER_SIZE = 10; semaphore empty = BUFFER_SIZE; semaphore mut_ex = 1; void producer(){ while(true){ produce(); semWait(empty); semWait(mutex); append(); semSignal(mut_ex); semSig..

오늘은 critical section problem을 해결할 수 있는 HW support 방법 중 하나인 Semaphore에 대해서 알아봅시다. Semaphore semaphore는 이전 글에서 소개드린 testset의 단점인 busy waiting을 해결하고, bounded waiting 또한 깔끔하게 해결할 수 있는 방식입니다. testset과 마찬가지로, semaphore도 atomic operation을 이용하여 critical section problem을 해결합니다. Semaphore는 하나의 정수와, 큐를 갖는 구조를 의미합니다. 이들의 쓰임은 아래에서 확인합시다. Semaphore에서는 특별한 함수 semWait(s)과 semSignal(s)을 사용합니다. semWait(s)은 semaph..

이번 글에서는 critical section problem을 해결하는 방법 중에서 testset을 이용한 방법을 다뤄보겠습니다. 하드웨어의 도움으로 critical seciton problem을 해결하기 위해 우리는 atomic operation을 활용할 것입니다. 그런데 뭔가 이상하지 않나요?? 우리가 이전 글에서 SW Solution으로 해결하기 위해 critical section을 atomic operation으로 정의해서 진행했더니, critical section을 진행하는 도중에는 interrupt를 받을 수 없으므로 옳지 못하다고 다뤘으니까요. 그래서 여기서는 하드웨어의 지원을 받아서, critical section이 아닌 entry section과 exit section을 atomic ope..

오늘은 어셈블리 언어로 다룬 프로그램 중, Subroutines와 I/O Programming에 대해서 살펴봅시다. Subroutines 우리는 계속 반복되는 작업들을 subroutine으로 둬서, 사용하기 편하게 합니다. 아래는 left shift를 4번하는 연산 즉, AC의 값에 16을 곱하는 연산이 되겠습니다. 이러한 식으로 subroutines를 돌고 나올 수 있습니다. X는 16진수로 1234이기 때문에 CIL을 4번 해주면 4비트 즉, 1바이트가 옮겨지므로 2340이 되고 같은 원리로 Y도 3210이 됨을 알 수 있습니다. I/O Programming 과거 컴퓨터는 I/O의 기능을 수행하기 위해 매번 CPU가 디바이스 장치에 대해서 확인을 하는 방식을 이용했습니다. 하지만, 이 방식은 너무 비..

오늘은 어셈블리 언어로 작성된 프로그램들을 살펴봅시다. 그 중에서 오늘은 Loops, Multiplication, Arithmetic, Logic operation에 대해서 다뤄봅니다. Program Loops 우리는 보통 같은 작업이지만 데이터가 다른 것들을 반복할 때, loop를 사용합니다. 그러면, 우리는 어셈블리 언어로 어떻게 작성할까요?? 아래의 예시를 보시죠. int[] A = new int[]; int sum = 0; for(int i=0; i

오늘은 어셈블러에 대해서 알아보겠습니다!!! Assembler 어셈블러는 어셈블리 코드를 목적코드로 변환하는 것을 의미합니다. 실제로, 저번에 보았던 어셈블리 언어의 예시를 다시 기억해봅시다. 이 어셈블리 언어를 목적코드로 바꾸면 아래와 같은 형태로 변환하게 됩니다. 사실 어셈블러는, 이러한 것을 바꾸는데 아스키 표를 이용합니다. 아마 어떠한 프로그래밍 언어를 공부하더라도 어느정도 들어봤을 친숙한 이름이라고 생각합니다. 저희는 지금 16비트 컴퓨터를 설계하고 있습니다. 따라서, 8비트로 표시되는 아스키값을 총 3개로 사용할 수 있습니다. 왜냐하면 맨 앞의 4비트로는 MRI인지 non-MRI인지를 확인해야하기 때문이죠. 여기서 보면, INC와 같은 opcode는 AC의 값을 increment하는 것이므로,..

오늘은 어셈블리 언어에 대해서 배워보겠습니다. Assembly Language 어셈블리 언어는 저급 언어에 속합니다. 즉, 파이썬같이 인간이 알 수 있는 고급언어와 다르게 기계가 알 수 있도록 쓰이는 언어를 의미합니다. 어셈블리 언어는 3가지 filed로 구성됩니다. label field : 비어있거나, symbolic address를 나타냅니다. Symbolic Address는 아래에서 다룹니다. Instruction field : machine instruction이나 pseudo instruction을 나타냅니다. Comment filed : 공란이거나 주석을 작성합니다. 이 세가지 filed를 알아보기 전, Symbolic Address에 대해서 알아봅시다. Symbolic Address는 마치 ..