BST BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 과정 BST를 이용한 탐색에서는 다음과 같은 과정을 거친다. 이진 탐색 트리 만들기 (생성) 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색) 삭제 및 삽입 하기 (삭제 / 삽입) 예시 먼저 이진 탐색 트리를 만들어보자. 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다. 결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다. 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다. 왼쪽 그림에서 오른쪽 그..

비트 조작 개념 비트(bit)란 0과 1의 값을 가질 수 있는 데이터의 단위이다. 4bit를 모은 단위를 니블(nibble)이라 부르고, 8bit를 모은 단위를 바이트(byte)라고 부른다. 2byte를 모은 단위는 일부 전자통신기기에서 워드(word)라고 한다. 구현 C++에서는 비트를 다루기 위해서 이라는 헤더를 포함해서 사용한다. 연산 C++에서 비트연산들은 위에서 언급한 라이브러리로 쉽게 가져다 쓸 수 있지만, 개념 공부 측면에서 그냥 구현도 하고 라이브러리 사용법도 익혀두려한다. 메모리 상에 변수를 저장하는 것이 1byte 단위로 가능하기 때문에, bit 단위의 자료형은 없다. 다만 bool 형은 메모리 상에서 1byte를 차지하지만 가능한 값이 true 혹은 false 밖에 없으므로 이를 이용..

스택 특징 용도 연산 삽입 삭제 접근 구현 큐 용도 종류 연산 삽입 삭제 접근 구현 우선순위 큐 덱 용도 구현 스택 스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다. top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다. 특징 LIFO 내부 요소를 확인할 방법이 pop 말고는 없다. 용도 입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다. 계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로..

목차 배열 선언 초기화 접근 다차원 배열 희소 행렬 표현 주소와 포인터 포인터 특징 제약 동적 메모리 할당 동적 배열(vector) 문자열 선언 초기화 함수 배열 / 문자열 배열 배열이란 단일 식별자로 _같은 자료형_의 여러 변수를 접근할 수 있게 해주는 자료구조이다. 선언 c++에서는 int arr[3];와 같이 자료형 배열이름[배열 길이];로 변수를 선언한다. 이 때, 대괄호 내의 요소의 갯수는 '컴파일 타임 상수'여야한다. 소스코드를 컴파일할 때, 고정 배열의 길이를 알아야하기 때문이다. 따라서 매크로 기호 상수 (ex_ #define ARRAY_LEN 5)나 열거자(ex_enum A{ARRAY_LEN = 5})는 배열의 길이로 사용할 수 있다. const 또한 컴파일 시 고정되는 상수이므로 사용가..