All Posts

그래프 동형사상 어떤 두 그래프가 겉보기에는 완전히 다른 그래프처럼 보이지만, 구조만 때어놓고 본다면 같은 구조를 가진 그래프일 수 있다. 아래 그래프를 보면 정점과 간선의 이름, 생김새가 다르게 보인다.그러나 재배열 한다면 비슷한 그래프처럼 보인다.이처럼 구조가 같은 그래프를 동형이라 한다. 좀더 명확하게는 다음과 같이 정의힌다.그래프 $ G_1 = (V_1, E_1) $ 과 그래프 $ G_2 = (V_2, E_2) $ 가 동형(isomorphic)이라 할 때 다음 조건을 만족하는 함수 쌍 $ f $ 와 $ g $ 가 존재하고, 이를 동형사상(혹은 동형함수)이라 한다.$ f: V_1 \to V_2 $ 와 $ g: E_1 \to E_2 $ 는 전단사 함수이다. 즉 $ f $ 는 $ V_1 $ 의 모든 정..

행렬표현 일반적으로 $ n $ 차원 벡터공간 $ V $ 에서 $ m $ 차원 벡터공간 $ W $ 의 선형변환을 행렬변환으로 나타낼 수 있고, 이는 좌표벡터를 통해 확인해볼 수 있다.$ n $ 차원 벡터공간 $ V $ 의 순서 기저를 $ S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \} $ 이라 하고, $ m $ 차원 벡터공간 $ W $ 의 순서 기저를 $ R = \{ \mathbf{y_1}, \mathbf{y_2}, \cdots, \mathbf{y_m} \} $ 이라 하며, $ T: V \to W $ 를 선형변환이라 하자. $ \mathbf{x_i} \in S $ $(i = 1, 2, \cdots, n) $ 에 대하여 $ T(\mathbf{x_i})..

한글 깨짐 VS Code 에서 코딩하면 기본적으로 UTF-8로 인코딩된다. 그런데 Code Runner 를 이용하면 터미널을 이용해서 코드를 컴파일하고 출력하는데, 이때는 윈도우 설정인 EUC-KR(혹은 CP949)로 인코딩된다. 따라서 한글이 깨지게 된다.이를 해결하기 위해서 터미널에 다음 명령어를 입력하여 UTF-8로 인코딩해주어야 한다. 물론 아예 코드를 EUC-KR로 작성하는 것도 방법일 수 있지만, 이렇게 작성된 코드는 깃허브에 올리거나 할 때 깨지기 때문에 윈도우 터미널 설정을 건드는 것이 좋다.-encoding UTF-8이제 이 입력어를 Code Runner 를 이용할 때 마다 입력되도록 하면 될 것 같다.VS Code 의 좌측 확장을 클릭하고 Code Runner 를 찾은 다음 톱니바퀴를 ..

최단 경로 문제 (Shortest Path Problem) 가중치 그래프는 간선에 값을 부여한 그래프이다. 이때 경로의 길이는 경로 안의 간선의 가중치 합으로 정의하고, 간선 $ (i, j) $ 의 가중치를 $ w (i, j) $ 라 표기한다.가중치 그래프가 있을 때 2개의 정점 간 가장 길이가 짧은 경로를 찾는 최단 경로 문제는 내비게이션, 통신망 등 여러 분야에서 활용된다. 다익스트라 알고리즘 다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 최단 경로를 구하는 알고리즘이다. $ n $ 개의 정점으로 구성되고, 단순하며, 연결된 가중치 그래프에 대하여 최악의 경우 $ \mathcal{\Theta} (n^2) $ 의 시간복잡도를 가진다.이 알고리즘은 가중치 그래프의 어느 한 정점에서 다른 정점으로의 최..

표준행렬 (Standard Matrix) 선형변환에 대해 이야기하면서 행렬을 이용한 선형변환을 행렬변환(링크)이라 하였다. 다시 정리해보자면 행렬 $ A_{m \times n} $ 과 $ \mathbf{x} \in \mathbb{R}^n $ 에 대하여 $ T (\mathbf{x}) = A \mathbf{x} $ 로 $ T : \mathbb{R}^n \to \mathbb{R}^m $ 을 정의한다면 $ T $ 는 선형변환이다.일반적으로 $ T: \mathbb{R}^n \to \mathbb{R}^m $ 이 선형변환이라면 표준기저 $ \{ \mathbf{e_1} , \mathbf{e_2} , \cdots, \mathbf{e_n} \} $ 에 대하여 다음과 같다고 할 수 있다.$ T(\mathbf{e_1}) = ..

파일 입출력 외부 파일을 읽고 쓰거나 저장해야 할 경우, 파일을 코드로 입력받고 출력할 수 있도록 처리해야 한다. 입력 파일을 읽고 필요한 작업을 수행한 후, 결과를 새로운 파일로 저장하는 방식을 사용한다. 파일로 저장하는 이유 중 하나는 데이터를 스토리지에 저장하여 반영구적으로 보존할 수 있기 때문이다.컴퓨터의 기억장치는 주기억장치와 보조기억장치로 크게 나눌 수 있는데, 주기억장치는 흔히 말하는 RAM이고, 보조기억장치는 SSD, HDD 등을 말한다. 주기억장치는 휘발성 메모리를 사용하기 때문에 전원이 꺼지면 데이터가 사라진다. 반면 보조기억장치는 비휘발성 메모리를 사용하기에 전원 공급 없이도 데이터 보존이 가능하다. 단 데이터 처리에서 RAM이 빠르기에 RAM에서 일반적으로 데이터를 처리한다.파일 입..

선형변환 벡터공간 $ V $ 의 각 벡터 $ \mathbf{v} $ 를 벡터공간 $ W $ 의 벡터 $ \mathbf{w} $ 에 대응시키는 함수를 $ T $ 라 하면 이를 다음과 같이 나타낸다.$$ T : V \to W $$이때 $ \mathbf{w} $ 를 $ T $ 에 의한 $ \mathbf{v} $ 의 상(image)이라 하고 $ \mathbf{w} = T(\mathbf{v}) $ 로 나타낸다. 그리고 $ V $ 를 $ T $ 의 정의역(domain)이라 한다.만약 이 $ T $ 가 다음 조건을 만족하면 $ T $ 를 선형변환이라 한다.모든 $ \mathbf{v_1} , \mathbf{v_2} \in V $ 에 대하여 $ T(\mathbf{v_1} + \mathbf{v_2}) = T(\mathbf..

오일러 사이클 그래프 안의 모든 정점과 모든 간선을 포함하는 사이클을 오일러 사이클이라 한다. 쾨니히스베르크 다리 문제가 대표적인 오일러 사이클을 확인하는 문제이다.어떤 그래프 $ G $ 가 오일러 사이클을 가진다면, $ G $ 는 연결 그래프이고, 각 정점의 차수는 짝수여야 한다. 이를 증명하기 위해 $ G $ 가 오일러 사이클을 가진다 가정하자. $ v $ 와 $ w $ 가 $ G $ 의 정점이면 $ v $ 에서 $ w $ 까지 취한 오일러 사이클의 일부는 $ v $ 에서 $ w $ 까지의 경로이고, 따라서 $ G $ 는 연결 그래프이다. 어떤 간선으로 $ v $ 에 도착하면 다른 간선을 따라 반드시 떠나야 하기 때문에, 또한 $ v $ 에 연결된 모든 간선이 반드시 사용되어야 하기 때문에 $ v $..

그래프 그래프는 정점(vertex)과 간선(edge)로 이루어져 있는데, 각 정점들을 연결하는 것이 간선이다. 특정 정점에서 다른 정점으로 이동하는것을 경로(path)라 한다.그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 나눌 수 있는데, 무방향 그래프는 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있고, 각 간선 $ e \in E $ 는 순서가 없는 정점의 쌍으로 나타낸다. 일반적으로 그냥 그래프라 말하면 무방향 그래프를 말한다. 방향 그래프 역시 정점의 집합 $ V $ 와 간선의 집합 $ E $ 로 구성되어 있는데, 각 간선 $ e \in E $ 는 순서가 있는 정점의 쌍으로 나타낸다. 통합적으로 그래프 $ G $ 는 $ G = ..

정렬  여러가지 값들이 규칙없이 모여있을 때 이를 규칙에 맞게 정렬해야 한다면 여러가지 정렬 알고리즘을 사용할 수 있다. 위 영상은 여러가지 정렬 알고리즘을 시각화한 것이다.정렬은 효율적인 탐색에도 필수적인데, 예를 들어 사전에서 단어들이 알파벳 순서가 아니라 랜덤으로 섞여 있다고 가정해보자. 알파벳 순으로 정렬되어 있을 때는 우리는 알파벳이 어디 있는지 알 수 있지만, 랜덤으로 섞여 있다면 사전의 모든 페이지를 확인해야 할 것이다.일반적으로 정렬 대상을 레코드(record)라 하고, 레코드는 필드(field)라는 레코드보다 작은 단위로 구성된다. 이때 키필드(key field)를 기준으로 레코드를 구별하고 정렬한다.모든 경우에 최적인 정렬 알고리즘은 없다. 레코드 수, 레코드의 크기, 키의 특성, 가용..