자료구조 4

[자료구조] 해시 테이블(Hash Table)

해시 테이블(Hash Table)은 실무에서 필수적인 자료 구조이며 자주 사용되는 자료 구조 중 하나이다.이뿐만 아니라 다른 자료 구조에 비해 월등히 빠른 속도를 가진다. 해싱(Hashing)아래의 이미지는 해시 함수를 통해 키가 해시 값으로 변환되는 과정을 도식화한 것이다. 이러한 일련의 과정을 해싱이라고 한다.  위의 이미지는 'John Smith'라는 문자열을 해시 함수를 통해 '01'이라는 새로운 해시 값으로 변환했다. 그리고 01에 들어 있는 값인 521-8976을 찾았다.해싱이란 임의의 크기의 데이터를 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 작업이다. 해시 함수(Hash Function)해시 테이블에서 가장 중요한 것을 꼽으라면 해시 함수라고 할 수 있다. 그렇다면 해시 함수는 무..

[자료구조] 비선형(NonLinear) 자료 구조

자료 구조는 생각보다 다양한 형태를 가진다.어떤 형태의 자료 구조를 사용하느냐에 따라 알고리즘의 효율성도 천차만별이다.   비선형(NonLinear) 자료 구조선형 구조는 자료를 저장하고 꺼내는 것에 초점을 맞추는 반면 비선형 구조는 자료를 어떻게 표현할지에 초점을 맞추고 있다. 다른 말로 표현하면 선형 구조는 일렬로 정렬된 데이터 구조, 비선형 구조는 하나의 자료 뒤에 여러 개의 자료가 연결되어 있는 형태다. 즉, 데이터 요소가 계층 구조를 가지고 있다. 2024.08.23 - [CS] - [자료구조] 선형(Linear) 자료구조 [자료구조] 선형(Linear) 자료구조의 종류와 특징자료 구조는 알고리즘의 효율성을 결정하는 중요한 요소 중 하나다.자료 구조는 크게 선형(Linear) 구조와 비선형(No..

[자료구조] 선형(Linear) 자료구조의 종류와 특징

자료 구조는 알고리즘의 효율성을 결정하는 중요한 요소 중 하나다.자료 구조는 크게 선형(Linear) 구조와 비선형(NonLinear) 구조로 나뉜다. 선형(Linear) 자료 구조선형구조란 메모리상에 데이터 즉, 요소들이 연속으로 나열된 형태의 자료 구조다. 각 요소는 앞과 뒤의 요소와 1대1 관계를 가진다. 각 요소에 접근할 때는 직접 접근으로 빅오 표기법 O(1)의 시간 복잡도를 가지나 요소의 삽입 및 삭제 시에는 데이터 이동으로 인한 시간 복잡도가 증가하므로 O(n)의 시간 복잡도를 가진다. 2024.08.23 - [CS] - [자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법 [자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법어떤 알고리즘이 효율적인지 판단하는 지표로..

[자료구조] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법

어떤 알고리즘이 효율적인지 판단하는 지표로는 크게 실행 소요 시간 측면에서 분석하는 시간 복잡도, 공간 측면에서 분석하는 공간 복잡도를 추정하여 판단한다.   시간 복잡도(Time Complexity)시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로 알고리즘이 수행되는데 필요한 시간을 상대적인 지표로 나타낸 것이다. 즉, 어떠한 알고리즘이 얼마나 많은 시간이 걸리는지 나타내는데 쓰인다. 주로 빅오 표기법으로 나타낸다.시간 복잡도는 알고리즘의 수행 시간을 분석한 결과다. 공간 복잡도(Space Complexity)시간 복잡도가 말 그대로 시간과 관련되어 있듯이 공간 복잡도도 공간과 관련되어 있다. 즉, 어떠한 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타내는데 쓰인다. 공간 복잡도는 알고리즘의..