Crat

1-5. 이중 배열 리스트(List) - 구현 복습

0. 필요성 vector가 list에 비해 얻는 편의성이 높기 때문에 대부분 vector를 사용하지만, 앞으로 공부할 자료 구조가 list가 기초가 되기 때문에 연습이 필요하다. 1. vector와 다른점? (1) push_front가 존재 vector는 데이터 수정을 위해서 각 요소를 한칸씩 미는 것이 복사 - 이동의 순서를 거치기 때문에(비효율적) 제공하지 않는 기능이다. (2) 중간 삽입 삭제가 효율적 (3) 이전 / 다음 노드를 가리키는 포인터를 저장 (4) list는 임의 접근이 불가능하기 때문에, 각 노드들을 타고 가서 찾는다 (5) insert가 존재 중간에 삽입하는 insert가 존재한다. insert('삽입 위치의 바로 다음','삽입할 값') // return 값은 반복자이다. 2. No..

1-4. 동적 배열(vector) - 구현 복습

1. 소멸자 소멸자 호출 시에 data 배열을 삭제 2. push_back (1) size와 capacity의 크기가 같게 되면 용량의 확장이 발생 (2) capacity와 새로운 capacity가 동일하면(capacity가 0이었을 때 발생함) 1 증가시켜야 함. (3) reserve 함수를 호출해서 새로운 capacity 값을 전달 (4) _size 인덱스의 값에 매개변수를 전달 (5) size의 크기를 증가시킴 3. reserve (1) 기존의 capacity는 매개변수의 값보다 작을 수 없음(축소불가). (2) capacity 값을 대입 (3) 데이터 복사 전에 새로운 메모리 영역을 capacity로 동적 할당해야함. (4) 새로운 데이터 영역에 기존 데이터를 복사 (5) 기존 데이터 영역 할당 ..

1-3. 배열(array), 동적 배열(vector), 연결 리스트(list) - 복습

1. 배열(array) 배열의 각 데이터를 배열 요소라 하고 배열의 위치를 인덱스라고 한다. (1) 장점 메모리 영역에 연속적으로 존재한다. (2) 단점 배열의 개수를 결정하면 확대 또는 축소할 수 없다. 2. 동적 배열(vector) 배열과 유사하지만 크기(capacity)를 능동적으로 조절할 수 있다. 메모리 영역에 연속적으로 존재한다. 배열 요소(size)가 용량(capacity)보다 많아지면 데이터를 통째로 복사해서 새로운 메모리 영역으로 이동한다. 이 때, 새로운 메모리 영역에서 Capacity는 Size의 크기의 1.5배 ~ 2배이다. (1) 장점 배열의 개수를 능동적으로 확대 또는 축소할 수 있다. (2) 단점 배열 요소가 많아지면(size > capacity) 통째로 다른 영역으로 복사해야..

1-2. 미로 만들기(2) - 오른손 법칙(우수법)

1. 오른손 법칙 미로를 탈출할 때 오른쪽 벽에 손을 대고 벽을 따라가면 언젠가는 탈출한다는 법칙이다. player의 진행방향을 기준으로 오른쪽으로 갈 수 있는지, 바라보고 있는 방향으로 갈 수 있는지 체크한다. (1) player.h #pragma once class Board; class Player { enum { MOVE_TICK = 100 // 100ms 당 한 번 이동하게 설정 }; public: voidInit(Board* board); voidUpdate(uint64 deltaTick); // 프레임마다 이동 voidSetPos(Pos pos) { _pos = pos; } // 위치 변경 PosGetPos() { return _pos; } // 위치 반환 boolCanGo(Pos pos);..

1-2. 미로 만들기(1) - Binary Maze Algorithm

0. 코드 정리 맵을 랜더링하는 코드를 maze가 아닌 board로 관리한다. 1. 맵 만들기 (1-1) Board.cpp - 벽 생성 Binary Tree Maze Algorithm을 따라 size에 해당하는 맵을 만든다. // Binary Tree 미로 생성 알고리즘 // - Mazes For Programmers void Board::GenerateMap() { for (int32 y = 0; y < _size; y++) { for (int32 x = 0; x < _size; x++) { if (x % 2 == 0 || y % 2 == 0) // 첫번째 가로줄과 세로줄은 벽으로 설정 _tile[y][x] = TileType::WALL; else _tile[y][x] = TileType::EMPTY;..

1-1. Maze 구현을 위한 환경설정

0. 자료 구조 Maze.cpp : 메인, 미로 ConsoleHelper.cpp, ConsoleHelper.h : 커서 위치, 색, 콘솔 커서 활성화 pch.cpp, pch.h : Types.h : int 타입 캐스팅을 편하게 하기 위함 * 헤더파일을 포함시킬 때 여러 곳에서 포함되는 헤더파일을 최상위에 include 하여야 한다. 1. 헤더파일 구성 (1-1) ConsoleHelper.h #pragma once #include #include "Types.h" enum class ConsoleColor { BLACK = 0, RED = FOREGROUND_RED, GREEN = FOREGROUND_GREEN, BLUE = FOREGROUND_BLUE, YELLOW = RED | GREEN, WHITE ..

0-0. Big-O 표기법

시간 복잡도를 표현하는 방법. 두 알고리즘 A와 B를 비교하는 방법이다. (어떤 알고리즘이 더 빠른가) 1. 단계 (1) 수행되는 연산(산술, 비교, 대입)의 개수를 대략적으로 판단한다. (2) 가장 큰 차수의 항만 남기고 나머지는 무시한다. ex) 'N^2 + 2N + 1'에서 제곱항만 남기고 나머지는 소거한다. 2. 의의 (1) n-t 그래프 데이터 갯수에 따른 시간 소모에 관한 그래프이다. n = 1,000,000 부터 큰 시간이 소요된다.(n^2 일 때 16.7min, n log n 일 때 19.93ms) 즉, 시간 복잡도가 log n 또는 n에 근접할수록 빠르게 작동한다고 알 수 있다. 3. 표기

10-10. 스마트 포인터

0. 포인터의 문제점 (1) 객체 삭제 이후 더 이상 유효하지 않는 메모리 수정 클래스를 하나 만들고 객체가 다른 객체를 조준하여 공격하는 클래스를 만든다. class Knight { public: Knight(); ~Knight(); void Attack() { if (_target) { _target->_hp -= _dam; cout _target = k2; // k1이 k2를 타겟으로 지정 k1->Attack(); // 공격 수행 // 이후 k2 유저가 접속을 종료함. delete k2; k1->Attack(); } 여기에서 k2 객체를 삭제하고 다시 k1에게 공격명령을 내리면 k1은 k2의 멤버변수였던 _hp의 더 이상 유효하지 않는(엉뚱한) 메모리 영역을 수정하게 된다. 따라서 _target 포..