봉황대 in CS

최소 신장 트리 (Minimum Spanning Tree, MST) 최소 신장 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중, 그 가중치의 합이 최소인 트리를 말한다. * 부분 그래프(Subgraph) : 주어진 그래프에서 일부 정점과 간선만을 선택하여 구성한 그래프 더 쉽게 말하자면 가장 적은 비용으로 모든 노드를 연결한 그래프를 말하며, 이때 사이클이 발생하면 안 된다. * 정점 = 노드 * 간선 = 비용 = 가중치 (그래프에서 선에 해당하는 부분) 동일한 그래프에서 최소 신장 트리는 여러 개가 나올 수 있다. 가중치의 합이 최소이기만 하면 되기 때문이다. 최소 신장 트리를 구하기 위한 알고리즘은 2가지가 존재하며, 각각 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이다...

최소 신장 트리(Minimum Spanning Tree, MST)에 대해서 찾아보다가 이를 구현하는 두 가지 방법 중 크루스칼(Kruskal) 알고리즘의 기본 베이스가 Union-Find 임을 보고, 먼저 Union-Find에 대해서 공부한 후 정리해보고자 한다. Union-Find Union-Find 알고리즘은 여러 개의 노드가 존재할 때 두 개의 노드를 선택한 후, 현재 이 두 노드가 서로 같은 그래프에 속하는지를 판별하는 알고리즘이다. Disjoint Set Disjoint Set(분리 집합)은 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조인데, 이 Disjoint Set을 표현할 때 사용하는 알고리즘이 바로 Union-Find 알고리즘이다. 이 알고리즘은 전체 집합..

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다. 1장에서 컴퓨터 성능은 명령어의 개수, Clock Cycle Time, CPI(명령어 당 Clock Cycle 수)에 의해 결정된다는 것을 알았다. 2장에서는 컴파일러와 명령어 집합 구조(ISA)가 프로그램에 필요한 명령어 개수를 결정하는 것을 배웠다. 하지만 Clock Cycle Time과 CPI는 프로세서의 구현 방법에 따라 결정이 된다. 본 4장에서는 프로세서를 구현하는 데 사용되는 원리와..

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다. 본서에서는 '오류'와 '함정'이라는 단어를 사용하는데, 각각의 의미는 다음과 같다. 오류(Fallacy) : 많은 사람들이 공통적으로 잘못 알고 있는 부분 함정(Pitfall) : 흔히들 저지르기 쉬운 실수 [ 오류 ] 한 비트 왼쪽 자리이동 명령어가 2를 곱해준 것과 같은 결과를 보이듯이 오른쪽 자리이동 명령어는 2로 나누어 준 것과 같은 결과를 나타낸다. 부호 없는 정수(unsigned in..

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다. 부동소수점 덧셈 부동소수점으로 표현된 수들의 덧셈은 어떻게 진행되는지 알아보자. 1. F1과 F2의 hidden bit을 복구시킨다. ex) F1이 011000...000이라면 원래 수는 1.011이다. (hidden bit = 1) 2. E1과 E2의 자릿수를 맞춰준다. * 자릿수를 맞추는 방법 (1) E1과 E2 중에 큰 것을 고른다. E1 > E2라고 가정하자. (2) E1 - E2 만큼 ..

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다. IEEE 754에는 4가지 자리맞춤 모드(rounding modes)가 있다. 1. Always round up (항상 자리올림) (+∞ 방향) 2. Always round down (항상 자리내림) (-∞ 방향) 3. Truncate (잘라내기) 4. Round to nearest even (가장 가까운 짝수로의 자리맞춤) (반올림) 이러한 자리맞춤 모드들이 존재하는 이유는 아래와 그림과 같이..

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다. 프로그래밍 언어는 부호있는 정수와 부호없는 정수뿐만 아니라 소수 부분을 갖는 수, 실수(reals)도 표현할 수 있어야 하고, 엄청나게 큰 값도 표현할 수 있어야 한다. 이 수들은 32비트 부호있는 정수로는 표현할 수 없다. 과학적 표기법과 정규화된 수, 부동소수점 우선 과학적 표기법과 정규화된 수에 대하여 알아보자. 과학적 표기법(scientific notation)은 소수점의 왼쪽에는 한 자..

배낭 문제 (Knapsack Problem) 배낭 문제란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭 문제에는 2가지 경우가 있다. 1. 분할 가능 배낭 문제 (Fractional Knapsack Problem) - 짐을 쪼갤 수 있는 경우 2. 0-1 배낭 문제 (0-1 Knapsack Problem) - 짐을 쪼갤 수 없는 경우 짐을 쪼갤 수 있는 경우에는 그리디 알고리즘을 통해 해결할 수 있다. (가치가 가장 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식) 짐을 쪼갤 수 없는 경우에는 동적 계획법(Dynamic Programming, DP)을 통해 해결할 수 있다. 브..