제레미 베러미의 타임라인

최소 스패닝 트리란? 최소 스패닝 트리(Minimum spanning tree) 는 그래프 이론에서 자주 사용하는 개념이다. 최소 신장트리, MST라고도 부르는데 다 같은 말이다. 스패닝 트리 / 최소 스패닝 트리 '최소 스패닝 트리'를 살펴보기에 앞서, 먼저 '스패닝 트리'를 이해해보자. 스패닝 트리는 어떤 그래프에서 모든 정점을 포함하지만, 사이클이 발생하지 않는 트리다. 다음 그래프를 보면서 이해해보자. 위 그래프는 사이클이 있다. 1번, 2번, 3번 노드가 서로 사이클을 발생시킨다. 사이클을 없애면서 모든 노드를 포함하는 그래프는 다음과 같은 모양이 될 것이다. 위에 보이는 그래프들 모두 '스패닝 트리' 다. 사이클이 없고 모든 노드를 포함하기 때문이다. 이때 스패닝 트리의 '가중치'를 물어본다면..

ISA ISA는 Instruction Set Achitecture의 줄임이란 걸 밝히고 시작한다. 위 그림은 CPU의 종류중 하나인 MIPS의 ISA 예시이다. 솔직히 봐도 무슨 내용인지 정확히는 모르겠지만, Comments 부분을 주목해 읽어보니 Arithmetic(산술연산) 포맷, Transfer, Branch, Jump 등등이 눈에 띈다. 만약 C언어에서 덧셈을 하는 코드를 짰다면, 우선 그것이 어셈블리어의 add 명령어로 변환이 된다. 이때 add명령어는 산술연산(Arithmetic)에 해당하므로, 위 그림에서 R-format에 해당하는 Intruction이 관계될 것으로 추측할 수 있다. 시간측정 일반적으로 CPU 퍼포먼스를 측정할 때, 우리는 실행 시간을 기준으로 그것을 측정하게 된다. 또한 ..

C언어 과외 도중 실수 언더플로우에 대한 질문이 들어왔다. 질문을 살펴보기 전에, 혹시라도 이 글을 읽는 누군가를 위해 언더플로우에 대한 개념부터 먼저 간단히 정리하고 들어가려 한다. 언더플로우란, 메모리가 표현할 수 있는 범위보다 작은 수를 저장할 때 생기는 문제이다. 언더플로우는 두 가지 종류가 있는데, 바로 '정수 언더플로우'와 '실수 언더플로우'이다. 1) 정수 언더플로우 : 지정된 자료형의 범위보다 적은 숫자를 연산하려 할때 발생 ex) char형 변수의 표현범위는 (-128~127) 인데, -128에서 -1만큼 더 감소시키면 -129가 아닌 127이 된다. 2) 실수 언더플로우 : 실수를 아주 큰 수로 나누었을 때, 즉 0에 한없이 가까워질 정도로 아주 작은 수가 되었을 때 발생 ex) FLT..