Dijkstra 알고리즘 최단 경로(Shortest Path) 찾기는 주어진 가중치 그래프에서 출발점에서 도착점까지의 최단 경로를 찾는 알고리즘이다. 이 최단 경로를 찾는 알고리즘 중 많이 사용하는 것이 바로 Dijkstra 알고리즘이다. Dijkstra 알고리즘은 출발점에서 각 정점까지의 최단 거리 및 경로를 구하는 알고리즘으로 이전에 배웠던 Prim의 MST 알고리즘과 유사하다. 어떤 점이 차이가 있냐하면, Prim 알고리즘은 임의의 점에서부터 시작을 하지만, Dijkstra 알고리즘은 출발 지점이 있다. 또한 Prim 알고리즘에서는 배열 D에 간선의 가중치를 저장했지만, Dijkstra 알고리즘은 배열 D에 출발점에서 각 정점까지의 거리를 저장한다. Prim 알고리즘에 관해 궁금하다면, 아래 포스팅..
최소 신장 트리(Minimum Spanning Tree, MST)이란? 최소 신장 트리를 배우기 앞서, 신장 트리란 무엇인지 알아야 한다. 이는 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분집합으로 구성된다. 신장 트리의 중요한 특징 중 하나는 모든 노드가 적어도 하나의 간선과 정점에 연결되어야 하며, 사이클을 만들면 안된다. 최소 신장 트리를 이해하기 위해서는 이러한 신정트리의 개념을 정확히 파악하고 있어야 한다. 아래와 같은 그래프가 신장 트리의 예시 중 하나이다. 최소 신장 트리는 하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장트리를 말한다. 이러한 최소 신장 트리 알고리즘은 대표적으로 Kruskal, Prim, Sollin 알고리즘이 있다. 이는 ..
강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..
이중 연결 성분(Biconnect Component)란? 이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다. 이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다. 즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다. 아래 예시와 함께 그 의미를 한 번 더 살펴보자. 위 그래프는 지금까지..
* 이 글은 알고리즘에 관해 학습하며 정리한 글입니다. 틀린 점이나, 고쳐야 할 부분이 있으면 알려주세요..! 위상 정렬이란? 위상 정렬이란(Topological Sort) : 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서로 나열하는 것이다. 이때 DAG, 즉 사이클이 없는 방향 그래프란 주로 노드들 간에 우선순위를 나타내기 위해서 사용한다. 만약 노드들간에 사이클이 존재한다면, DAG라고 볼 수 없다. 즉, 우선 순위가 존재하는 노드들 간에 순서를 나타낸 것인데, 만약 우선순위가 동일하다면 그 중 임의의 하나를 선택한다. 그래서 위상 정렬은 여러 값이 나올 수 있다. 일반적으로 위상 정렬을 사용하는 때는 의존 관계가 존재할 때, 수행 가능한 작업 순서..
* 이 글은 컴퓨터 구조에 관해 학습하며 정리한 글입니다. 틀린 점이나, 고쳐야 할 부분이 있으면 알려주세요..! Multiplication Program 이전에 알아야 할 것 bit Multiplication를 수행하기 앞서 2진수에 있어 어떤 방식으로 곱셈이 이루어지는 지 알아야 한다. 곱셈의 주축을 Multiplicand, 곱셈의 행위자를 Multiplier, 그리고 이 결과물을 Product라고 할때, 이를 이미지로 보면 아래와 같다고 본다. 중요하게 기억해야 할 것은 다음과 같다. 곱셈에서 생각해야 할 것은 결국 Multiplicand와 Multiplier의 쉬프트 이동 연산이다. Multiplicand의 쉬프트 연산은 자릿수를 올리는 것이다. Multiplier에서의 쉬프트 연산은 LSB를 빼..
Instruction Cyle은 크게 4가지 단계를 거쳐 진행된다. 1. Memory로부터 Instruction을 fetch 2. Instruction을 Decode 3. Memory로부터 effective address 읽기 4. Instruction의 실행 특히나 3번의 과정은 Instruction의 종류에 따라 생략될 수 있다. Instruction의 구조 앞선 cycle의 흐름을 단번에 파악하긴 어렵다. Instruction Cycles를 이해하기 위해선, Instruction에 어떤 종류가 있는지 부터 파악해야한다. 기본적으로 16비트 컴퓨터에서 Instruction format에는 총 3가지가 있다. 1. Memory - reference Instruction 2. Register - refe..
빅데이터의 탐색 크로스 집계(크로스 테이블, 트랜잭션 테이블) 크로스 집계를 알기 전, 크로스 테이블이라는 것을 알아야 한다. 크로스 테이블은 행과 열이 교차하는 부분에 숫자 데이터가 들어가는 테이블을 말한다. 이는 사람들이 보기에는 편하나, 열을 늘리는 것은 간단한지 않아 데이터베이스에서는 다루지 않는다. 트랜잭션 테이블이란, 열 방향으로 데이터가 증가하지 않고, 행 방향으로 증가하는 테이블을 의미한다. 결국 데이터는 크로스 테이블이 아닌 트랜잭션 테이블의 형태로 저장되어야 한다. 하지만, 보고서와 같은 시각화 과정이 필요하다면 트랜잭션 테이블 보단 보기 쉬운 크로스 테이블을 사용해야 한다. 그렇기 때문에 크로스 집계라는 것을 수행하는 것이다. 크로스 집계 : 트랜잭션 테이블에서 크로스 테이블로 변경해..
이 책은 빅데이터를 다루는 엔지니어 혹은 작업의 자동화를 원하는 데이터 과학자들을 대상으로 한다. 또한 데이터를 수집하고 원하는 형태로 가공하여 제공하고 싶은 나에게 있어 많은 깨달음을 준 책이기도 하다. 책의 구성은 다음과 같다. 1. 빅데이터의 기초지식 2. 빅데이터의 검색 - 데이터의 대화적인 집계와 시각화 그리고 데이터 마트의 성질 3. 빅데이터의 분산 처리를 위한 하둡과 스파크 등의 분산 처리 프레임워크를 통해 데이터 가공과 집계, 그리고 데이터 마트를 만드는 프로세스 4. 빅데이터의 축적 - 데이터를 수집하여 보존하는 절차를 말한다. 여기서는 분산 스토리지의 특징을 다루며, 분산 스토리지에 데이터를 넣는 데이터 수집에 대해 설명한다. 5. 빅데이터의 파이프라인은 데이터 처리를 자동화하는 절차를..
Union과 find는 집합과 관련된 연산이다. - Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산 - find : 두 노드가 같은 집합에 속해 있는 지를 확인하는 연산 코드 상에서의 구현 방법도 어렵지 않다. 일반적으로 유니온과 파인드를 구현하기 위해 1차원 배열을 사용한다. 초기에는 아무 노드도 연결되어 있지 않기 때문에 각 노드가 대표노드가 되며 자신의 인덱스 값으로 초기화 된다. union은 두 노드의 대표노드를 일치시키는 연산이다. 이 과정에서 재귀적으로 대표노드를 찾는 과정이 포함될 수 있다. find는 자신이 속한 집합의 대표노드를 찾는 연산이다. 이 과정이 중요한 이유는 단순히 노드를 찾을 뿐만 아니라, 그래프를 정돈하고 시간 복잡도를 향상시키기 때..
