[자료구조] 자료구조와 배열 (누구나 자료구조와 알고리즘 도서 스터디)

---

이 포스팅은 '누구나 자료구조와 알고리즘 개정2판' 을 스터디한 내용을 바탕으로 작성하는 공부기록이다.

 

자료구조 용어

• 데이터 : 기초적인 수와 문자열
• 자료구조 : 데이터를 조직하는 방법으로 같은 데이터를 다양한 방식으로 조직할 수 있다. → 데이터 조직은 그 방식에 따라 코드의 실행 속도에 영향을 미친다.

속도 측정

'연산이 얼마나 빠른가'를 측정한다.
이때, 측정은 얼마나 많은 단계가 필요한지를 논해야 한다.

배열

• 크기 : 배열에 데이터 원소가 얼마나 들어있는지
• 인덱스 : 특정 데이터가 배열의 어디에 있는지

연산

1. 읽기 : 위치를 찾아보는 것
   배열은 각 인덱스에 특정 메모리 주소를 가지고 있고, 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
   → 배열의 읽기는 한 단계로 끝나는 가장 빠른 연산 유형이며 강력한 자료 구조이다.
2. 검색 : 값을 찾는 것
   읽기와 반대의 방식으로 컴퓨터에 값을 제공하고 그 값이 들어있는 인덱스를 반환하라고 요청한다.
   컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알지 못하기 때문에 찾으려는 값을 발견할 때까지 셀을 확인해야 한다.
   → 찾는 값과 찾는 방식에 따라 많은 단계가 걸릴 수 있다. (알고리즘이 필요한 이유)
3. 삽입
   컴퓨터는 배열의 시작 메모리 주소를 알고 있으니 마지막 항목의 메모리 주소를 쉽게 계산할 수 있고 그 끝에 삽입하는 것은 한 단계면 된다.
   단, 중간이나 맨 앞에 삽입해야 하는 경우 기존 데이터를 이동하고 삽입해야 하므로 그 위치에 따라 많은 단계가 걸릴 수 있다. (최악의 경우는 맨 앞에 삽입할 때 N+1 단계 필요)
4. 삭제
   인덱스로 접근해 값을 삭제하는 것은 한 단계면 끝난다.
   하지만 삭제하며 생긴 빈 공간을 메꾸기 위해 데이터를 이동하면 삽입과 마찬가지로 그 위치에 따라 많은 단계가 걸릴 수 있다. (최악의 경우는 맨 앞을 삭제할 때 N 단계 필요)

정렬된 배열

전형적인 배열과 거의 같으나 값이 항상 순서대로 있어야 한다.

연산

1. 읽기 
2. 검색
   • 선형 검색
     전형적인 배열과 가장 큰 차이를 보이는 연산이며, 찾으려는 값이 배열에 없을 때 검색을 빨리 멈출 수 있다.
     (최악의 경우는 찾으려는 값 ≥ 마지막 값일 때 최대 N단계)
   • 이진 검색
     계속해서 중간 값을 골라 남은 수 중 반을 제거해가며 값을 찾는다.
     선형 검색에 비해 훨씬 빠르며 주의할 점은 정렬된 배열에서만 쓸 수 있다.
3. 삽입
   검색을 먼저 수행해서 삽입할 올바른 위치를 정해야 한다. 
   새 값이 앞 부분에 놓이면 비교가 줄고 이동이 늘어나고, 뒷 부분에 놓이면 비교가 늘고 이동이 줄어든다.
   어디에 값이 놓이게 되든 연산 단계는 비슷하다. (맨 끝에 놓을 때 N+1단계)
4. 삭제

→ 정렬된 배열이 전형적인 배열보다 삽입 성능은 느리지만, 검색은 이진 검색 방식을 사용함으로써 훨씬 빨라진다.

 

이를 통해 애플리케이션에서 요구사항을 분석하여 삽입/검색 중 무엇이 더 빈번하게 일어나는가에 따라 더 효율적인 자료구조를 선택해야 한다.