CS

[C++] 계단 오르기 알고리즘

예로 들어서 n이 3이라면 꼭대기에 도달 하는데까지 총 3가지의 방법이 존재한다. 다른 예시로는 n = 1 // 한 가지의 방법만 존재하므로 1을 출력 n = 2 // 2, (1 , 1)과 (2) n = 4 // 5, (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2) 재귀를 사용한 방식 방법의 수(n) = 방법의 수(n - 1) + 방법의 수(n - 2) 피보나치 수열을 이용하여 구할 수가 있다. 방법의 수(1) = 피보나치(2) = 1 방법의 수(2) = 피보나치(3) = 2 방법의 수(3) = 피보나치(4) = 3 int fib(int n) { if (n

세션의 생성과 관리

세션이란, 멀티 player 게임의 1 개의 인스턴스이다. 1 개의 세션에는 동시에 플레이 하는 복수의 사용자가 존재해, 각각이 자신의 컴퓨터상에 게임 클라이언트를 가지고 있다. player란, 게임안의 엔티티여, 각 게임에서 정의한다. 각 사용자가, 1 개의 게임에 복수의player를 가지는 경우도 있다. 다만, 게임 애플리케이션은, 개별의 Microsoft® DirectPlay® 인터페이스 또는 각 player의 개체를 사용해, 이러한 player를 애플리케이션 자신으로 관리해야 한다. 세션 생성의 최초의 순서는, 사용자 그룹의 수집이다. 이 때문에는, 2 개의 기본적 방법이 있다. 많은 게임 세션은, 리모트 컴퓨터로 실행되는로비 애플리케이션에 의해 준비된다. 이 방법은, 많은 인터넷 베이스의 게임에..

sort() 함수에서 쓰여지는 정렬 알고리즘 (Intro 인트로, Tim 팀)

일반적으로 시간 복잡도를 기준으로 sort 알고리즈므이 성능을 판단하지만, 실제로는 지역성이나 실 데이터의 분포 등 고려할 것들이 많다. 언어마다 default로 사용하는 sort들이 정해져있다. C++ : Intro Sort c++의 std::sort로 사용되고 퀵 정렬, 삽입 정렬, 힙 정렬로 이루어져 있다. 특징 기본적으로 퀵 정렬로 시작을 한다. 정렬할 element가 Threshold(일반적으로 16) 미만일 때는, 삽입 정렬로 수행된다. 재귀 depth가 정렬되는 element 수(n)과 비교해 log N보다 많아지면 힙 정렬로 수행된다. 퀵, 삽입 정렬은 지역성의 이점을 얻는 알고리즘(배열의 경우)으로 유명하다. 특히, 삽입 정렬은 참조 지역성을 아주 잘 만족한다고 한다. 삽입 정렬의 경우 ..

[C++] Radix Sort (기수 정렬)

기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이기에 시간 복잡도가 O(n)이다. 구체적인 정렬 법을 알기 전에 이름인 '기수'가 뭔지 부터 알아보자. 여기서 '기수'라는 것은 '자릿수'를 의미한다. 자릿수로 뭘 어떻게 하는 것일까?? 방법은 다음과 같다. 1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬이된다. 2. 1)에 의해서 정렬된 배열에서, 10의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 3. 2)에 의해서 정렬된 배열에서, 100의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 4. 최대 자릿수까지 계속해서 반복한다.. 구체적인 과정을 알아보자. 먼저 최대자릿수 까지 위의 과정을 반복해야 하므로 우리는 최대..

[C++] Trie (트라이) 소스코드

trie.h #ifndef TRIE_H #define TRIE_H #include #include #include #include #include #include #include #include #include namespace trie { struct SetCounter { }; namespace detail { template struct TrieNode : public PrefixHolderT { private: typedef TrieNode self_type; typedef self_type * self_pointer; self_pointer * data = nullptr; uint32_t size = 0; /* Will still be 64 bit due to alignment */ public..

Debug - Release 차이

보통 C++로 코드 작성 후 결과물을 실행 파일로 만들기 위해서는 빌드 작업을 해야만 한다. 이때 Visual Studio와 같은 IDE에서는 Debug 또는 Release 빌드 모드를 선택할 수 있다. 이는 사실 C/C++ 컴파일러의 최적화 옵션의 차이인데, Visual Studio에서는 편의를 위해 빌드 모드를 분리해놓은 것이다. 현업에 종사하거나 숙련된 개발자는 당연히 이 차이를 알고 있겠지만, 주로 C/C++ 개발을 처음 접하는 분들, 특히 학생들은 Visual Studio 기본값인 'Debug'로 빌드해서 배포를 하는 경우가 종종 있다. 잘못된 빌드 모드로 배포할 경우 성능 저하가 발생하거나 프로그램 실행 불가 등의 문제로 상당히 고생할 수 있으므로 각 빌드별 특징을 잘 알고있어야 한다. 차이점..

[C++] Trie (트라이) 개념과 구현방법

트라이는 "문자열을 빠르게 탐색하게 해주는 자료구조" 이다. 즉, '문자열'을 관리하는 방법 중의 하나다 작동 원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가면서 만들어 진다. 이 과정에서 반복된 재귀 호출이 이루어지는데, 말로는 무슨 말인지 모르겠으니, 이 과정을 구체적으로 알아보자. 먼저, 문자열을 트라이로 생성하는 과정부터 알아보자. 간단하게 순서를 붙여보자면 다음과 같이 진행된다. ( 지금부터 '루트(Root)' 라는 말이 나올 수 있는데, 이는 가장 초기 노드라 생각하면 된다. 즉, 연결되어 있는 어떠한 노드도 없는 초기 노드이다. ) 1. 주어진 문자열에서 현재 문자를 가져온다. 2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐..

[C++] const map 객체에 [key] 접근시 에러

map 클래스의 객체 a가 있고 이 객체가 const 화 되고 b라는 변수로 reference 됐다고 해보자. b에 대한 value 를 접근함에 있어 b["key"] 이런식으로 접근하면 에러가 난다. 내용은 error : passing '~' as 'this' argument discards qualifiers 이하 생략. 이유는 const 화 된 map 객체에 ["key"]로 접근하면 그 값을 수정할 여지가 발생하기 때문이다. value를 접근하는 다른 방법이 있다. 바로 .at를 쓰면 된다 b.at("key") 이렇게 접근하면 에러 없이 const화 된 map 객체의 value에 접근 가능하게된다. #include #include #include #include using namespace std; ..

[C++] vector resize 시 주의할 점

기존보다 더 작게 할당하게 될 경우 만약 1 라는 값을 5 개 가진 벡터를 3 의 크기로 resizing 하며 2 로 채운다면 #include #include using namespace std; void Print_Vec(const vector vec) { for (auto const &it : vec) { cout

Brute Force (브루트 포스) 알고리즘

개념 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 장단점 장점) 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 단점) 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 종류 선형 구조) 순차 탐색 비선형 구조) 백트래킹, dfs, bfs 예시 만약 10자리 비밀번호 자물쇠가 있다고 가정해보자. 이 자물쇠를 풀..