데이터를 저장하고 접근하기 좋게 조직한 논리적 형태입니다.
자료구조 선택과 Big-O 판별 기준
자료구조 문제는 어떤 연산을 자주 하는지와 입력 크기가 커질 때 시간이 어떻게 늘어나는지를 함께 묻습니다.
무엇을 할 수 있는지 정의하고, 내부 구현은 나중에 분리합니다.
상수나 낮은 차수보다 가장 크게 자라는 항만 남겨 비교합니다.
인덱스 접근은 빠르지만 중간 삽입과 삭제는 이동 비용이 큽니다.
배열과 연결 구조 선택
논리적 구조는 사용자가 보는 연산이고, 물리적 구조는 메모리에 실제로 놓인 방식입니다.
O(1)
입력 크기와 관계없이 한 번에 끝나는 배열 인덱스 접근 같은 경우입니다.
O(n)
처음부터 끝까지 한 번 훑는 순차 탐색과 합 계산에서 자주 나옵니다.
O(n^2)
이중 반복문처럼 각 원소마다 다시 전체를 훑을 때 나타납니다.
O(log n)
문제 크기를 절반씩 줄이는 이진 탐색에서 대표적으로 등장합니다.