Computer Science/Algorithm & Data Structure

[자료구조] 해시테이블

1. 해시 테이블이란? 우리가 누군가에게 연락하기 위해서는 핸드폰 번호를 입력해서 할 수 있겠지만 이런 경우 그 사람의 연락처가 무엇인지 기억하기 위한 노력이 필요합니다. 그런데 만약 100명, 아니 10,000명의 사람의 연락처를 기억하고 그것을 바로 생각해서 연락하는 것은 음, 쉽지 않겠죠? 그래서 그것을 기억하기 쉽게 단축 번호(1, 2, ..., N)를 등록하거나 이름, 별명 등 다양한 방식으로 그 전화번호를 저장하는게 보통입니다. 여기서 홍길동이라는 사람의 연락처를 찾는다고 하고, ㄱ~ㅎ까지 순차적으로 확인한다고 하면 등록된 연락처의 수에 비례해서 찾는 시간이 걸립니다. 또한 탐색에서 빠르다고 하는 이진 탐색을 이용해도, 탐색하는 양을 절반씩 줄여나가 많이 개선됩니다. 하지만 결국에는 데이터의 ..

[알고리즘] 복잡도 / 빅오 표기법 기본 개념

1. 복잡도(Complexity) 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 복잡도가 높다라는 것은 특정한 함수의 성능적인 측면에서 많은 시간을 소요하고, 많은 메모리의 자원을 먹는 것을 말한다. 2. 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항(최고차항)을 고려하는 표기법 함수의 상한(최악의 수행시간)만을 나타내게 된다. ex ) 3N² + 5N + 100 의 경우, 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N²)으로 표현된다. 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨..