[자료구조] 배열

자료의 추상화

• 물리적이며 전기적인 동작과는 무관하게 자료를 생각하고 바라보는 사람의 상상
• 다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징만을 뽑아 정의한 것

자료구조

• 추상화를 통해서 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것
• 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있음

알고리즘

• 컴퓨터에게 일을 시키기 위한 (추상화)된 명령어의 연속된 덩어리
• 개발자가 컴퓨터에게 일을 시키기 위한 사람의 의도와 명령을 전달해 줄 수 있는 방법(언어/글)
• 컴퓨터에게 시킬 일
• 컴퓨터가 수행할 명령어의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것
• 컴퓨터에게 시킬 일(프로그램)을 머릿속에서 추상화시켜서 대략적으로 상상해 놓은 것

추상 자료형

• 자료구조와 알고리즘의 중간쯤에 있는 자료의 복잡한 논리적 성격을 정의하는 방식
• 자료값의 집합과 연산 집합에 대한 정의로 구성되며 자료구조를 표현하는 가장 대표적인 방법

배열

• 차례(순서)와 관련된 기본적인 자료구조
• 원소의 메모리 공간(메인 메모리, DDR)의 물리적 위치를 순서적으로 결정하는 특징
• 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서와 같다.
• 인덱스와 원소값 <index, value>의 쌍으로 구성된 집합

1차원 배열

: 한 줄짜리 배열을 의미하며 하나의 인덱스로 구분됨

• A[i]는 배열의 첫 번째 원소 A[0]이 저장된 메모리 주소인 a로 부터 시작하여 A[0]부터 A[i-1]개 까지의 i개의 배열 A[]를 지나서 저장됨
• 따라서 A[]의 메모리 시작주소를 a라고 가정하면 A[i]의 메모리 저장 주소는 [a + i*k]가 됨
  

2차원 배열

행 우선 배열/ 행 우선 할당

열 우선 배열/열 우선 할당

희소 행렬

: 메모리를 효율적으로 관리할 수 있지만 연산은 매우 복잡해진다. 계산 시간이 증가하게 된다.