선형 vs. 비선형선형 구조는 자료를 순차적으로 나열한 형태이다ex. 배열, 연결 리스트, 스택/큐 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태이다ex. 트리, 그래프 배열장점: 연속된 데이터로 임의 접근 가능단점 1: 배열의 크기 변경 불가단점 2: 중간 삽입/삭제 매우 비효율 동적배열장점 1: 연속된 데이터로 임의 접근 가능장점 2: 배열의 크기 변경 가능단점 1: 배열의 크기를 변경하는 경우, 전체 데이터를 복사해야 하는 부담단점 2: 중간 삽입/삭제 매우 비효율단점 1의 해결책: 배열의 크기가 변경되는 경우에어느정도 더 크게 (1.5배 or 2배) 생성해서 배열의 크기가 증가될수록 배열의 크기 변경 횟수를 최소화하도록 내부적으로 작동 연결리스트장점: 중간 삽입/삭제 매우 효율단..
오른손 법칙을 미로에 적용한 코드는 아래와 같다void Player::Init(Board* board){ // 초기 설정 _pos = board->GetEnterPos(); _board = board; Pos pos = _pos; _path.clear(); _path.push_back(pos); Pos dest = board->GetExitPos(); // 우아한 코드를 위한 배열 Pos front[4] = { Pos { -1, 0}, // UP Pos { 0, -1}, // LEFT Pos { 1, 0}, // DOWN Pos { 0, 1}, // RIGHT }; // 목적지 도착까지 계속 반복 while (pos != dest) { // 1. 현재 바라보는 방향을 기..
Big-O 표기법 사용이유알고리즘의 성능 비교를 위해 Big-O 표기법을 사용한다 Big-O 표기법 사용법1단계. 대략적인 계산2단계. 최고차항 계수만 남기고 상수도 버린다 Big-O 표기법 사용법 예시int Add(int n){ return n + n;}// O(1) int Add2(int n){ int sum = 0; for(int i = 0; i int Add3(int n){ int sum = 0; for(int i = 0; i int Add4(int n){ int sum = 0; for(int i = 0; i O(N^2) Big-O 표기법 그래프 log 함수로그 함수는 매번 절반 씩 줄어드는 것이 핵심이다또한, 프로그래밍에서 밑은 대부분 2이기 때문에 ..
TLSTLS는 스레드 개인 공간으로 공용 영역(Global, Heap)에서 본인이 작업할 데이터들을 어느 정도 끌고 와서 TLS에 저장하고 그와 관련된 작업을 처리한다이렇게 하면,매번 공용 영역을 사용할 때 Lock을 걸고 해제하는 것이 아닌 공용 영역의 적당한 크기의 데이터들을 TLS로 들고오거나 반환할 때만 Lock을 걸고 해제하니 효율적이다 TLS vs. Stack스택과의 차이점은 스택은 함수에 의한 메모리이기에함수가 종료되면 스택 프레임이 정리되고 사라지는 불안정한 메모리이다따라서, 스택에 영구적인 데이터를 저장하는 것은 위험하다그래서 영구적인 데이터인데이터 영역(전역, static 변수)과 Heap 영역의 데이터를저장하는 각 스레드만의 개인적인 공간이 바로 TLS이다 예시 코드int32 GVa..
C++ 11 메모리 모델C++ 표준 자체가 싱글스레드 환경을 염두에 둔 모델이다그러다 보니 멀티스레드 환경에서 작업을 하기 불편했다그래서 C++ 11에 메모리모델이 확립되면서멀티스레드 환경도 프로그래밍하기 편해졌다 멀티스레드 환경의 문제 (복습)여러 스레드가 동일한 메모리에 동시 접근 (대표적으로 write 연산)-> Race Condition (경합 조건) 발생 -> Undefined Behavior (정의되지 않은 행동) 이러한 상황의 해결책은Lock (mutex)을 이용한 상호 배타적 (Mutual Exclusive) 접근을 하거나Atomic (원자적) 연산을 이용하는 것이다C++ 원자적 연산의 절대법칙Memory Model을 학습하기 전C++에서 원자적 연산의 절대 법칙을 알고 가는 것이 좋다"a..
캐시RAM에서 미리 사용할 데이터들을 예측해서 CPU에 가까운 캐시에 저장해 둔다따라서, 데이터를 찾을 때바로 RAM에서 찾아보는 것이 아닌 캐시를 가서 확인해 보고 캐시에 있는 경우 (캐시 히트)에는 캐시에서 데이터를 찾아온다 캐시 예측 방식 - 시간 지역성 최근에 찾아본 데이터들을 다시 찾을 확률이 높다 - 공간 지역성 찾아본 데이터들 근처의 데이터를 찾을 확률이 높다 CPU의 캐시 활용 실제 코드 예시#include int32 buffer[10000][10000];int main(){ memset(buffer, 0, sizeof(buffer)); { uint64 start = GetTickCount64(); int64 sum = 0; for (int32 i = 0; i 2차원 배열을 순서대..
Future계속 사용해야 하는 Event는 CV를 활용하면 되지만단발성 Event인 경우는 CV를 사용하기엔 너무 과하다thread를 만들고 cv변수를 만들고 해당 변수의 멀티스레드에서 활용되면 lock도 관리해주어야 한다 따라서간단하게 사용하기 위해 Future가 도입되었다 Future 예시#include int64 Calculate(){ int64 sum = 0; for (int32 i = 0; i future1 = std::async(std::launch::deferred, Calculate); std::future future2 = std::async(std::launch::async, Calculate); int64 sum1 = future1.get(); int64 sum2 = futur..
Condition VariableEvent의 발전된 버전이다Event 보단 Condition Variable을 거의 대부분 사용한다 mutex랑 짝을 지어 사용하는 방법을 알아볼 것이다그 외에 condition_variable_any를 사용하는 방법도 있다#include conditon_variable cv;#include condition_variable_any cva; Event vs Condition Variablecondition_variable은 Event처럼 커널 오브젝트가 아닌 유저(레벨) 오브젝트이다커널 오브젝트는 여러 프로그램에서 사용 가능하고유저 오브젝트는 하나의 프로그램 내에서만 사용 가능하다는 특징이 있다참고로, 게임서버는 여러 프로그램에서 교류를 하지 않기에딱히 해당 특성을 이용..
EventEvent는 Lock에서만 활용되는 것뿐 아니라다양하게 사용된다앞서 Lock 구현이론에서 보았듯이 Event는 누군가에게 부탁을 해서 빈 상태가 되면 전달을 받는 방식이다여기서 누군가는 바로 커널 영역으로커널 영역에게 부탁을 하는 것이다Auto Reset Event vs. Manual Reset Event C#은 두 개의 클래스가 구분된다C++은 인자에 따라 구분된다둘의 차이는 이 글의 맨 마지막 부분에서 다룬다 Event 흐름Event는 단순하게 boolean 값으로사용 중이던 스레드가 나가면서 자물쇠를 열고 이벤트를 켜준다그러면, 기다리는 스레드가 이벤트가 켜진 것을 확인하고 본인이 들어간다 예시코드 - Event 미사용#include mutex m;queue q;void Producer()..
