코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 기초 자료구조
여러분, 자료구조의 출발점인 배열부터 시작해볼게요.
배열이 왜 가장 기본적인 자료구조인지, 그 원리를 알아야 다른 구조도 이해할 수 있어요.
슬라이드 위쪽 에이 패널, 메모리 레이아웃을 보세요. =10]
파란 칸 5개가 빈틈 없이 나란히 있죠. 10, 25, 37, 42, 58이에요.
이게 배열의 핵심입니다. 연속된 메모리 공간에 데이터를 빈틈 없이 나열하는 거예요.
각 칸 아래 주소를 보세요. 영엑스1000, 영엑스1004, 영엑스1008 순서로 올라가죠.
초록색 플러스 4비 화살표가 보이시죠? 정수 하나가 4바이트니까 주소도 4씩 증가합니다.
이 규칙적인 간격이 배열의 가장 강력한 무기를 만들어요.
비 패널의 주황색 공식 박스를 보세요. 주소 계산 공식이 있습니다.
에이디알 오브 에이알알 아이 이퀄 베이스 플러스 아이 곱하기 사이즈오브 엘리먼트.
예를 들어 에이알알 3은 영엑스1000 플러스 3 곱하기 4, 영엑스100씨가 되고 값 42에요.
CPU가 이 계산을 한 번에 수행하니까 접근 시간이 항상 오원이에요.
배열 크기가 5개든 5백만 개든 한 번의 산술로 끝납니다.
이제 씨 패널의 캐시 친화성을 보세요. 연속 메모리니까 CPU 캐시에 한 번에 올라갑니다.
64바이트 캐시 라인에 정수 16개가 한꺼번에 적재돼요.
첫 원소를 읽으면 주변 15개도 이미 캐시에 있으니 반복 접근이 엄청 빨라요.
이게 배열이 다른 자료구조보다 순회가 빠른 핵심 이유입니다.
디 패널을 보세요. 인덱스가 왜 0부터 시작하는지 나와 있어요.
에이알알 0이면 베이스 플러스 0 곱하기 4, 즉 베이스 주소 그 자체예요.
만약 1부터 시작하면 매번 아이 빼기 1을 계산해야 해서 뺄셈이 한 번 추가됩니다.
다익스트라가 이 점을 지적했고, 대부분의 언어가 0-based 인덱싱을 채택했어요.
정리하면, 배열은 연속 메모리 플러스 산술 한 번으로 오원 접근하는 가장 기본적인 구조예요.