✍️Today I Learned
- 시간 복잡도
- 공간 복잡도
- 자주 쓰이는 자료구조
시간 복잡도
- 프로그램의 수행 성능을
최악의 경우를 가정하여 정량화하는 방법 - 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
입력이 array인 이중루프의 경우
| 입력 | 실행 시간 |
|---|---|
| array 원소 개수 = N | array 원소 개수 X array 원소 개수 만큼 비교 연산 = N X N |
| 시간 복잡도 O(N^2) |
공간 복잡도
시간 복잡도에 비해 중요하지 않다. 지나치게 공간을 낭비하는 것만 주의!
#include <iostream>
#include <vector>
#include <algorithm> // max_element 사용
using namespace std;
int largest_product(const vector<int>& arr) {
vector<int> products; // 배열은 벡터를 쓸겁니다!
for (int a : arr) {
for (int b : arr) {
// products 배열에 원소가 들어가는 이 연산은 (a * b)번이 실행되겠죠? 2중 루프!
products.push_back(a * b);
}
}
// products의 최대값을 찾는 함수
int maxVal = *max_element(products.begin(), products.end());
// 따라서, products의 공간 복잡도는 O(N^2)
return maxVal;
}
int main() {
vector<int> myList = {1, 3, 5, 7, 9};
cout << largest_product(myList) << "\n";
}자주 쓰이는 자료구조
배열
- 하나의 변수에 연관된 데이터를 그룹핑하여 관리하며 반복문과 결합해 효율적으로 처리할 수 있다.
- 실제 메모리에 연속적인 위치에 존재하며 관리된다.
- C++은 정적 타입 언어이므로, 배열 생성 시 타입과 크기를 명시해야 한다. 메모리를 효율적으로 관리 할 수 있다.
- 배열의 각 요소는 동일한 타입이어야 하며 컴파일 시점에 타입이 결정된다.
배열 대표 기능
- 조회
- O(1)의 조회 시간
- 인덱스 값을 받으면 해당하는 배열 값을 바로 리턴 - 삽입 & 삭제
- 정적 배열의 경우 크기 변경 불가능
- vector 사용할 경우- 배열 끝에서 추가 및 삭제 -> O(1) 재할당 필요없는 경우
- 중간에서 삽입 혹은 삭제하는 경우 -> O(N) 새로 공간 확보 후 재정렬
- 정렬
- 정렬 알고리즘에 따라 시간 복잡도가 다르다
- STL sort() -> 평균적으로 O(N log N) - 검색
- 일반적으로 O(N)
- 정렬된 배열의 경우 이진 검색을 사용하면 O(log N)
LinkedList
- 유동적으로 연결고리를 떼었다가 붙일 수 있는 자료구조. 회물 기차같은 구조
- 삽입/삭제에 강점이 있지만 조회에 약하다.
용어
- 노드
- 각 화물 칸을 노드라고 한다.
- 맨 앞 노드를 Head, 맨 뒤 노드(포인터가 NULL)를 Tail - 포인터
- 현재 노드가 가리키는 다음 칸을 포인터라고 한다.
인덱스를 알고 있다는 전제 하에
- 데이터에 빈번하게 접근해야 할 때 -> 배열
- 데이터를 빈번하게 삽입/삭제해야 할 때 -> Linked List
Stack
- LIFO(Last In First Out)
- 역순의 성질을 사용해야 할 때 유용하다.
- ex) 모바일에서 뒤로가기
기능
- Top: 스택의 맨 위 데이터 출력
- Push: 스택에 원소를 삽입. Top에 들어간다.
- Pop: 스택의 Top에서 원소를 제거한다.
Queue
- FIFO(First In First Out)
- ex) 대기열
기능
- Front: 큐의 맨 앞 데이터 출력
- Back: 큐의 맨 뒤 데이터 출력
- Push: 큐에 원소를 삽입. End에 들어간다.
- Pop: 큐에서 Front의 원소를 제거한다.
