직접 만들어보는 std::vector 클래스 선행 * 이 코드는 동적 배열을 모방한 것이다. [C++] STL - vector vector 라이브러리 선행 * vector 라이브러리는 STL 중에 하나이다. [C++] STL - Standard Template Library STL - Standard Template Library STL * C++에서 제공하는 표준 라이브러리이다. * STL을 사용해 기본적인 자료구조 licktwice.tistory.com 코드 #include #include using namespace std; template class Vector { public: Vector() { } ~Vector() { if (_data) delete[] _data; } void push_ba..
해시 테이블 Hash Table 1편이 있어용 해시 테이블 Hash Table * 해시 테이블이 시간 복잡도 O(1)을 가지기 위해서는 해시 값과 인덱스가 쉽게 매칭이 되어야 한다. * 하지만 해시 값의 중복이나 인덱스의 중복으로 인해 둘의 관계가 직관적이지 못 할 수 있다. 해시 값의 중복 1. 상황에 맞는 해시 함수 선택 해시 함수에 따라 중복 확률이 다르며 같은 해시 함수라도 자료형이나 크기에 따라 중복되는 확률이 다르다. 상황에 맞는 해시 함수를 선택하는 것만으로 충돌을 많이 피할 수 있다. 1-1. 하지만 완벽하지는 않다. 상황에 맞는 해시 함수를 선택한다 해도 해시 함수는 어쩔 수 없이 중복이 생기는 함수이다. 다른 해결책과 같이 사용하는 것이 좋다. 1-2. 완벽할 수도 있다. 해시 함수에 ..
후위표기법 (Postfix Notation) 후위표기법이 필요한 이유 * 우리가 사용하는 사칙연산 공식이 중위표기법이다. (2+6/2)+10*3 * 딱 보면 컴퓨터가 이해하기 힘들어 보인다. 컴퓨터가 이해하기 쉽게 도와주는 방법이 후위표기법을 쓰는 것! 어떻게 바꾸는데? * 다른 곳에서 보세여 ㅎㅎ (설명 잘한 곳이 너무 많아서 의욕을 잃음..) 필요 개념 * 기본적인 C문법 + 스택만 알면 만들 수 있다. 스택 만들기 #define _CRT_SECURE_NO_WARNINGS #include #define STACK_SIZE 256 char stack[STACK_SIZE]; int top = -1; void push(char num) { if (top >= STACK_SIZE) { printf("\nst..
연결 리스트 Linked List 개념 * node라는 구조의 집합니다. * node = 값 + (다음 노드를 향하는 포인터)로 구성되어 있다. [값 + 포인터] 구조가 갖는 장점 * 포인터가 다음 값의 위치를 알고 있으니 배열처럼 메모리가 빈틈없이 연속적일 필요가 없음. = 자료들이 산재해 있다. * 자료들이 여기저기 떨어져 있다면? = 동적 할당 (아닐 수도 있지만 보통 동적) * 연결 리스트에 최대 길이 따윈 없다! = 포인터로 다음 값을 알아낸다 -> 메모리에 값이 분포될 수 있다 -> 최대 크기 설정이 없다 node의 구조 typedef struct node{ int num; struct node* next; }node_t; * 가볍게 보면 어지러울 수 있다. 천천히 구조를 생각하자 * node..
