전체 글

오일러 사이클 그래프 안의 모든 정점과 모든 간선을 포함하는 사이클을 오일러 사이클이라 한다. 쾨니히스베르크 다리 문제가 대표적인 오일러 사이클을 확인하는 문제이다.어떤 그래프 $ 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)를 기준으로 레코드를 구별하고 정렬한다.모든 경우에 최적인 정렬 알고리즘은 없다. 레코드 수, 레코드의 크기, 키의 특성, 가용..

예외 모든 프로그래밍 코드는 오류가 발생할 가능성이 있다. 그냥 실수로 오타를 낼 수도 있고, 잘 모르고 문법에 안 맞게 코드를 짤 수도 있으며, 예상하지 못한 값이 들어오며 오류가 발생할 수도 있다. 이러한 오류는 Throwable 클래스(참고 링크)의 하위 Error 클래스(참고 링크)와 Exception 클래스(참고 링크)에 정의되어 있다.오류(error)는 메모리 부족(OutOfMemoryError), 스택오버플로우(StackOverFlowError)처럼 JVM이나 하드웨어 등 시스템의 문제로 발생하는 것이다. 그러므로 개발자가 다루기 힘들고, Error가 발생하면 프로그램은 종료된다.그러나 예외(exception)는 발생하자마자 프로그램을 종료하지 않는다. 즉 개발자가 예외를 처리할 수 있다. ..

탐색 그래프의 어떤 정점에서 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다. 효율적인 구간을 찾거나, 특정 정점에 도달 가능한지 알아볼 때 자주 사용된다.탐색은 대표적으로 깊이 우선 탐색과 너비 우선 탐색이 존재한다. 말 그대로 깊이를 먼저 탐색하면 깊이 우선 탐색이고, 너비를 우선 탐색하면 너비 우선 탐색이다. 트리에서 전위, 중위, 후위 순환이 깊이 우선 탐색의 일종이고, 레벨 순회가 너비 우선 탐색의 일종이다. DFS 한 방향으로 탐색 가능한 곳까지 가다가 더 이상 갈 수 있는 정점이 없다면 다시 가장 가까운 갈림길로 돌아와 그 갈림길부터 다시 안 간 방향으로 탐색을 진행하는 것을 말한다. 되돌아가기 위해 스택이 필요한데, 재귀를 이용하여 묵시적 스택 이용이 가능하다.위 그래프에서 빨..

그래프  연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 트리 역시 그래프의 특수한 형태이다.다음은 그래프의 기본적인 용어이다.정점(vertex) 혹은 노드(node): 각 객체간선(edge) 혹은 링크(link): 각 정점을 연결하는 선 혹은 관계부분 그래프(sub graph): 어떤 그래프의 정점과 간선의 부분집합으로 이루어진 그래프인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점차수(degree): 무방향 그래프에서 하나의 정점에 연결된 다른 정점의 수진입 차수(in-degree): 방향 그래프에서 하나의 정점으로 오는 간선의 수진출 차수(out-degree): 방향 그래프에서 하나의 정점에서 외부로 향하는 간선의 수경로(path): 한 정점에서 다른 ..

결측값 데이터가 없는 것을 결측값이라 한다. 데이터가 0 이거나 계산될 수 없는 것과는 다르다. R 에서는 NA로 표기한다.결측값이 포함되면 당연하게도 데이터 분석에 지장이 생긴다. 다양한 함수에서 해당 데이터를 그대로 사용하지 못하는 것부터 계산했더라도 결측값이 있는 데이터가 얼마나 정확한지에 대한 검증이 없기 때문에 신뢰성에 문제가 생긴다. 따라서 결측값을 사전에 전처리(preprocessing) 해주어야 한다. 결측값 확인is.na(data)is.na() 함수로 결측값을 확인할 수 있는데, 결측값이면 TRUE를, 없으면 FALSE를 반환한다. 만약 단일 변수가 아니라면 해당 자료형에 맞춰 TRUE와 FALSE를 반환한다.예를 들어 아래와 같은 코드가 있다 해보자.vdata 출력은 다음과 같다.> i..

곡선적합 특정 실험을 통해 측정값을 얻었다면 이를 설명하는 함수를 구할 수 있다. 즉 $ (x_0, y_0) $, $(x_1, y_1) $, $ \cdots $, $(x_n, y_n) $ 과 같은 자료가 주어졌을 때 이 모든 점을 지나면서 이를 대표하는 곡선, 혹은 함수식 $ y = f(x) $ 을 찾을 수 있는데, 이를 곡선적합이라 한다.$$ y = f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^{n-1} $$위와 같은 $ n $ 차 다항식에 대하여 점 $ (x_i, y_i ) $ 가 곡선 $ y = f(x) $ 위에 있다 가정하면, $ f(x_i) = y_i $ 이다. 이를 $ n + 1 $ 개의 미지수 $ a_0, a_1, \cdots, a_n $ 를 가진 선형방..

우선순위 큐 우선순위 큐는 일반적인 큐와 달리 우선순위가 높은 데이터가 먼저 나가는 큐이다. 따라서 일반적인 큐처럼 리스트로 구현하면 우선순위가 높은 데이터를 이동시킬 때, 즉 삽입, 삭제를 할 때 시간복잡도가 커지므로 트리를 이용한 힙으로 구현하는 것이 일반적이다. ADT 객체 (Object)0 개 이상의 우선순위를 가진 요소들의 모임연산 (Operation)create() ::= 우선순위 큐를 생성한다.init() ::= 우선순위 큐를 초기화한다.is_full() ::= 우선순위 큐가 가득 차 있다면 true 를, 아니라면 false 를 반환한다.is_empty() ::= 우선순위 큐가 비어있다면 true 를, 아니라면 false 를 반환한다.insert(item) ::= 우선순위 큐에 item을 추..

정규직교집합 내적공간의 원소 $ \mathbf{x} $ 와 $\mathbf{y} $ 에 대하여 $ \left = 0 $ 일 때 두 벡터가 직교한다고 정의하였다. 만약 $ V $ 가 내적공간일 때 $ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \in V $ 에 대하여 $ S = \{ \mathbf{x_1}, \mathbf{x_2}, \cdots, \mathbf{x_n} \} $ 을 가정하자. 이때 $ S $ 의 서로 다른 두 벡터가 모두 직교한다면 $ S $ 를 직교집합(orthogonal set)이라 한다. 또한 직교집합 $ S $ 의 벡터가 모두 단위벡터이면 $ S $ 를 정규직교집합이라 한다.즉 다음이 정의된다.$ S \text{ } \text{ is or..