ADT
추상 자료형
무엇을 할 수 있는지 정한 약속이다. 배열, 연결 리스트 같은 구현과 구분해서 읽는다.
자료구조 선택
자료구조와 시간 복잡도
자료구조 문제는 무엇을 자주 하는지부터 정한다. 접근, 탐색, 삽입, 삭제의 비용을 비교하면 배열 선택의 장단점이 드러난다.
array
배열 선택
인덱스 접근은 O(1)로 빠르다. 중간 삽입과 삭제는 뒤
원소를 옮겨야 해서 O(n)이다.
search
순차 탐색
처음부터 끝까지 하나씩 비교하면 최악의 경우 모든 원소를 본다. 시간은
O(n)이다.
루프
이중 반복
바깥 반복마다 안쪽 반복이 다시 돌면 전체 횟수는 곱해진다. 대표
형태는 O(n²)이다.
행렬
행렬과 희소행렬
2차원 배열은 행과 열 위치를 계산한다. 0이 많은 행렬은 0이 아닌 값만 저장하면 공간을 줄일 수 있다.