2. 배열과 집합

 

배열 

배열은 순서라는 개념을 갖고 있는 기본적인 자료구조

배열은 요일약통처럼 데이터를 보관할 수 있는 통!

요일은 index, 요일안에 들어있는 약들이 element라고 생각하기!

자료구조에는 크게 읽기 ,검색, 추가, 삭제의 기능이 있다.

 

 

읽기

읽기는 월요일부터 일요일까지 써져있는 약통을 열어보는 것이다.

할아버지께서 화요일에 있는 약을 꺼내달라는 부탁을 들었을 때,

약통에 화요일이라고 써져있는 케이스 안에 있는 약을 드리면된다.

약통을 보는 순간 화요일를 바로 찾을 수 있듯이,

컴퓨터도 배열의 index(요일)값을 통해 element(약)를 조회할 수 있다.

 

 

검색

검색은 약통에 모든 알약의 색이 다르다고 가정했을 때, 특정색의 약을 찾는 것과 같다.

할머니께서 노란색 영양제를 꺼내달라고 하셨을 때, 월요일부터 일요일까지의 케이스를

열어보고, 노란색 영양제를 찾아야 한다.

검색도 특정 element를 찾기 위해 모든 index를 순회하면서 그 안에 있는 element를 확인한다.

찾는 약이 일요일에 있다면 최고의 경우다.

하지만 약이 토요일에 있을 경우 모든 케이스를 열어봐야 하므로 배열의 검색은 효율적이지 않다.

[여기서 효율적이지 않다는 것은 배열의 요소가 무수히 많을 경우를 말한다.]

 

 

추가

추가는 기존의 배열에 새로운 element를 특정 index값에 넣는 것을 말한다.

기존 배열의 마지막 자리에 새로운 element를 추가하는 것은 index + element가 추가되는 것 이기에 빠르다.

하지만 배열의 첫번째 자리 또는 중간 자리에 추가할 경우, 배열의 index가 바꿔줘야 한다.  

 

삭제

삭제는 특정 element를 제거하는 것을 말한다.

삭제를 할 때에는 먼저 제거할 element를 배열을 순회하며 검색한 후, 해당 index의 element를 삭제한다.

삭제 후, 빈 index 자리를 매운다.

 

 

집합

집합은 배열과 유사하나 큰 차이점이 중복되는 엘리먼트가 포함될 수 없다는 점!

 

읽기와 검색, 삭제는 배열과 같다.

 

하지만!! 추가는 다르다.

 

검색과 추가를 할 경우, 먼저 전체의 집합을 순회하여 중복되는 요소가 있는지 검사를 한다.

만약 중복되는 요소가 없다면, 집합에 추가가 된다.

하지만 요소가 이미 집합에 존재한다면, 추가되지 않는다.

 

집합은 중복되는 요소가 포함되지 않아야 하는 자료구조에서 유용하게 쓰인다.