누구나 자료구조와 알고리즘 - (1) 자료 구조: 배열과 집합

 

 

 

 

 

기본개념

[자료구조연산]

• 읽기: 자료 구조 내 특정 위치를 찾아보는 것 (인덱스 찾기)
• 검색: 자료 구조 내 특정 값을 찾는 것
• 삽입: 자료 구조에 새로운 값을 추가
• 삭제: 자료 구조에서 값을 제거하는 것

 

[속도측정]

연산이 얼마가 빠른가를 측정할 때는 시간관점이 아닌 "얼마나 많은 단계가 필요한지"를 논해야한다.

시간은 연산을 실행하는 하드웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 안된다. 단계 수 측정이 연산 속도를 분석하는 핵심 비결이다.

 

 

 

---

 

 

배열

사과

바나나

오이

대추

포도

 

 

[읽기]

자료 구조 내 특정 위치를 찾아보는 것이다. (=인덱스 찾기)

• 컴퓨터는 모든 메모리 주소에 한번에 갈수 있다.
• 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다. 그래서 배열의 첫번째 원소를 찾으라고 요청하면 적절한 메모리 주소로 바로 가서 찾는다.

 

[검색]

배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것으로, 읽기와 달리 값으로 인덱스를 찾는 것이기때문에 효율성에 차이가 있다.

만약 배열의 개수가 5개이고 찾는 값이 4번째에 있다면 총 4단계가 걸린다. 처음부터 검색하는 것을 "선형검색"이라고 한다.

 

[삽입]

• 배열 끝에 삽입하는 경우: 1단계
• 배열 앞이나 중간에 데이터를 삽입 경우: 많은 데이터를 이동시켜야해서 단계가 늘어난다.

최악의 시나리오는 맨 앞에 삽입하는 경우이다. 이때는 N+1단계이다.

 

[삭제]

기술적으로는 한단계가 걸리지만 배열 중간에 비어있는 셀을 채워야한다.

만약 '오이'를 삭제한다면 대추와 포도를 빈 셀로 옮기는 단계가 필요해 총 3단계가 소요된다.

최악의 시나리오는 맨 앞의 요소를 삭제하는 경우이다. 이때는 N단계이다.

 

 

 

---

 

 

집합

집합은 중복 값을 허용하지 않는 자료구조이다. 배열 기반 집합과 일반적인 배열간 유일한 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않는다. 그렇기때문에 삽입을 하기위해서는 1) 전체를 검색하는 단계 2) 삽입하는 단계로 최대 N+1단계가 필요하다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.