프로그래밍 기초
-
[C++ 14] 제네릭 프로그래밍 / 추가된 기능과 기억해야 할 내용프로그래밍 기초/C++ 2022. 5. 26. 11:00
제네릭 프로그래밍 함수 템플릿 타입 결정 방법 = 대부분의 경우 암묵적으로 잘 변환되나 int와 unsigned 같이 모호한 경우 명시적으로 결정해 줘야 한다. template TPara max(TPara a, TPara b) { return a > b ? a : b; } unsigned u1 = 2; int i = 3; max(u1, i); // 에러 발생! max(int(u1), i); // Ok max(u1, i); // Ok 자동 리턴 타입 + 컴파일러에서 리턴 타입도 추론이 가능하게 되었다. template inline auto max(T a, U b) { return a > b ? a : b; } 네임 스페이스 네임 스페이스 한정 = 네임 스페이스로 특정 클래스, 변수 등을 선택해 사용할 수 ..
-
[C++ 14] 클래스 / 추가된 기능과 기억해야 할 내용프로그래밍 기초/C++ 2022. 5. 22. 11:32
클래스 생성자 = 단일 인수를 가지는 생성자는 대입 연산자로 생성해도 오버헤드가 발생하지 않는다. class complex { public: complex(double r = 0, double i = 0) : r(r), i(i) {} // ... } complex z4 = 4; // 과거에는 임시 변수를 생성해 오버헤드가 발생한다고 했으나 최신 컴파일러는 문제없이 최적화한다. = 생성자가 여러 개 일 때 다른 생성자를 불러 초기화하는 것을 허용한다. class complex { public: complex(double r, double i) : r{r}, i{i} {} complex(double r) : complex{r, 0.0} {} complex() : complex{0.0, 0.0} {} // ...
-
[C++ 14] C++ 기초 / 추가된 기능과 기억해야 할 내용프로그래밍 기초/C++ 2022. 5. 21. 16:54
C++ 기초 리터럴 + 2진수 표현 접두사가 추가되었다. 접두사 진수 타입 예제 10진수 값 없음 10진수 11 11 0 8진수 011 9 0x 16진수 0x11 17 0b 2진수 0b11 3 + 길이가 긴 리터럴의 자릿수를 표현할 수 있도록 작은따옴표(')로 자릿수 구분이 가능해졌다. long d = 6'546'687'616'861'129l unsigned long ulx = 0x139'ae3b'2ab0'94f3; int b = 0b101'1001'0011'1010'1101'1010'0001; const long double pi = 3.141'592'653'689'793'238'462l; 축소하지 않는 초기화 = 큰 값을 작은 크기의 변수로 초기화할 때 축소 변환하지 않고 오류를 발생시키는 초기화 방..
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 2022. 1. 12. 10:45
동적 프로그래밍 동적 프로그래밍 개념 큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다. 가령 피보나치수열의 경우 다음과 같은 식으로 나타난다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다. 이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다. 가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다. 피보나치수열 알고리즘 fib(n) { if (f[n] ≠ 0) then return f[n]; el..
-
해시 테이블 구현 및 테스트프로그래밍 기초/알고리즘 2022. 1. 7. 17:51
해시 테이블 구현 STL의 vector를 이용하여 해시 테이블을 구현한다. 해시 테이블 기본 클래스 해시 테이블 처리 중 충돌 처리에 따라 함수를 나누기 위해 기본 기능을 가진 클래스를 구현한다. HashTable.h #pragma once #include "../Common.h" #include #include using std::string; /// /// 해시 테이블에서 사용할 해시 함수 /// enum class HashFunction { Division, Multiplication, }; /// /// 해시 테이블의 구성 요소 테스트를 위한 베이스 클래스 /// class HashTable { public: HashTable(HashFunction hashFunction = HashFunctio..
-
해시 테이블 알고리즘프로그래밍 기초/알고리즘 2021. 12. 22. 14:42
해시 테이블 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. ※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다. 해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때..
-
R 트리 알고리즘프로그래밍 기초/알고리즘 2021. 12. 9. 16:48
R 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. R 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 R 트리는 다음의 성질을 갖는다. 루트를 제외한 모든 내부 노드는 └k/2┘ ~ k 개의 영역을 갖는다. 모든 리프 노드는 같은 깊이를 가진다. 모든 레코드는 리프 노드에서만 가리킨다. R 트리의 표현 R 트리는 KDB 트리와 달리 키를 포함하는 최소 영역에만 노드가 존재한다. 아래와 키가 존재할 때 R트리의 표현은 다음과 같다. 이름 key1 key2 A 8 100 B 4 10 C 6 35 D 1 10 E 6 60 F 5 45 G 7 85 H 3 20 I 10 70 J 2..