All Posts

인터페이스 인터페이스란 기본적으로 코드 수행부가 없는 추상 메소드로 구성된 것이다. 상속 가능한 추상 클래스와 유사하지만, 추상 메소드만 선언되어 있다는 점, 이 때문에 상속과 같이 클래스에 구현(일종의 상속)이 가능하고 이를 통해 다중 상속이 불가능한 자바에서 인터페이스를 통한 일종의 다중 상속이 가능하다는 점이 특징이다. 이를 통해 다형성과 유연성에 이점을 가진다.기본적인 선언 문법은 아래와 같다.access_modifier interface Name { abstract public return_type method_name(parameter); ...}이때 인터페이스에 포함되는 추상 메소드는 자동으로 abstract와 public의 속성을 가지며, 따라서 생략할 수 있다.앞서 말한 바와 ..

점화 관계 점화 관계는 수열을 선행 항으로 표현한다. 점화식이라고도 한다.수열 $ a_0, a_1, \dots $ 에 대한 점화 관계는 $ a_n $ 과 그 앞의 항들인 특정 $ a_0, a_1, \dots, a_{n-1} $ 과의 관계를 나타내는 식이다. 이 수열 $ a_0, a_1, \dots $ 에 대한 초기 조건은 명시적으로 유한 개의 수열 항에 주어진 값들이다.예를 들어 피보나치 수열을 점화 관계로 나타낸다면, $ f_n = f_{n-1} + f_{n-2} $ $ (n \geq 3) $ 이고, 초기 조건은 $ f_1 = 1, f_2 = 1 $ 이다.이러한 점화 관계는 재귀적 알고리즘 및 수학적 귀납법과 관련되어 있다.예를 들어 피보나치 수열의 재귀적 알고리즘을 구현한다면 다음과 같고, 이를 수학..

람다 표현식 익명의 함수를 만드는 기능으로 C++11에서 도입되었다. 코드 내에서 간결하게 함수를 정의하고 사용할 수 있도록 도와준다. 특히 std::function이나 STL의 다양한 알고리즘 함수에 인라인으로 사용할 때 유용하다. 람다 표현식 혹은 람다식이라 한다.기본 문법은 아래와 같다.[capture](parameter) -> return_type { body };캡처 리스트에는 람다식에 사용하고자 하는 함수 바깥 변수 목록이고, 매개변수 리스트, 리턴타입, 함수 바디는 기본적인 함수와 동일하게 사용하면 된다. 이때 -> return_type은 생략 가능하다.람다식을 사용할 때 역시 일반적인 함수와 마찬가지로 소괄호를 이용하여 매개변수를 전달해주면 된다.캡처 리스트는 [=]을 통해 모든 외부 변수..

내적공간 벡터공간 $ V $ 에 대하여 내적(inner product ro dot product)은 $ \mathbf{x}, \mathbf{y} \in V $ 와 $ k \in \mathbb{R} $ 에 대하여 다음을 만족하는 함수 $ \left: V \times V \to \mathbb{R} $ 이다.$ \left = \left $$ \left = \left + \left $$ k \left = \left = \left $$ \left \geq 0, \quad \left = 0 \Leftrightarrow \mathbf{x} = \mathbf{0} $일반적으로 정의된 내적 다음의 내적 역시 이에 해당 한다.$ \mathbf{x}, \mathbf{y} \in \mathbb{R}^n $, $ \mathbf..

이진 탐색 트리 탐색작업을 효율적으로 하기 위해 정렬한 이진 트리이다.루트 노드의 값보다 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 있는 것이 특징이다. 이러한 특징 때문에 이진 탐색 트리를 최상위 노드부터 중위순회한다면 오름차순으로 정렬된 값을 얻을 수 있다. 탐색 탐색 연산은 이진 탐색 트리의 정렬을 이용한다. 최상위 노드의 값부터 비교를 시작하는데, 탐색하고자 하는 값과 같다면 탐색 종료, 탐색하고자 하는 값보다 크다면 그보다 더 작은 값을 찾아야 하기 때문에 외쪽 서브트리로 이동, 반대로 탐색하고자 하는 값보다 작다면 그보다 더 큰 값을 찾아야 하기 때문에 오른쪽 서브트리로 이동하여 탐색을 진행한다.예를 들어 트리에서 5를 탐색한다고 하면 아래와 같이 탐색한다. 탐색 값을 찾으면 해당..

스레드 이진 트리 이진 트리의 빈 포인터를 활용하여 트리 순회 속도를 향상시키기 위해 고안된 자료구조이다. 순회시 이진 트리에서 자식이 없는 노드를 만나면 일반적으로 부모노드로 돌아가지만, 스레드 이진 트리에서는 이 빈 포인터를 활용하여 그 다음 순회에 필요한 노드로 바로 찾아갈 수 있다.때문에 재귀 호출이나 스택 없이 순회가 가능하여 함수 호출에 필요한 시간을 효율적으로 절약할 수 있다.빈 포인터를 다음 순회 노드인 후속 노드(successor)를 가리키는 스레드로 활용하게 되면 해당 포인터가 더이상 빈 포인터가 아니기 때문에 일반적인 포인터인지 스레드인지가 구분 불가능해진다. 따라서 스레드 이진 트리의 노드는 해당 포인터가 스레드인지 아닌지를 나타내는 변수가 들어간다.이진 트리에서는 왼쪽과 오른쪽 자..

순회 (Traversal) 트리에서 순회란 트리의 노드들을 체계적으로 방문하는 것을 말한다. 기본적으로 세 가지 순회방법이 있는데, 전위순회, 중위순회, 후위순회이다. 왼쪽 서브트리를 L, 오른쪽 서브트리를 R, 루트 노드를 V라 하면 전위순회의 순회 순서는 VLR, 중위순회의 순서는 LVR, 후위순회의 순서는 LRV이다. 즉 V의 위치에 따라 전중후로 나눈다.전중후 순회 외에 순회도 존재한다. 스택을 이용해 반복문으로 구현하는 반복적인 순회와 큐를 이용하여 구현하는 레벨 순회가 대표적이다.각 순회들은 방문 방법만을 제시할 뿐 방문하여 어떤 연산을 할 것인지는 따로 구현하면 된다. 각 노드의 값을 출력할 수도 있고, 리스트를 만들어 리스트에 순회 순서대로 넣을 수도 있겠다.이진트리 노드의 구조체는 아래와..

추상 클래스 업캐스팅과 다운캐스팅을 통해 객체를 좀 더 자유롭게, 특히 배열등으로 묶어서 관리할 수 있다. 이때 부모 클래스에서 미리 변수와 메소드를 선언해놓고, 이를 자식 클래스에서 메소드 오버라이딩을 통해서 각각 다르게 정의한다면, 업캐스팅을 통해 다룰 때 같은 메소드를 사용하여도 다른 메소드가 사용되므로 보다 유연하고 효율적으로 객체를 다룰 수 있다.이때 부모 클래스는 자식 클래스를 유연하게 사용하기 위해서만 사용되므로 직접적으로 객체가 선언되서는 안되고, 클래스는 자식 클래스가 가질 기본적인 정보만을 담아야 한다. 이를 abstract 키워드를 이용하여 달성할 수 있다. abstract 키워드를 사용하여 클래스를 선언하면 추상 클래스를 만들어 직접적으로 해당 클래스를 사용하지 못하게 한다. 즉 업..

auto C++11부터 선언 초기화 식에서 추론되는 형식으로 변수를 선언하는 역할을 한다. C++11 이전까지는 스택에 할당되는 지역 변수를 선언하는 키워드였다. 따라서 C++ 버전에 따라 달리 동작할 수 있으니 주의해야 한다.복잡한 변수 선언을 간소하게 하고, 이름이 긴 자료형이나 헷갈릴 수 있는 자료형을 선언할 때 실수를 줄일 수 있다는 장점이 있다.예를 들어 아래와 같은 코드가 있다고 가정하자.#include using namespace std;class ClassNameThatIsUnnecessarilyLong { ...}int main() { ClassNameThatIsUnnecessarilyLong temp; ClassNameThatIsUnnecessarilyLong* ptem..

STL STL(Standard Template Library)은 C++에서 제공하는 표준 템플릿 라이브러리로, 다양한 자료구조와 알고리즘을 템플릿 형태로 제공한다.STL은 효율적이고 재사용 가능한 코드를 작성할 수 있도록 돕는 강력한 라이브러리로, 크게 컨테이너, 반복자(iterator), 알고리즘의 세 가지 주요 구성 요소로 이루어져 있다. STL container • vector#include 벡터는 가변 크기의 배열을 일반화한 클래스로 다양한 자료형을 담을 수 있다. 원소의 저장, 삭제, 검색 등 다양한 멤버 함수를 지원하며 인덱스를 통해 접근 가능하다. 아래와 같이 선언하여 사용한다.vector vector_name;주요 멤버 함수는 다음과 같다.push_back(element)벡터 마지막에 el..