배열 - 가장 기초적인 자료구조 ( 1 )

 이번 포스트에서는 컴퓨터 과학에서 가장 기초적인 자료구조라고 할 수 있는 배열에 대해서 포스팅해보겠습니다.
배열에 대한 분석과 더불어 알고리즘에서 말하는 "속도" ( 시간 복잡도 ) 란 무엇인가에 대해서도 조금 이야기해보도록 하겠습니다.

---

1. 배열이란?

배열이란 앞서 썼던 것과 같이 컴퓨터 과학에서 가장 기초가 되는 자료구조로서

"단순한 데이터 원소들의 리스트" 

이 한 문장으로 정의할 수 있습니다.

조금 더 자세히 정의하자면 컴퓨터가 데이터 저장을 위해 연속되는 메모리를 할당하고 이를 통해 읽기, 탐색, 삽입, 삭제 등이 이루어질 수 있는 자료구조가 배열이라 할 수 있습니다.

 

이게 배열 이다.

 

---

2. 배열의 요소

• 크기 : 배열에 저장되어 있는 원소의 개수를 뜻합니다.
• 인덱스 : 배열 내 특정 데이터의 위치를 나타냅니다. ( 일반적으로 zero-based )

---

3. 자료 구조의 연산  

이번에는 자료구조에서 통상적으로 쓰이는 연산을 배열을 통해서 알아보겠습니다.

• 읽기 : 자료 구조 내 특정 위치를 확인하는 연산  >> (배열) 특정 인덱스를 통한 접근으로 값을 가져오는 것
• 검색 : 자료 구조 내 특정 값을 찾는 연산 >> (배열) 특정 값이 배열 내에 존재하는지, 존재한다면 어떤 인덱스에 위치하여 있는지를 확인하는 과정
• 삽입 : 자료 구조 내 새로운 값을 추가하는 연산
• 삭제 : 자료 구조 내 특정 값을 삭제하는 연산 

---

4. 속도의 측정

우리에게는 개발할 때에 있어 항상 문제 상황에 맞는 적절한 자료 구조를 선택해야 하는 의무가
있습니다.

그렇다면 위에서 보았던 연산의 속도는 어떻게 측정해야 할까요? 

 

연산이 얼마나 빠른가 측정할 때에는 순수한 시간의 관점이 아닌 얼마나 많은 단계가 필요한지를 확인해야 합니다.

시간은 연산을 실행하는 하드웨어 성능이나 환경에 따라 달라질 수 있는 요인입니다. 하지만 계산 단계는 같은 연산이라면 

결코 변하지 않습니다. 때문에 연산 간의 비교를 위해서는 계산 단계를 확인하는 것이 바람직합니다.

이러한 계산 단계를 측정하는 방법은 시간 복잡도 측정으로 알려져 있습니다.

---

마치며

포스트는 가능한 한  짧은 호흡으로 흥미롭고 알차게 이어나갈 수 있도록 하겠습니다.
다음 포스트는 배열의 각 연산 과정을 알아보고 시간 복잡도를 실제로 계산해 보도록 하겠습니다.
항상 감사드립니다.

 

관련 게시물

배열 - 가장 기초적인 자료구조 ( 1 )

배열 - 가장 기초적인 자료구조 ( 3 )