전체 글

파일 종류 파일은 텍스트 파일과 바이너리 파일로 나뉜다. 텍스트 파일은 문자 데이터로 구성된 파일로, 사람들이 사용하는 글자 혹은 문자들만 포함된다. 각 문자는 ASCII 코드나 유니코드로 저장되며, 일반적으로 텍스트 편집기를 사용해 읽고 수정할 수 있고, 대표적인 예로 txt 파일이 있다. 반면, 바이너리 파일은 텍스트로 표현되지 않는 바이너리 데이터를 포함하며, 특정 프로그램만이 이 데이터를 해석할 수 있고, 이미지, 오디오, 실행 파일 등이 바이너리 파일의 대표적 예이다. 바이너리 파일은 각 바이트의 의미가 응용 프로그램에 의해 정의된다.참고로 어느 파일이든 파일의 끝을 읽으면 EOF, 즉 -1을 반환한다. 파일 입출력 스트림 (File I/O Stream) 파일 입출력 스트림은 파일을 프로그램과 ..

직교행렬 $ n $ 차 정사각행렬 $ A $ 에 대하여 $ A^T A = I_n $ 이면 $ A $ 를 직교행렬이라 한다. 또한 이는 $ A^T = A^{-1} $ 이면 $ A $ 는 직교행렬이다와 동치이고, $ A $ 의 열(행)벡터들은 정규직교집합이다와 동치이다.$ A $ 의 열(행)벡터들이 정규직교집합인 이유는 $ A^T A = I = A A^T $ 이기 때문이다.$ A $ 가 직교행렬이면 $ A^T A = I $ 이고, $ | A | = | A^T | $ 이므로 $ 1 = | I | = | A^T A | = | A^T | | A | = | A | ^2 $ 이므로 $ | A | = \pm 1 $ 이다. 즉 $ A $ 가 직교행렬이면 $ | A | = 1 $ 또는 $ -1 $ 이다. 직교 대각화 정사..

포맷 플래그 포맷 플래그는 C++에서 입출력 형식을 지정하기 위한 플래그이다. C에서는 printf() 와 함께 다양한 형식 지정자 및 플래그를 사용하여 입출력 형식을 지정하였지만 C++에서는 입출력 스트림을 이용하여 입출력을 제어하고, 이때 std::cin 혹은 std::out 이 사용되기 때문에 C와 다른 방식으로 입출력 형식을 지정해주어야 한다.플래그값의미ios::skipws$\rm 0x0001$입력 스트림에서 공백 문자(Space, Tap, Enter) 무시ios::unitbuf$\rm 0x0002$출력 스트림에 들어오는 데이터를 버퍼링하지 않고 바로 출력ios::uppercase$\rm 0x0004$16진수 표현의 알파벳을 대문자로 출력ios::showbase$\rm 0x0008$16진수는 $\..

스트림 및 버퍼 스트림은 입출력 및 에러 전달 과정 등 데이터의 흐름을 추상화한 개념이다. 구체적으로는 이 흐름을 구성하는 일련의 데이터 요소를 말한다. 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) { ..