배열 기반 자료구조 특징
- 메모리 상 연속적인 위치
- 순차적인 액세스가 매우 빠름
캐시 메모리 작동 측면- 직관적
- 인덱스를 통한 빠른 접근
- 특정 위치 데이터 삽입 과정이 복잡함
- 빈번한 할당·해제로 인한 메모리 단편화 우려
연결 리스트 자료구조 특징
- 메모리 상 불 연속적인 위치
- 포인터를 통한 요소 접근
default- 헤드 노드부터 순차적 접근을 통한 요소 접근
- 특정 위치 데이터 삽입 과장이 간단함
메모리 단편화
주기억 장치의 빈 공간이 여러 개의 조각으로 나뉘는 현상
- 사용가능한 공간 축소 ↓
- 읽기/쓰기 속도 ↓
- 내부 단편화
의도하지 않는 메모리 할당으로 낭비되는 현상
필요한 메모리의 크기보다 큰 단위로 할당되는 경우- 외부 단편화
프로그램이 다양한 크기의 남은 영역을 할당·해제로 인해 빈 공간이
여러 작은 조각으로 나뉘는 현상
- 사용 가능한 메모리 공간 총합 여유
- 메모리 할당 알고리즘 약화
프로그램 성능 저하
push · emplace
- push
- 복사 생성자 호출
default- 이동 생성자 호출
r-value- 오버 헤드 발생
이동·복사- emplace
- 내부에서 객체 생성
- 버그 발생 우려
예기치 못한 타입 변환
높이가 n 인 포화이진트리 노드 총 개수
2 ^ (n+1) - 1
말단 노드 제외한 모든 노드 차수가 2
이진 힙 트리
힙 속성을 만족하며 최댓값·최솟값을 O(1) 시간복잡도로 탐색위한 완전 이진 트리 자료 구조
- 노드 삽입·제거 → 부모
- 자식 노드 사이의 키값의 재귀적인 비교
- O(log n)
힙 속성 | 부모 노드 키 값이 자식 노드 키 값보다 항상 크거나 작은 성질
이진 탐색 트리의 O(n) 상황
- 불균형 상태의 극단적인 경우 발생
단순 연결 리스트와 동일- 자가 균형 이진 탐색 트리를 통한 해결
AVL , Red-Black 트리
불균형 상태 | 루트 노드 기준으로 부분 트리의 높이가 한 방향으로 크게 치우져져 있는 상태
자가 균형 이진트리| 노드 삽입·제거시 규칙에 따라 부분 트리의 회전을 통해 균형을 유지하는 자료구조
서로 집합 자료구조의 union-find 연산 최적화
- union by rank
항상 크기가 작은 집합을 큰 집합 하위 연결하는 형태로 유니온 연산을 구현- 경로 압축
루트 노트들 찾을 때 까지 방문 노드를 루트 노드로 갱신
알고리즘 복잡도 표현
- 시간 복잡도
- 연산 소요 시간
- 주로 사용
현대 컴퓨터의 메모리 여유성- 점근 표기법 사용
상한 (빅 오), 하한 (빅 오메가), 상한·하한의 종합적 (빅 세타)- 최장 시간 파악 중요
default- 공간 복잡도
- 연산 사용 메모리
가변 크기 컨테이너의 Capacity
- 시간 복잡도
요소 추가·제거 < 실제 크기 증가
매 번 요소 추가시 컨테이너 크기 증가는 재할당으로 인한 오버헤드 초래- 해결 방법
현재 capacity 에 비례하는 크기로 적절하게 늘리는 방식 사용
슬랙
컨테이너가 저장할 수 있는 요소 최대 개수인 capacity 와 실제 컨테이너
저장 요소 개수인 size 의 차이
분할-정복, 동적계획법 차이
- 분할-정복
- 주어진 문제를 독립적인 작은 문제 분할
- 부분 문제 해결
- 결합하여 문제의 해 도출
- 동적계획법
주어진 문제를 분할 시 이전 단계의 결과가 이후 단계에서 활용되어 문제를 해결
버블·선택·삽입 정렬의 실행 속도 차이
- 버블 정렬
pairwise 비교를 통해 정렬 순서가 마지 않을 시 요소 swap가장 느림- 선택 정렬
최소값을 찾는 과정 반복 필요 매 → 반복마다 남아있는 요소 재탐색중간- 삽입 정렬
이미 정렬되어 있는 데이터가 존재가장 빠름
삽입 정렬 O(n)
이미 정렬된 상태일 경우 삽입할 위치를 찾는 시간 복잡도 O(1)
퀵 정렬 O(n^2)
정렬된 상태에서 단계별 pivot 이 항상 최솟(최댓)값이므로 발생
선택 정렬과 동일
일반적으로 단계별로 가장 앞(뒤) 요소를 pivot 으로 사용하기 때문
기수 정렬
주어진 숫자 형식의 데이터에 대해 보조 배열을 사용하여 각 자리수마다
데이터 보관·인출 과정을 통해 정렬
- 유용한 경우
- 데이터가 정수형
- 여분의 충분한 메모리를 활용 가능
GameProgrammer