자료구조는 저장 방식, 알고리즘은 해결 절차입니다.
저장 방식과 비용을 한 표로 비교하기
자료구조 문제는 이름을 외우는 문제처럼 보여도 결국 접근, 삽입, 삭제, 공간 사용 중 무엇을 묻는지 고르는 문제입니다.
시간복잡도와 공간복잡도를 따로 적습니다.
접근, 탐색, 삽입, 삭제 중 어느 비용인지 봅니다.
배열, 행렬, 희소 행렬의 저장 모양을 그립니다.
증가 속도만 비교
O(1), O(log n), O(n),
O(n²)는 입력 크기가 커질 때의 변화입니다.
빠른 접근, 느린 중간 변경
인덱스 접근은 O(1)이지만 중간 삽입과 삭제는 뒤 원소
이동 때문에 O(n)입니다.
행우선과 열우선
C 배열은 보통 행우선으로 저장하므로
i × 열 개수 + j 감각을 잡습니다.
전치와 희소 표현
전치는 행과 열을 바꾸고, 희소 행렬은 0이 아닌 원소만 저장해 공간을 아낍니다.