선형 자료 구조(Linear)
- 선형 자료 구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것
- 배열, 리스트, 스택, 큐
⌨랜덤 접근 가능
랜덤 접근이 가능하다는 것은 모든 자료에 O(1)으로 접근이 보장된다는 의미
✔ 배열 (array) : 순차 자료 구조
- 정적인 자료구조
- 파이썬에서는 리스트 자료구조를 사용
array1 = [] # 빈 리스트
array2 = [0, 1, 2, 3, 4] # 길이가 5인 리스트. 숫자를 0부터 센다
array3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] #리스트 안에 리스트 중첩
배열의 장점
- 정적인 업무에서 처리해야할 자료가 항상 같은 개수를 유지할 경우 공간을 100% 활용
배열의 단점
- 메모리 사용의 비효율성
- 배열의 크기를 사전에 최대로 선언해야 함, 런타임에 변경 불가
- 배열의 모든 요소는 연속적으로 메모리에 저장되어야 함
시간복잡도 계산
- 삽입 : (n+1)/2 = O(n)
- 삭제 : (n-1)/2 = O(n)
- 검색 : 순차 검색의 경우 O(n)
공간복잡도
- 최악의 경우 : O(n)
✔ 해시 (Hash Table)
해시 테이블 - (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이 터를 검색할 수 있다.
- 해시는 해시 함수로 구현
- 해시 함수에 키 값을 넣어 주소값을 얻고, 그 주소에 저장된 데이터를 가져오는 방식을 사용
- 파이썬의 해시는 “딕셔너리”(Dictionary)라고 부른다.
- 해시 함수는 충돌이 일어나지 않을수록 좋다.
충돌 해결
- Chaining
- 데이터들을 포인터를 이용해 서로 linked list 형태로 연결하는 것
- 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도
- Open Addressing
- 모든 데이터를 테이블에 저장하는 방법
- 사용하고자하는 해시 테이블이 이미 사용중인 경우 다른 테이블 사용
- 데이터가 적을 경우 연속된 공간에 데이터를 저장하기 때문에 공간 효율이 높다.
dict1 = {1:"하나", "apple":"사과", "리스트":[1, 2, 3]}출처 https://librewiki.net/wiki/시리즈:수학인듯_과학아닌_공학같은_컴퓨터과학/알고리즘_기초
Programmer & Media