C++
바인딩, 오버로딩과 오버라이딩, 가상함수와 가상 테이블
바인딩
- 어느 블록에 있는 함수를 실행하라는 의미로 해석하는 것을 바인딩이라고 한다.
- 컴파일러는 함수를 호출하는 코드를 컴파일 타임에 고정된 메모리 주소로 변환시킵니다. 이것을 정적바인딩이라고 합니다.
- 가상 함수는 런타임에 객체를 결정하게 되는데 이것을 동적바인딩이라고 합니다. 기초 클래스 타입의 포인터나 참조를 통하여 호출될 때만 동적 바인딩을 합니다.
오버로딩
- 같은 이름의 함수에 매개변수와 리턴값이 다른 함수들로 중복 정의하는 것
오버라이딩
- 부모클래스의 함수를 자식클래스에 같은 이름, 매개변수로 재정의 해서 사용하는 것
가상 함수
- 파생 클래스에서 재정의할 것으로 기대하는 멤버 함수
가상 함수의 필요한 이유
- 일반 함수는 고정된 메모리 주소를 불러오므로 상위클래스에 하위클래스 주소를 넣어주게 되어도 정적바인딩때문에 상위클래스의 함수를 불러오게 됩니다. 그렇기에 파생클래스에서 재정의하고 싶은 멤버 함수가 있을 경우 가상 함수를 사용하여야 합니다.
가상테이블
- 가상함수를 가진 클래스마다 가상함수 포인터의 정보들을 저장하는 가상함수 테이블이 있습니다. 상위 클래스의 가상함수테이블을 하위클래스가 받고 가상함수인 부분은 재정의하여 하위클래스의 가상함수 테이블이 됩니다.
상위클래스의 참조나 포인터에 하위클래스를 넣어서 업캐스팅을 하게 된다면, 상위클래스는 하위클래스의 가상함수 테이블을 가지게 되므로 상위클래스에서 해당 가상함수를 호출할 때에 하위클래스의 가상함수가 호출하게 됩니다.
얇은 복사, 깊은 복사
얇은 복사
- 디폴트 복사 생성자에 의한 멤버 대 멤버의 복사 방식을 말합니다. 멤버 대 멤버 복사이기 때문에 객체 a, b가 있을 때 객체 a의 변수을 가리키는 주소 값을 b도 같이 할당받아, 두 객체가 같은 변수을 참조하는 문제가 생길 수도 있습니다. 그래서 깊은 복사가 필요합니다.
깊은 복사
- 클래스가 new에 의해 초기화되는 포인터들을 멤버로 가지고 있을 경우에, 포인터 자체를 복사하는 것이 아니라 그 포인터가 지시하는 데이터를 복사하는 복사 생성자를 정의해야 하는데 이것을 깊은 복사라고 한다.
malloc과 new의 차이
malloc
- 함수로 구성되어 있다.
- sizeof로 할당해야 될 메모리의 크기를 알아야한다.
- 생성자를 호출하지 않는다.
- free를 사용하여서 할당 해제한다.
- 오버로드 할 수 없다.
new
- 연산자이다.
- 생성자를 호출한다.
- 초기화를 동시에 할 수 있다.
- delete를 사용하여 할당 해제한다.
- 오버로드 할 수 있다.
call by value, call by reference
call by value
- 값을 통해 전달한다.
- 그 값이 복사되어서 전달 되기때문에 원본의 값이 변경되지 않는다.
call by reference
- 주소 값을 통해 전달한다.
- 그 주소를 통해 있는 데이터를 전달하기 때문에 원본의 값이 변경될 여지가 있다.
- 함수라면 매개변수를 const와 참조를 통해서 전달하면 원본의 값이 변경되는 것을 막으며 비용의 문제도 해결할 수 있다.
업캐스팅과 다운캐스팅
업캐스팅
- 명시적 형변환이 필요없이 파생클래스 객체를 기초클래스의 포인터로 가리키는 것이다.
다운캐스팅
- 기초클래스의 객체를 파생클래스의 포인터로 가리키는 것입니다. 이 때 기초클래스는 파생클래스의 포인터를 갖고있어야 한다. 갖고있는 데이터의 크기가 다르기 때문이다. 다이내믹캐스트를 사용하여서 다운캐스팅이 가능한지를 판단하여 다운캐스팅하는 방법을 사용한다.
cast연산자의 종류
static cast
- 컴파일 타임에 형변환이 가능한지 검사합니다. 주로 기본자료형을 바꿀 때 사용합니다.
dynamic cast
- 런타임에 형변환이 가능한지 검사합니다. 주로 상속 관계에서 캐스팅을 할 때 사용합니다.
reinterpret_cast
- 임의의 포인터끼리의 형변환을 실시합니다. 타입을 바로 재해석 해버립니다.
const_cast
- 상수성을 제거해줍니다.
함수포인터
함수포인터
- 함수를 변수처럼 사용할 수 있게 도와준다. 한 함수포인터에 다른 함수를 넣어서 그 함수포인터가 넣어진 함수를 호출하게 된다. 함수를 다른 함수에 전달할 때 유용하게 쓰인다.
스마트 포인터
스마트 포인터의 사용 이유
- 메모리 누수의 방지를 위해서 쓰입니다. 사용이 끝난 메모리를 자동으로 해제시켜줍니다.
auto_ptr
- 현재는 쓰이지 않지만 이동을 자신의 복사 연산으로 사용합니다.
unique_ptr
- 이름과 같이 항상 자신이 가리키는 객체를 소유합니다.
shared_ptr
- 하나의 특정 객체를 참조하는 스마트 포인터가 총 몇 개인지를 참조하는 스마트 포인터입니다.
- 만약 서로가 상대방을 가리키는 shared_ptr를 가지고 있다면, 참조 횟수는 절대 0이 되지 않으므로 메모리는 영원히 해제되지 않습니다. 이렇게 서로가 상대방을 참조하고 있는 상황을 순환 참조라고 합니다.
weak_ptr
- 하나 이상의 shared_ptr 인스턴스가 소유하는 객체에 대한 접근을 제공하지만, 소유자의 수에는 포함되지 않는 스마트 포인터입니다.
객체지향 프로그래밍
객체지향 프로그래밍의 4가지 특징
추상화
- 공통된 특성을 파악하고 불필요한 특성은 제거한다.
캡슐화
- 객체는 상태와 동작을 가지며 객체 스스로 상태를 책임지도록 한다.
상속성
- 상위 객체를 상속 받을 수 있도록 한다.
다형성
- 동일한 요청에 다른 방식으로 처리할 수 있도록 한다.
자료구조
시간 복잡도에 대해서
- 빅오표기법에 따라서 최악의 시간복잡도를 계산합니다.
- 입력되는 n의 크기에 따라서 실행되는 조작의 수를 나타냅니다.
- 예로 2중 for문의 경우 O(n^2), 문제를 해결할 때마다 필요 단계들의 줄어들게 되면 O(logn)입니다.
vector와 list의 차이점
vector
- 연속적인 메모리이다.
- 끝에 요소를 추가, 제거하는 것은 O(1)이지만, 다른곳에서는 O(n)이다.
- 특정 위치 접근이 가능하다. ([]나 at으로 접근, 이 경우 O(1))
- 탐색은 O(n)이다.
list
- 비연속적인 메모리이다.
- 더블링크드리스트로 구성되어있다.
- 특정 위치 접근이 되지 않지만 어느 위치에서든 삽입 삭제가 가능 O(1)
- 탐색은 O(n)이다.
vector와 array의 차이점
- array는 크기가 고정되어 있어 있어서 요소들을 삽입하거나 삭제할 수 없고, 그 요소들은 모두 같은 자료형을 갖습니다.
- vector는 크기를 동적으로 조절합니다. 순차적이지만 요소로의 접근을 포인터로 하기 때문에 속도 측면에서는 느릴 수 밖에 없습니다.
vector에서의 push_back, emplace_back의 차이점
- push_back은 전달 받은 객체를 임시로 복사나 이동하여서 값을 생성, 삽입합니다.
- emplace_back은 생성에 필요한 인자들을 받아서 내부에서 값을 생성, 삽입을 한다. 임시 객체가 생성되지 않습니다.
- C++17에서부터는 emplace_back을 사용하면, 삽입된 요소에 대한 참조를 반환합니다. 이를 사용할때도 사용합니다.
stack
- LIFO (Last In First Out) 구조 : 후입선출의 구조로 제일 최근에 들어온 것이 제일 먼저 나오게된다.
- ctrl+z와 같이 실행 취소 (undo)에도 쓰인다.
- 삭제나 삽입시 시간복잡도 O(1), 이유는 맨 끝에서만 삭제와 삽입을 하기 때문
- 탐색 시간복잡도 O(n), 맨 끝에서부터 하나씩 탐색하기 때문
queue
- FIFO (First In First Out) 구조 : 선입 선출의 구조로 먼저 들어왔던 것이 제일 먼저 나오게된다.
- 선착순이나 대기열에 사용되면 좋다. 먼저들어온 것이 먼저 나가기 때문
- 삭제나 삽입시 시간복잡도 O(1), 먼저 들어왔던 것을 삭제하고 맨 뒤쪽에 데이터가 들어오기 때문
- 탐색 시간복잡도 O(n), 들어온 순서대로 탐색을 쭉하기 때문
priority_queue
- 가장 큰 것이 우선순위로 데이터가 나오게 됨
- 최대 힙의 구조로 되어있음
- 삽입, 삭제 : 시간복잡도 O(log n)
heap
- 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙'
- 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'
- 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립한다.
- 탐색, 삽입, 삭제 : 시간복잡도 O(log n)
- 완전이진트리에서 부모노드와 자식노드의 최대최소를 비교하여 바꾸어 주는 트리구조이다.
- 우선 순위 큐에서 사용
완전이진트리
- 부모노드가 자식을 두개만 갖는다.
- 레벨별로 왼쪽에서부터 채워 나가며 한 레벨이 다 채워져야만 다음 레벨을 채울 수 있다.
- 삭제는 최하위노드 오른쪽에서부터 레벨별로 삭제해준다.
- 왼쪽과 오른쪽를 가르키는 노드를 만들어서 구현한다.
이진탐색트리
- 부모노드보다 작으면 왼쪽 크면 오른쪽으로 자식들이 정해진다.
- 부모노드가 자식을 두개만 갖는다.
- 계속 크거나 작은 자식만 생길경우 한 쪽으로 노드가 쏠릴 수 있다. 그렇기에 탐색 속도가 O(n)이다.
- 전위순회, 중위순회, 후위순회가 있다.
전위순회
- 트리를 복사할때 쓰인다. 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문입니다.
- 부모노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리를 순회한다.
중위순회
- 중위 순회는 오름차순 또는 내림차순으로 값을 가져올 때 사용됩니다.
- 왼쪽 서브트리 -> 부모노드 -> 오른쪽 서브트리를 순회한다.
후위순회
- 후위 순회는 삭제에 쓰인다. 부모노드를 삭제하기 전에 자식노드를 삭제해야되기 때문
- 왼쪽 서브트리 -> 오른쪽 서브트리 -> 부모노드
균형 이진탐색트리
- 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하도록 하는 트리이다.
- AVL트리, 레드블랙트리, B트리가 있다.
AVL트리
- 왼쪽과 오른쪽의 서브트리 높이 차이가 1이하인 트리.
- 균형을 유지 하는방법은 LL, LR, RR, RL이 있으며 균형인수(Balance factor)를 구성한다.
- 균형인수는 현재 노드가 왼쪽층 - 오른쪽층이 -1~1의 값이 되어야 한다.
- 높이를 logn으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logn)입니다.
레드블랙트리
- 노드는 레드 또는 블랙이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드는 블랙이다.
- 레드 노드의 자식은 모두 블랙이다. (연이은 레드가 올 수 없다.)
- 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 있다.
- 새 노드를 레드로 칠한다.
- 이 규칙을 지키기위해 Restructuring, Recoloring가 있다.
- 부모의 형제가 블랙일 경우 Restructuring을 하고 레드일 경우 Recoloring을 한다.
map
- map은 각 노드가 key와 value 쌍으로 이루어진 트리입니다.
- 중복된 데이터를 허용하지 않습니다.
- 탐색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성되어 있습니다.
unorderd_map
- unordered_map은 해쉬테이블로 구현한 자료구조로 탐색, 삽입, 삭제 시간복잡도는 O(1)입니다.
- 중복된 데이터를 허용하지 않습니다.
- 데이터가 많은 경우에는 unordered_map 이 map 보다 성능면에서 유리합니다.
- 문자열을 키로 사용하는 경우 문자열이 길어질 수록 unordered_map 이 map에 비해 더 성능이 떨어질 수 있습니다.
- key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있습니다.
해시충돌
- 해시충돌에는 두가지 해결 방안이 있다. 열린 주소방법, 닫힌 주소방법이다.
열린 주소방법
- 선형조사 : 충돌이 일어난 바로 뒷 자리로 값을 넣어준다. 이외에 이중해싱, 재해싱이 있다.
닫힌 주소방법
- 체이닝 : 해시 테이블 자체는 포인터 배열로 만들고 같은 버켓의 해당하는 데이터들은 체인 형식으로 만들어(링크드 리스트) 연결하는 방식.
그래픽스
그래픽스 파이프라인
그래픽스 파이프라인 순서도
IA - VS - HS - TS - DS - GS - SO (3D처리)
- RS - PS - OM (2D처리)
IA (Input Assembler)
- 사용자의 Input을 관리한다. Input은 Vertex Data(정점)등이 들어가게 된다.
VS (Vertex Shader)
- 정점의 처리, 노말공간이나 탄젠트공간을 월드(world)공간로 변환시킨다.
HS (Hull Shader) - tessellation
- 선분을 어떻게 쪼갤 것인가 무게중심이 어디가 될 것인가를 판단하여 선을 나눠놓는다.
TS (Tesellation Stage) - tesellation
- HS에서 어떻게 쪼갤것인가에 대한 판단한 것대로 선을 쪼갠다.
DS (Domain Shader) - tesellation
- HS와 TS에서의 입력을 기반으로 출력 패치의 쪼개어진 지점의 정점위치를 계산한다.
GS (Geometry Shader)
- 인접 한 정점과 함께 삼각형, 선 및 점의 전체 기본 형식을 처리 합니다.
SO (StreamOutput)
- 앞에서 처리한 결과를 다시 IA로 return하거나 cpu로 전달해줌 (재계산이 필요할 때 쓰임)
RS (RasterizingStage)
- 3D공간을 2D공간으로 변환시켜줌 (Viewport있음)
PS (PixelShader)
- 기본 형식에 대한 보간된 데이터를 받고 색과 같은 픽셀 별 데이터를 생성 합니다.
OM (Output-Merger Stage)
- 다양한 유형의 출력 데이터 (픽셀 셰이더 값, 깊이 및 스텐실 정보)를 렌더링 대상의 내용과 깊이/스텐실 버퍼의 내용과 결합하여 최종 파이프라인 결과를 생성합니다.