해시 테이블 Hash Table 1편이 있어용 해시 테이블 Hash Table * 해시 테이블이 시간 복잡도 O(1)을 가지기 위해서는 해시 값과 인덱스가 쉽게 매칭이 되어야 한다. * 하지만 해시 값의 중복이나 인덱스의 중복으로 인해 둘의 관계가 직관적이지 못 할 수 있다. 해시 값의 중복 1. 상황에 맞는 해시 함수 선택 해시 함수에 따라 중복 확률이 다르며 같은 해시 함수라도 자료형이나 크기에 따라 중복되는 확률이 다르다. 상황에 맞는 해시 함수를 선택하는 것만으로 충돌을 많이 피할 수 있다. 1-1. 하지만 완벽하지는 않다. 상황에 맞는 해시 함수를 선택한다 해도 해시 함수는 어쩔 수 없이 중복이 생기는 함수이다. 다른 해결책과 같이 사용하는 것이 좋다. 1-2. 완벽할 수도 있다. 해시 함수에 ..
해시 Hash 해시란? Hash~ * 해시는 해시 함수와 함수에서 나온 해시 값이 있다. 해시 함수에 매개변수로 들어가는 값은 크기와 자료형에 구애를 받지 않는다. 반환되는 해시 값은 의도적으로 고정된 길이의 데이터로 바뀐다. * 부동소수점형이나 길이가 고정되지 않은 문자열 등을 언제나 정수형으로 바꾸는 함수를 해시함수라고 할 수 있다. * 데이터 → 해시 함수 → 해시 값 * 해시 함수는 특정 값을 넣으면 언제나 같은 값을 반환한다. a를 넣어서 b가 나온다면, a를 몇 번을 넣어도 언제나 b가 나온다. * 하지만 a를 넣어도 b가 c를 넣어도 b가 나올 수 있다. 이는 매개변수의 폭은 넓은데 반환값은 고정된 크기로 바뀌는 데에서 기인한다. 해시를 사용해서 좋은 점 * 해시 함수를 사용하여 임의의 데이..
연결 리스트 Linked List 개념 * node라는 구조의 집합니다. * node = 값 + (다음 노드를 향하는 포인터)로 구성되어 있다. [값 + 포인터] 구조가 갖는 장점 * 포인터가 다음 값의 위치를 알고 있으니 배열처럼 메모리가 빈틈없이 연속적일 필요가 없음. = 자료들이 산재해 있다. * 자료들이 여기저기 떨어져 있다면? = 동적 할당 (아닐 수도 있지만 보통 동적) * 연결 리스트에 최대 길이 따윈 없다! = 포인터로 다음 값을 알아낸다 -> 메모리에 값이 분포될 수 있다 -> 최대 크기 설정이 없다 node의 구조 typedef struct node{ int num; struct node* next; }node_t; * 가볍게 보면 어지러울 수 있다. 천천히 구조를 생각하자 * node..
스택 Stack 개념 * Last in first out. 가장 먼저 들어간 자료가 가장 나중에 나오는 구조이다. 제약 * 입구가 하나인 형태로 자료가 차곡차곡 쌓인다. * 가장 위에 자료만 접근 가능하다. (중간이나 밑에서 자료 접근 불가) 삽입 * 가장 위에 자료를 올려두면 됨. Push라고 함. * 시간 복잡도 = O(1) 제거 * 가장 위에 자료를 제거하면 됨. Pop이라고 함. * 시간복잡도 = O(1) 검색 * Push와 Pop만 할 줄 아는 스택에서 검색은 정신 나간다. 1. 원하는 걸 찾을 때까지 Pop을 한다. (Pop 데이터는 다른 곳에 저장) 2. 원하는 걸 찾았다면 다시 차곡차곡 쌓는다. * Pop 하는 데에 O(n), 원하는 자료는 찾았으면, Push 하는 데에 O(n) * 시간 ..
