조규진의 스터디 블로그

오늘은 RBT(Red Black Tree) vs 힙 에 대해서 알아 보겠습니다. 1. RBT은? Red Black Tree라고 하며 이진 탐색 트리에 문재점을 고치기 위해 탄생한 기법입니다. 이진 탐색 트리가 한쪽에 치우쳐져있으면 시간 복잡도가 매우 증가하는 모습이있습니다 (기존의 시간 복잡도가 O(logN) 에서 O(N)으로 되는 현상). 이런 경우를 대비하기 위해 레드-블랙 트리가 탄생하였습니다. 레드-블랙 트리는 이진 탐색 트리에 항상 넣을때와 뺄때, 그리고 순회할때 모두 O(logN) 을 만족합니다. 원리를 간단하게 설명하면 Red 와 Black으로 노드의 색을 칠하고 데이터를 넣을때와 뺄때 Restructuring과 Recoloring라는 추가 프로세스로 진행하여 균형을 맞춥니다. "루트 부터 ..

오늘은 쿼드 트리 & 옥 트리 에 대해 공부하도록 하겠습니다. 1. 트리란? 나무를 거꾸로 놓아듯한 자료구조이다. 대표적인 비선형 자료구조의 하나로 이진 트리 즉 트리의 데이터가 완전이진트리가 되면 탐색 시간이 매우 감소한다. 트리의 대표적인 특성으로는 최소 1개 이하의 부모노드를 가지고 있다.(루트 노드는 부모가 없다) 1개의 노드가 여러개의 자식을 가질수 있다.(리프 노드는 자식이 없다) (리프 노드란 : 맨 끝에 있는 노드) 대표적인 비선형 자료구조 선형 : 리스트, 배열, 원형 큐 등 비선형 : 트리, 그래프 트리에는 이진 트리, 비 이진 트리가있다. 이진 트리에는 이진 탐색 트리, 레드 블랙 트리가 있으며 비 이진 트리에는 쿼드트리, 옥트리 등이 있다. 2 쿼드 트리란? 사진 분할 트리라 하며 ..

오늘은 해쉬 테이블(Hash Table) 에 대해 공부 하도록 하겠습니다. 1. 해쉬 테이블 이란?? 해쉬 테이블은 키(Key) 에 데이터 값(Value) 를 저장하는 자료 구조 입니다. 키를 통해 데이트 값을 찾아 주기 때문에 값을 읽는속도가 매우 빠릅니다. O(1) 파이썬의 딕셔너리(Dictionary), C++의 Unorderd_map이 대표적인 해쉬 테이블 자료구조 예시입니다. 따라서 파이썬, C++은 따로 해쉬 테이블을 구현 안해도 괜찮습니다. 2. 해쉬 테이블 용어 정리 해쉬(Hash) - 임의 값을 고정 길이로 변환하는 것 해싱 함수(Hash Function) - Key를 해쉬 값(Value)으로 저장되는 주소값으로 바꾸기 위한 수식 해싱(Hashing) - 키 값을 해시 함수라는 수식을 대..

오늘은 C++의 템플릿에 대해 공부하도록 하겠습니다. 템플릿 이란? C++에서 제공해주는 기능으로 함수나 클래스를 개별적으로 다시 작성하지 않아도, 여러 자료 형으로 사용할 수 있도록 하게 만들어 놓은 틀 입니다. 템플릿은 두가지로 함수형 템플릿 과 클래스형 템플릿 으로 나눠집니다. 템플릿은 말 그대로 자료형에 따라 함수를 여러번 정의할 필요없이 template를 함수 위나 클래스 위에 정의하고 사용하면 인자값을 전달할때 그거에 맞는 매개변수로 자료형으로 변환해주는 기법입니다. 함수 템플릿(Function Template) 함수를 만들어 낼때, 함수의 기능은 명확하지만 자료형을 모호하게 두는 것 아래의 코드를 보면서 설명하겠습니다. int sum(int a, int b) { return a + b; } ..

오늘은 C++의 STL의 장단점을 공부하도록 하겠습니다. STL이란? STL(Standard Template Library)는 C++의 표준 라이브러리를 지원합니다. 이 라이브러리를 이용하여 특정 기능을 작성하지 않고 제공되는 함수를 통해 손쉽게 기능을 구현할 수 있습니다. STL은 사전적으로 표준 템플릿 라이브러리이며 C++의 템플릿을 사용하고 있으므로 하나의 코드로 여러 결과를 보여줍니다. ex) vector v 벡터 자료구조에 int형으로 선언 STL의 기본 개념은 이미 구현되어 있는 공통적인 기능을 쉽게 사용하는 것 입니다. STL 장/단점? 그럼 이러한 STL의 장단점은 무엇일가요? 장점 단점 일반화를 지원합니다. 하나의 단일 알고리즘으로 여러 개의 컨테이너에 대해 동일한 작업이 가능합니다. 템..

오늘은 C++의 인터페이스(Interface)의 개념을 공부하도록 하겠습니다. c++의 인터페이스 사실 c++에는 인터페이스 라는 키워드가 없습니다. Java는 인터페이스라는 키워드를 사용하는 것이 있고 또한 abstract라는 키워드를 사용하여 추상 클래스를 정의합니다. 하지만 c++은 그러한 키워드는 없고 개념만 가지고 있는 상태입니다. 보통 가상 함수 즉 virtual을 사용하여 오버라이딩을 기대하며 기반클래스에서 사용하는 방법을 다들 알고있을겁니다. 거기에 virtual함수 를 =0을 주면 pure virtual함수로 만들수 있다는 것도 알고 있습니다. 이것이 추상클래스라는 것도 알고있고요 virtual함수나 pure virtual함수에 대해 공부가 안되신 분들은 아래에 내용을 참고해서 공부해주시..

오늘은 가상상속에 대해서 공부하도록 하겠습니다. 가상 상속이란??? C++에는 다중 상속을 지원하지만 JAVA는 다중 상속을 지원하지 않습니다. 다중상속에는 장점도 있지만 매우 큰 단점이 하나 있습니다. 장점은 객체에 재사용성을 즉 상속성을 좀더 유연하게 만들어 줄수 있습니다. 하지만 단점으로는 다이아몬드 상속 구조를 사용할 경우 매우 큰 성능 저하 및 메모리의 낭비가 올수 있습니다. 아래의 그림을 보시면 다이아 몬드 상속을 대표적으로 보여주고 있습니다. 이러한 상속 구조가 될경우 B나 C는 A를 포함하여 메모리상에 올리며 매우 좋은 상속 구조를 가질수 있지만 D같은 경우는 B 랑 C를 상속을 받지만 결국 B 랑 C는 A를 상속 받고 있기 떄문에 D는 메모리 구조상 A를 두번 할당을 받습니다. 또한, 생..

오늘은 UTF-8 과 UTF-16의 차이점을 공부해보겠습니다. 먼저 UTF의 개념을 이해하기 전에 유니코드의 개념을 이해해야 합니다. 유니코드 유니코드는 다국어를 지원하는 프로그래밍을 하다보면 가장 먼저 접하는 어려움입니다. 컴퓨터의 언어는 0과 1로만 이루어 져있는데 세상에는 무수한 언어가 존재합니다. 컴퓨터 내에서 무수한 언어를 표현하기 위해 나타난 기법입니다. 일단 유니코드라는 용어의 개념은 숫자와 글자, 즉 키와 값이 1:1로 매핑된 형태의 코드입니다. 예를들어 ASCII Code로 0x41 = A로 매핑된 것 처럼, 아스키코드로 표현할 수 없는 문자들을 유니코드라는 이름 아래 전세계의 모든 문자를 특정 숫자(키)와 1:1로 매핑한 것 입니다. UTF란? UTF는 유니코드 문자를 인코딩 하는 방식..

오늘은 컴파일의 과정을 알아보도록 하겠습니다. 개요 프로그래밍을 하다보면 컴파일이라는 단어를 많이 들어봤을겁니다. 소스 코드를 빌드(Build) 혹은 컴파일(Compile)해서 실행해봤거나 코드를 잘못 작성하여 컴파일 에러가 났던 경험이 있을 겁니다. 정확하게 컴파일이 어떠한 일을 하는지 모르고 막연하게 "컴파일을 하면 소스 코드의 문법을 검사하고 실행하나 보다" 라는 생각이 들었으면 이참에 자세히 알아보도록 하겠습니다. 정의 컴파일은 인간이 이해할 수 있는 언어로 작성된 소스 코드(고급 언어 : C,C++,JAVA 등) 을 CPU가 이해할 수 있는 언어(저급 언어 : 기계어) 로 변환 하는 작업을 말합니다. 우리가 소스코드를 작성할때는 인간이 이해할수있는 영어로 작성을 하지만 컴퓨터는 이것을 이해를 절..

오늘은 퐁 모델에 대해 공부하도록 하겠습니다. 퐁 모델은 총 4가지 항의 합으로 이루어집니다. Diffuse, Specular, Ambient, Emissive 입니다. 각각 난반사, 정반사, 간접조명, 자체 발산광이라고 보시면 됩니다. 또한 조명 용어도 정리하겠습니다. 조명 용어 정리 지역 조명(local illumination) -광원(light source)로 부터 직접적으로 물체에 들어오는 빛만을 고려합닌다. 전역 조명(global illumination) - 광원이 직접적으로 보이지 않더라도 공간 내 다른 물체에서 반사된 빛에 의해 받는 간접 조명 을 고려하여 모든 물체를 잠재적인 광원으로 취급합니다. - 비실시간 렌더링에 주로 사용되며 현재는 하드웨어 성능의 향샹으로 실시간 랜더링이 가능해지는..