자료구조
정적 배열
int a[3] = {1,1,3}
a[0] = 1 //True배열의 크기를 설정해서 선언한다.
숫자 인덱스를 기반으로 접근 가능하다.
중복을 허용한다.
동적 배열
vector<int> v;
for(int i=1; i<=10; i++) v.push_back(i);컴파일 시점에 사용해야 할 요소들의 개수를 모를 때 사용한다.
연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음
숫자 인덱스를 기반으로 접근 가능하다.
중복을 허용한다.
참조: O(1)
탐색: O(n)
맨 끝에 삽입/삭제: 시간복잡도 O(1)
맨 끝 제외 삽입/삭제: 시간복잡도 O(n)
vector<int> v(5, 100);
for(int a:v) cout << a << " ";
//100, 100, 100, 100, 100포인터
java, python, javascript는 개발자가 메모리에 관여할 수 없고 가비지컬렉터를 통해 메모리를 할당하거나 해제한다.
C, C++ 등은 가비지컬렉터가 없고, 개발자가 직접 필요한 메모리를 예약하고 해제한다.
포인터는 메모리의 주소를 담는 타입이다.
<타입> * <변수명> = <해당 타입의 변수의 주소>
int a = 4;
int *b = &a;
double c = 4.4;
double *d = &c;
cout << sizeof(b) << '\n'; //8
cout << sizeof(d) << '\n'; //8windowOS 64bit -> pointer 8byte 고정
windowOS 32bit -> pointer 4byte 고정
트리
자식노드와 부모노드로 이루어진 계층적인 구조
무방향 그래프
사이클이 없는 자료구조
이진트리
자식노드의 수가 2개 이하인 경우 이진트리라 부른다.
- 정이진 트리: 자식 노드가 0개 또는 2개인 이진트리
- 완전 이진 트리: 왼쪽에서부터 채워져있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져있고, 마지막 레벨의 경우 왼쪽부터 채워져있다.
- 변질 이진 트리: 리프 노드 제외, 자식 노드가 하나밖에 없는 이진 트리
- 포화 이진 트리: 모든 노드가 꽉 차있는 이진 트리
- 균형 이진 트리: 트리의 모든 노드에 대해 그 노드의 왼쪽 하위 트리와 오른쪽 하위 트리가 1이하인 이진 트리
- 이진 탐색 트리: 오른쪽 하위 트리에는 노드의 값보다 큰 값이, 왼쪽 하위 트리에는 노드의 값보다 작은 값이 들어있는 트리. 검색에 용이한 구조
인접 행렬
그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬
각 요소는 0 또는 1의 값을 가지는데, 0은 두 정점 사이의 경로가 없음을, 1은 두 정점 사이에 경로가 있음을 의미한다.
공간 복잡도 O(V^2)
시간 복잡도 : 간선 한 개 찾기 O(1) -> a[0][10000]
시간 복잡도 : 모든 간선 찾기 O(V^2)
인접 리스트
그래프에서 정점과 간선의 관계를 나타내는 연결리스트
공간 복잡도 O(V+E) : 정점과 연결된 간선만 필요
시간 복잡도 : 간선 한 개 찾기 O(V) -> for문
시간 복잡도 : 모든 간선 찾기 O(V+E)
인접 행렬 vs 인접 리스트
그래프가 희소(sparse)할 때에는 인접리스트, 조밀(dense)할 때에는 인접행렬
보통은 인접 리스트를 쓰면 됨
맵
자동으로 오름차순 정렬된다.
참조: O(logn)
탐색: O(logn)
삽입/삭제: O(logn)
셋
중복된 값은 제거된다.
map과 같이 자동정렬된다.
힙
가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리
가장 작은 요소가 루트노도에 있는 최소힙, 가장 큰 요소가 루트노드에 있는 최대힙
시간복잡도 참조(최대/최소값): O(1)
시간복잡도 탐색: O(n)
시간복잡도 삽입/삭제: O(logn)
