Power of Positive Thinking

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조를 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 시간복잡도가 O(1) 이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 1. 해시 해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 여기서 입력값은 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자이지만, 화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑된다. 여기서 화살표 역할을 하는 함수가 바로 해시 함수다. (해시 함수를 만드는 방법론도 하나의 주제가 될 수 있지만 코딩테스트 주제를 벗어난다. 참고로, 구글은 해..

1. 트리의 정의 : 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조이다. ex) 월드컵 본선 대진표, 회사나 학교의 조직도, 인터넷 상점의 상품 분류 기준 등 2. 개요 트리는 현실 세계의 개념을 추상화해 표현하는 자료 구조로 고안되었지만, 탐색형 자료 구조로도 유용하게 쓰인다. 특정한 조건을 지키도록 구성된 트리들을 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 할 수 있기 때문이다. 즉, 어떤 형태로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라 다양한 형태의 트리가 있을 수 있으며, 이들을 이용해 다양한 문제들을 빠르게 풀 수 있다. 3. 트리의 구성 요소 - 트리는 자료가 저장된 노드(node)들이 간선(edge)으로 서로 연결되어 있는 자료 구조이다. 노드 간에..