All Posts

스트림 및 버퍼 스트림은 입출력 및 에러 전달 과정 등 데이터의 흐름을 추상화한 개념이다. 구체적으로는 이 흐름을 구성하는 일련의 데이터 요소를 말한다. C++에서는 특히 표준 입력, 표준 출력, 표준 에러 스트림이 존재하고, 입력은 키보드와 같은 입력 장치에서 데이터를 받아 프로그램으로 전달하며, 출력과 에러는 프로그램에서 생성된 데이터를 출력 장치, 예를 들어 디스플레이로 전달한다.입출력 스트림에는 버퍼가 사용되는 경우가 많은데, 일시적으로 데이터들을 저장하는 곳이라 보면 된다. 데이터를 입력받은 그 즉시 전달하는 것이 아니라 일정 수준, 혹은 전달하는 특정한 입력이 있을 때까지 버퍼에 저장해두었다가 전달하는 것이다. 예를 들어서 std::cin 은 사용자가 공백문자나 개행문자를 입력하기 전까지 버퍼..

행렬 대각화 정사각행렬 $ A $ 와 어떤 가역행렬 $ P $ 에 대하여 $ P^{-1}AP $ 가 대각행렬이 된다면 $ A $ 를 대각화 가능한 행렬(diagonalizalble matrix)이라 하고, $ P $ 는 $ A $ 를 대각화하는 행렬이라 한다.만약 $ A $ 가 대각행렬이라면 $ P $ 를  $ I $ 로 둠으로써 대각화 가능하다.이러한 대각화가 가능할 필요충분조건은 $ n $ 차 정사각행렬 $ A $ 가 $ n $ 개의 일차독립인 고유벡터를 갖는 것이다. 이때 $ A $ 는 고윳값 $ \lambda_1, \lambda_2, \cdots, \lambda_n $ 을 주대각성분으로 갖는 대각행렬 $ D $ 와 닮은 행렬이다.더보기$ A $ 개 대각화 가능한 $ n $ 차 정사각행렬이라할 때 ..

해시테이블  해시테이블이랑 해시를 이용하여 키(key)에 대응되는 값(value)을 저장하는 자료구조이다. 키에 대응되는 값에 빠르게 접근하는 것이 특징인데, 이는 해시 함수(hash function)를 이용하여 키에 대응되는 해시 주소(hash address), 즉 인덱스(index)를 생성하고, 이 인덱스를 통해 배열(버켓, bucket)에 값을 저장하기 때문이다. 배열에 저장하기 때문에 임의접근(ramdom access)이 가능하고, 따라서 잘 만들어진 해시테이블에서 키를 이용하여 값에 접근하는 것의 시간복잡도는 $ \mathcal{O}(1) $ 이다.해시 함수를 이용하여 키를 테이블 인덱스로 바꾸는 것을 해싱이라 하는데, 이 해싱을 어떻게 할 것이냐가 해시테이블의 접근 성능을 판가름한다. 당연히 ..

2-3 트리  차수가 2 또는 3인 트리, 즉 하위 노드의 개수가 두 개 혹은 세 개인 트리이다. 2-노드라면 이진 탐색 트리처럼 한 개의 데이터와 두 개의 자식 노드를 가지고, 3-노드라면 두 개의 데이터와 세 개의 자식 노드를 가진다.왼쪽 서브 트리에 있는 데이터들은 모두 첫 번째 데이터보다 작은 값이고, 중간 서브 트리에 있는 값들은 모두 첫 번째 데이터보다 크고, 두 번째 데이터보다 작아야 한다. 오른쪽 서브 트리에 있는 값들은 두 번째 데이터보다 커야 한다. 즉 이진 탐색 트리와 유사하게 정렬되어 있어야 한다.즉 트리가 위와 같다면 왼쪽 서브 트리의 값은 모두 $ k $ 보다 작고, 오른쪽 서브 트리의 값은 모두 $k $ 보다 크다.트리가 위와 같다면 왼쪽 서브 트리의 값은 $ k_1 $ 보다 ..

균형 이진 탐색 트리  이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조를 가지는데, 이진 탐색의 대상은 배열이므로 삽입과 삭제가 비효율적이지만 이진 탐색 트리에서 삽입과 삭제는 효율적이다. 단 이진 탐색 트리는 불균형인 경우 탐색의 시간복잡도가 $ \mathcal{O}(n) $ 이 되는 단점이 있다.이를 이진 탐색과 마찬가지로 효율적으로 탐색하기 위해서는 트리가 균형 트리여야 한다. 즉 이진 트리이면서 이진 탐색과 마찬가지로 왼쪽 서브트리 값이 노드 값보다 작게, 오른쪽 서브트리 값이 노드 값보다 크게 오도록 하며, 균형잡혀 있다면균형 이진 탐색 트리이다.간선의 수, 높이 등은 이진 트리(링크)의 속성을 일부 따른다. 노드가 $ n $ 개일 때 간선은 $ n -1 $ 개이고, 높이는..

보간 탐색  정렬된 리스트에서 탐색 범위를 줄여나가며 탐색하는 방식인데, 이진 탐색은 그냥 중앙을 탐색 위치로 지정하고 비교했다면 보간 탐색은 아래와 같은 공식을 이용해서 탐색 위치를 결정한다. 즉 이진 탐색이 균등 분할하였다면 보간 탐색은 불균등 분할하여 탐색한다.$$ \dfrac{\text{key} - \text{list}[\text{low}]}{\text{list}[\text{high}] - \text{list}[\text{low}]} \times (\text{high} - \text{low}) + \text{low} $$예를 들어 설명한다면 1400페이지의 전화번호부에서 하정우라는 이름을 찾는다고 해보자. 성에 ㅎ 이 들어가니까 당연히 중앙을 보는 것보다 1300페이지쯤부터 찾아보는 것이 효율적일..

순차 탐색  말 그대로 순차적으로 탐색하는 방법이다. 주어진 리스트의 시작부터 끝까지 찾으려는 값인 탐색키와 비교하면서, 탐색키와 같으면 반환, 다르면 다음 값을 탐색한다. 정렬되지 않은 경우 최선의 방법일 수 있다.값이 존재한다면 평균 비교 횟수는 $ (n+1) / 2 $ 이고, 값이 존재하지 않는다면 $ n $ 으로 시간복잡도는 $ \mathcal{O} (n) $ 이다.조금 개선된 순환 탐색 방법으로는 탐색 대상 리스트의 끝에 탐색키를 삽입하고 탐색키와 같은 값을 찾을 때까지 탐색한 후 탐색된 값의 인덱스가 삽입한 리스트의 인덱스라면 탐색 실패로 처리하는 방법이 있다. 구현 | C int sequential_search(int list[], int key, int low, int high) { ..

결정 트리 어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다. 5개의 동전 문제 5개의 동전 중 하나의 동전만 무게가 다르다면 어떤 동전이 무게가 다르고, 다른 동전보다 무거운지 가벼운지를 알 수 있는 결정 트리이다.최악의 경우 시간을 최악의 경우에 필요한 무게 비교의 수로 정의한다면 최악의 경우 시간은 결정 트리의 높이인 $ 3 $이다. 만약 최악의 경우에도 $ 2 $ 이하의..

이진 트리 이진 트리는 각 정점의 자식의 수가 최대 2개인 트리이다. 이때 자식은 왼쪽 자식 혹은 오른쪽 자식으로 지정된다. 트리 운행 트리의 각 정점을 정확히 한 번씩 방분하는 체계적 방법으로 트리를 운행한다. 순회라고도 한다.이진 트리에서 운행은 전위 운행법(preorder traversal), 중위 운행법(inorder traversal), 후위 운행법(postorder traversal)이 존재한다. 전위, 중위, 후위에서 전, 중, 후는 운행 중 루트의 위치를 말한다. 전위는 루트를 먼저 처리하고, 중위는 중간에, 후위는 마지막에 처리한다. 전위 운행법입력: $ T $ (이진 트리의 루트 혹은 트리가 비어있음을 나타내는 NULL)출력: $ \text{process} $ 에 따라 종속적preord..

신장 트리 $ T $ 가 그래프 $ G $ 의 모든 정점을 포함하는 부분 그래프이면서 트리라면 $ T $ 를 $ G $ 의 신장 트리라 한다.일반적으로 그래프는 여러 개의 신장 트리를 가진다.예를 들어 위와 같은 그래프에는 아래와 같은 신장 트리가 있을 수 있다. 주황색 선으로 표시된 것이 신장 트리이다.그래프 $ G$ 가 신장 트리 $ T $ 를 가지고 있다는 것과 $ G $ 가 연결되어 있다는 것은 동치이다. 증명은 다음과 같다.그래프 $ G $ 가 신장 트리 $ T $ 를 가진다 가정하고, $ a, b \in V_G $ 를 가정하자. 그렇다면 $ a, b \in V_T $ 이다. $ T $ 가 트리이므로 $ a $ 에서 $ b $ 로의 경로 $ P $ 가 존재하며 따라서 연결되어 있다.반대로 $ G..