CS

분리 집합 (Disjoint Set) / Union-Find

다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다." 이 메신저 프로그램을 통해 내가 A라는 사람과 친구 관계를 맺었다. 다음과 같은 관계도에서, 내가 주황색으로 표시된 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 위처럼 친구 관계를 그래프로 나타낸 후 나를 시작으로 그래프 탐색(DFS, BFS)을 통해 목표 정점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 새로운 친구 관계는 언제나 생겨날 수 있다. 만약 주황색으로 표시된 친구 관계가 새로 생겼다고 할 때, 우리는 주황색 사람과 친구 관계가 될 수 있는지 알기 위해서다시 그래프 탐색을 진행해야 한다. 하지만 이 메신저 프로그램을 사용하는 사용자의 수가..

최소 스패닝 트리 (MST) / 크루스칼 알고리즘 (Kruskal Algorithm)

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 크루스..

가중치 그래프와 임계 경로(Critical Path)

가중치 그래프 Weighted Graph 숫자로 된 가중치를 각 간선에 부여하여 가중치 그래프(weighted graph)로 확장할 수 있다. 이는 비가중치 그래프를 일반화한 것인데, 비가중치 그래프는 모든 간선의 가중치가 동일해서 생략한 가중치 그래프이고 더 많은 정보를 표현할 수 있어서 유용하다. 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 여행하는데 걸리는 시간일 수 있다. 가중치 그래프는 비가중치 그래프와 유사하게 표현할 수 있다. 인접 행렬로 나타낸다면, 가중치 그래프의 인접 행렬은 엔트리로 간선들의 가중치를 갖거나 연결되지 않은 엔트리들에 대해서는 특수한 값을 갖는다. 아래는 위 그래프를 인접행렬로 표현한 것이다. 이 인접행렬에서는 연결된 간선이 없을 때는 특수 값으로 \i..

CPU 캐시의 원리 (캐시 라인과 태그)

프로세서가 빈번하게 사용하는 데이터를 빠르게 추출하기 위한 '캐시 라인' 이라는 데이터 단위라고 불리며 데이터 저장구조로는 대표적으로 몇 가지 있다. Full Associative 방식 Set Associative 방식 Direct Map 방식 캐시 라인과 태그 프로세서는 다양한 주소에 있는 데이터를 사용하므로 일반적으로 빈번하게 사용하는 데이터의 주소는 여기저기 흩어져 있어서 캐시에 저장하는 데이터에는 해당 데이터의 메모리 주소 등을 쓴 태그를 달아놓을 필요가 있다. 그리고 메모리로부터 가져오는 데이터 묶음(단위)을 캐시 라인이라고 한다. 태그의 크기, 캐시 라인의 크기 캐시 라인에 붙이는 태그는 32비트 주소 공간을 갖는 프로세서는 32비트, 64비트 주소 공간을 갖는 프로세서는 64비트 정도의 크기..

CPU 프로세서 CISC / RISC 차이

1.CISC (Complex Instruction Set Computer) *Complex 복잡한, 복합체의 CISC는 필요한 모든 명령어 셋을 갖추도록 설계된 마이크로프로세서에 관련되는 용어로서, 요구되는 능력을 가장 효율적인 방법으로 제공했었다. 이름에서 알 수 있듯이 컴퓨터에 주어진 CISC 명령은 매우 작기 때문에, 그 당시 메모리 부족의 문제점을 보완할 수 있었다. 그러나 그 후, instruction set 자체를 가장 자주 사용되는 명령어만으로 개수를 줄임으로써 대부분의 활용업무 면에서 소요되는 시간을 줄일 수 있는 방법이 고안되었는데, 이것을 RISC라고 불렀다. 그러다 보니, 이러한 RISC 프로세서와 모든 명령어 셋을 갖추고 있는 컴퓨터를 구별할 수 있는 말이 필요하게 되었는데, 그래서..

CPU 그리고 캐시 메모리

cpu의 퍼포먼스는 다음으로 결정된다. 코어 수 클럭 속도 캐시 메모리 프로세서 타입 (따로 글로 빼둠) 코어 cpu는 하나 또는 그 이상의 프로세서를 가질 수가 있다. 내부 논리 구조는 아래와 같다. 컴퓨터 메모리에 담겨있는 프로그램을 실행하라는 입력이 들어와서 프로그램이 실행되는 순서는 입력 - CU(컨트롤유닛)가 메모리에 프로그램 데이터를 호출 메모리에서 레지스터로 자료가 이동 ALU(산술연산장치)에서 프로그램을 계산 또는 해독 출력 CU (Control Unit) 명령 제어장치 입력된 명령어를 해독하여 cpu 내부의 움직임을 총괄하고 각 과정을 통제한다. 주로 데이터를 메모리로부터 ALU로 옮기라는 명령과 그 후 다시 메모리로 옮기는 명령을 내린다. CU의 명령에 의한 명령 처리 과정 캐시나 파이..

64bit OS에서 C++과 C# 데이터 차이 비교

CTS C++ C# Size(byte) System.Byte unsigned char byte 1 System.SByte signed char sbyte 1 System.Int16 short short 2 System.UInt16 unsigned short ushort 2 System.Int32 int int 4 System.Int64 long, long long long 8 System.Single float float 4 System.Char wchar_t char 2 System.Double double double 8 System.UInt64 size_t ulong 8 System.IntPtr void * (pointer) IntPtr 8 출처 : https://dragontory.tistory...

C++ vector empty()와 size()간 차이

vector::empty() 벡터가 비어있는지 확인하는 함수이다. Input : myvector = 1, 2, 3, 4, 5 myvector.empty(); Output : False Input : myvector = {} myvector.empty(); Output : True 시간 복잡도 : O(1) #include #include using namespace std; int main() { vector myvector{}; if (myvector.empty()) { cout

C++ vector사용법 및 설명 (장&단점)

vector vect; // vect는 stack, 각 원소들은 heap vector *vect = new vector; // vect와 각 원소들 모두 heap vector vect; // vect는 stack, 각 원소들은 heap 그리고 가리키는 대상들은 heap 또는 stack https://stackoverflow.com/questions/8036474/when-vectors-are-allocated-do-they-use-memory-on-the-heap-or-the-stack 속도적인 측면에서 array(배열)에 비해 성능은 떨어지지만 메모리를 효율적으로 관리하고 예외처리가 쉽다는 장점이 있다. Vector의 초기화 vector 변수명 백터 생성 vector 변수명(숫자) 숫자만큼 백터 생성 ..

CPU 32비트 64비트와 두 프로그램의 차이

CPU 32비트와 64비트 차이 컴퓨터에는 32비트, 64비트 두 가지 유형의 프로세서가 존재한다. 이것은 컴퓨터 프로세서가 CPU 레지스터에 전달할 수 있는 메모리의 양이다. 즉 32비트보다 64비트 프로세서가 데이터 처리량이 높기 때문에 더 우수한 성능을 보여준다. 32비트 232개의 메모리 주소, 즉 4GB((4,294,967,296바이트) 정도의 물리 메모리(RAM)에 전달할 수 있다. 64비트 264개의 메모리 주소, 실제로 18GB (18,446,744,073,709,551,616)바이트 또는 17,179,869,184GB(16EB) 정도의 물리 메모리(RAM)에 전달할 수 있다. 듀얼 코어, 쿼드 코어, 6 코어, 8 코어 버전의 홈 컴퓨팅으로 제공될 수 있다. 속도 향상. 멀티태스킹에서 많..