너무너무 멋져 눈이눈이 부셔
자료구조 -시간복잡도, 배열, 연결리스트 본문
시간 복잡도
C++의 기본
- C++은 main함수를 중심으로 동작. main 반드시 있어야 함.
(1) : 헤더 파일. bits/stdc++.h는 모든 표준 라이브러리가 포함된 헤더.
(2): std라는 네임스페이스를 사용. ,cin이나 cout을 사용할때는 std::cin처럼 네임스페이오 함꼐 호출해야 하므로 이를 기본으로 설정한다는 뜻.
(3): 문자열 선언. <타입><변수명>
(4): 입력. cin,scanf등 있음.
(5): 출력. cout, printf등 있음.
(6) return 0 : main 함수가 0리턴하면서 프로세스 종료.
빅오 표기법
시간복잡도: 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간.
이건 입력 크기 n에 대해서 시간 복잡도 10n^2 + n -> O(n^2)
공간 복잡도
프로그램 실행시켰을 떄 필요로 하는 자원 공간의 양. 정적 변수로 선언된 것 말고도 동적인 재귀적 함수로 인해 공간을 계속해서 필요로 할 경우도 포함.
int a[1004];
의 경우 a 배열은 1004 * 4byte의 크기를 가지게 된다.
자료 구조에서의 시간 복잡도
리스트보다 해시 테이블이 대체적으로 빠르다!
시간복잡도를 구하는 요령
하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n m) -> O (n²)
컬렉션 정렬을 사용하는 경우 : O(nlog(n))
선형 자료 구조
요소가 일렬로 나열되어있는 자료 구조
연결 리스트
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조.
삽입,삭제는 O(1) 탐색에는 O(n)
prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨것.
- head: 맨 앞의 노드
- 마지막 노드를 tail
- 싱글 연결 리스트 : next 포인터만
- 이중 연결 리스트 : 둘 다.
- 원형 이중 연결 리스트: 마지막 노드의 next가 헤드 노드를 가리킴.
push_front() : 앞에 요소 넣기
push_back(): 뒤에 요소 넣기
insert() : 중간에 요소 넣기
배열
같은 타입의 변수 + 정해진 크기 + 인접한 데이터 위치에 있는 데이터들의 집합.
중복 허용, 순서 O
- C++에서 사이즈 구하기
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]); // 7랜덤 접근(직접접근)과 순차적 접근
직접접근: 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능.
순차적 접근: 순차적으로 검색
배열과 연결 리스트 비교
배열은 인덱스만 알면 요소를 끄집어 낼 수 있다.
연결리스트는 하나씩 상자를 확인해야 요소를 알 수 있다.
참조가 많이 일어난느 작업 -> 배열이 빠르다.
데이터 추가 및 삭제 -> 연결리스트가 더 빠르다.
왜? 배열은 모든 상자를 앞으로 옮겨야 추가가 가능, 연결리스트는 선만 바꾸면 됨.
보통 면접 문제는 각 자료 구조에 대한 설명(장단점), 비교, 시간 복잡도, 활용 예시 등이 있다.
'천재적인 CS > 자료구조' 카테고리의 다른 글
| [자료구조 CS] 이진탐색트리, 맵, 해시테이블, 셋, 힙, 우선 순위 큐. (0) | 2023.12.28 |
|---|
