[자료구조] 자료구조 & 시간복잡도

해당 블로그는 '문제 해결력을 높이는 알고리즘과 자료구조' 책을 바탕으로 작성하였습니다

자료구조란?

data structure : 자료를 가지고 있는 방법
쿼리(query): 자료 구조에 값을 넣어 관리하거나 자료 구조에서 원하는 값을 꺼내는 요구

주로 자료구조를 사용할때 쿼리 타입은 요소를 삽입, 삭제, 탐색가 있다

---

배열

대량의 데이터가 있을 때 각각의 요소에 간단히 접근할 수 있는 자료구조
요소를 일렬로 나열하고 각 요소에 인덱스로 쉽게 접근할 수 있다

배열을 사용한 처리를 C++로 구현할 때는 주로 STL vector를 사용하면 편하다

예시 코드

#include <iostream>
#include <vector>
using namespaced std;

int main()
{
	vector<int> a = {4, 3, 12, 7, 11, 1};
    
    // 0번째 요소를 출력
    cout << a[0] << endl;
    
    // 두 번째 요소의 값을 5로 교체, 12 -> 5
    a[2] = 5;
	cout << a[2] << endl;
}

출력값 : 4 5

배열의 장점

• 데이터 a[i]에 빠르게 접근할 수 있다는 점이다
• 배열은 O(1) 상수시간의 시간복잡도로 실행이 가능하다
• 랜덤 액세스 : 데이터에 저장한 장소나 기록 순서에 관계없이 직접 접근하는 방식

배열의 단점

• 중간에 데이터 삽입하는 경우 (시간복잡도가 O(N))

1. 배열 안에서 요소 y직후에 바로 요소 x를 삽입하려면 요소 y가 어디있는 지 파악해야한다

2. 선형탐색법(for문)으로 일단 탐색하여도 괜찮다 (시간복잡도O(N))

3. 요소y를 탐색한 후 요소 x를 삽입하려면 x뒤에 오는 요소들을 한칸 씩 밀어야한다

4. 결론적으로 시간복잡도가 O(N)이 된다

• 중간 데이터를 삭제하는 경우

1. 마찬가지로 중간 데이터를 삭제하는 경우에도 요소x를 삭제하게 되면 뒤에 있던 요소들의 위치를 앞으로 밀어야한다
2. 시간복잡도는 O(N)이다

• 요소를 탐색하는 경우
  내가 찾고자 하는 요소를 탐색하려면 선형탐색법으로 주로 찾을텐데 시간복잡도O(N)이 걸린다

시간복잡도 예외

1. 배열에서 마지막 인덱스 위치에 값을 삽입하거나, 삭제하는 경우에는 시간복잡도가 O(1)이다
   -> 이유: 마지막 인덱스의 위치에 삽입/삭제를 하면 따로 요소들의 이동이 필요없기 때문이다
   

배열과 연결리스트의 차이

배열과 연결리스트 모두 특정 요소의 포함 여부를 탐색하는 데 O(N)의 시간복잡도가 걸린다
탐색에 빠른 시간이 걸리는 자료구조 : 해시테이블, 자가 균형 이진 탐색 트리

해시테이블 시간복잡도