프로그래밍을 이제 정말 진지하게 다루고 깊게 이해해야 한다고 스스로 생각이 들었다. 그래서 CS의 가장 기초인 자료구조부터 정리하며 공부하려고 한다.
운이 좋게 이번 학기에 방통대 과목으로 자료구조를 듣게 되었으니 공부한 내용을 블로그에 정리하면서 깊게 이해해보는 시간을 갖겠다.
배열이란?
- 일정한 차례(순서)와 관련된 기본적인 자료구조
- 인덱스와 원소값 (<index, value>)의 쌍으로 구성된 집합
배열의 정의
- 원소들이 모두 같은 자료형과 같은 크기의 기억공간을 가짐
- 배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근이 가능함
인덱스
- 인덱스 값은 추상화된 값, 메모리 주소값은 자료가 실제로 저장되어 있는 곳의 값
ADT Array 객체
Index: 순서를 나타내는 원소들의 유한집합
Element: 타입이 같은 원소의 집합
-> 배열을 사용하기 위한 일종의 가이드라인
1차원 배열
- 한 줄짜리 배열을 의미, 하나의 인덱스로 구분됨
- A[i]는 배열의 첫 번째 원소 A[0]이 저장된 주소인 a로부터 시작하여, A[0]부터 A[i-1]개까지 i개의 배열 A[]를 지나서 저장됨
- 따라서, A[]의 시작주소를 a라고 가정하면, A[i] 저장 주소는 [a+i*k]가 됨 (*k는 메모리 할당 단위)
a, a+k, a+i*k .... a+u*k
-> 이 룰을 기반으로 운영체제가 데이터에 접근함.
데이터 저장 or 접근 시에는 컴파일러가 추상화된 값을 번역해서 운영체제에게 요청.
2차원 배열
행우선 배열: 1차원 배열을 여러개 쌓아 놓은 것이 2차원 배열
ex) A[5][3]
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 |