Data Structure

1. 해시란? Set 자료구조의 특성을 살펴보기 전에 Hash의 개념을 먼저 정리해보겠습니다. 해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 매핑하기 전 입력 데이터의 값을 키(Key), 매핑 후 출력 데이터의 값을 해시코드(HashCode), 매핑하는 과정 자체를 해싱(Hashing)이라 부릅니다. 해시의 특징은 다음과 같습니다. 동일한 입력 값에 대해서는 항상 동일한 출력 값이 보장된다. 출력 데이터 값을 가지고 원본 입력 데이터의 값을 알아낼 수 없다. 일반적으로 해시 함수는 그리 복잡하지 않은 알고리즘으로 구현되기 때문에 CPU, 메모리 자원을 크게 소비하지 않는다. 입력 값의 범위보다 출력 값의 범위가 좁기 때문에 다른 입력 데이터에 대..

1. 개요 배열의 장단점은 다음과 같습니다. 장점 항목 접근 속도가 빠르고 일정하다. 배열의 원소들은 모두 연속된 메모리 위치에 저장되기 때문에 인덱스를 통해 가장 빠르게 원소를 참조하거나 변경할 수 있다. 단점 사용하기 전에 배열 크기를 지정해야하고, 지정한 크기로 고정된다. 정해진 크기를 넘겨서 데이터를 저장하려 한다면, 더 큰 크기의 배열을 새로 할당받아 사용해야 한다. 삽입/삭제가 힘들다. 배열의 중간에 원소를 삽입/삭제할 경우, 나머지 원소들의 연속적인 순서를 맞추기 위해 삽입/삭제가 이루어진 위치 뒤의 모든 데이터들을 모두 한 칸씩 앞으로 당기거나, 뒤로 밀어야한다. 원소들을 모두 옮기는데 드는 시간복잡도는 O(n)이다. 메모리를 한 덩어리로 차지하므로, 배열 크기가 클 경우 배열 전체를 위한..