Coding StudyRoom

C++ 에서 제공하는 map은 데이터를 정렬하여 저장. unordered_map은 정렬을 하지 않고 저장. unordered_map의 자료구조는 "해시 테이블"이다. : 좋은 경우 탐색 시간복잡도 O(1)이다. hash_function("key") : 해시함수에 key값을 대입하면 해시 테이블의 인덱스를 반환해줌 -> 이러한 인덱스를 가지고 배열로 구성된 hash table의 value 값에 상수시간 내에 접근가능. #include 선언 C++ STL 이기 때문에 using namespace std; 생성 unordered_map 변수명; ex) unordered_map um; 1. 삽입 insert( {key, value} ) , insert(make_pair(..

HashTable이란? - >> Key값과 Value 값으로 데이터를 저장하는 자료구조. 내부적으로 배열을 이용하여 구현하기 때문에 빠른다. (상수 시간내에 찾을 수 있다.) Key 값을 해시 함수에 매개변수로 입력하여 Value 값이 저장된 배열의 인덱스 값을 찾는다. ex) hash_function(Key) --> return index array[index] = Value 해시 함수에서 중요한것! 고유한 인덱스 값을 설정하는 것이 매우 중요 즉, 해시 함수 구현이 중요하다. - 해시 함수는 주로 해시 테이블의 크기로 모듈로(%) 연산을 사용한다. 이 외에도 다양한 방법 가능. ** 해시 값이 충돌하는 경우 ** 해시 값이 충돌할 때 해결 방안 Separate Chaining 버킷에 Value만 저장..

보호되어 있는 글입니다.

희소행렬이란? 정확한 정의는 없지만 행렬의 원소의 대부분이 0인 행렬 -> 2D matrix로 표현시에 불필요한 메모리의 낭비가 심하다. C에서 구조체를 사용하여 값으로 0이 아닌 값들만 표현이 가능 각 배열의 0번째 index의 값은 총 행, 열, 값의 수를 나타낸다. #include #include // sparse matrix typedef struct { int row;// index of row int col;// index of col double val;// value }term; // a[i,j] -> b[j,i] void transpose(term a[], term b[]) { int i, j; int curb;// current index of b b[0].row = a[0].col; ..

1번째 index부터 앞의 값들을 순차적으로 탐색하며 정렬 #include #include template void insertionSort(T arr[], const int size) { for (int i = 1; i = 0 && tmp < arr[j]; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } }

#include #include #include #define MAX_ROW 13 #define MAX_COL 17 #define START_POINT 0 #define END_POINT 0 #define MAX_STACK_SIZE (MAX_ROW - 2) * (MAX_COL - 2) #define EXIT_ROW (MAX_ROW - 2) #define EXIT_COL (MAX_COL - 2) // declaration of maze -> // if maze[row][col] == 0 path // else if maze[row][col] == -1 block short maze[MAX_ROW][MAX_COL] = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,START_PO..