[230221] 배열과 집합 연습문제 (1장 자료구조가 중요한 까닭)

1. 원소 100개를 포함하는 배열이 있을 때, 다음 연산에 걸리는 단계 수를 계산하기

1. 읽기 : 1단계, O(1), 메모리 주소를 가지고 한번에 찾음
2. 배열에 들어 있지 않은 값 검색 : 100단계, O(n), 없는 값을 임을 확인해야 하므로, 인덱스 0부터 99까지 모두 탐색
3. 배열 맨 앞에 삽입 : 101단계, O(n), 100개의 원소를 모두 한칸씩 밀고, 인덱스 0에 삽입
4. 배열 맨 뒤에 삽입 : 1단계, O(1), 인덱스 100에 삽입
5. 배열 맨 앞에서 삭제 : 100단계, O(n), 인덱스 0을 삭제하고, 남은 99개 원소를 모두 한칸씩 이동
6. 배열 맨 뒤에서 삭제 : 1단계, O(1), 인덱스 99 원소를 삭제

2. 원소 100개를 포함하는 배열 기반 집합이 있을 때, 다음 연산에 걸리는 단계 수를 계산하기

1. 읽기 : 배열과 같음
2. 배열에 들어 있지 않은 값 검색 : 배열과 같음
3. 배열 맨 앞에 삽입 : 201단계, O(n), 100개의 원소를 모두 탐색하여 중복이 있는지 확인하고, 없다면, 모든 원소를 한칸씩 밀고, 인덱스 0에 삽입
4. 배열 맨 뒤에 삽입 : 101단계, O(n), 100개의 원소를 모두 탐색하여 중복이 있는지 확인하고, 없다면, 인덱스 100에 삽입
5. 배열 맨 앞에서 삭제 : 배열과 같음
6. 배열 맨 뒤에서 삭제 : 배열과 같음

3. 일반적으로 배열에서 검색 연산은 주어진 값의 첫 인스턴스를 찾는다. 하지만 주어진 값의 모든 인스턴스를 찾을 때가 있다. 예를 들어, 배열에 "apple"이 몊 번 나오는지 세고 싶다. 모든 "apple"을 찾는 데 며 단계가 걸릴까? N에 대해 답하기

원소가 N개 있는 배열 중 "apple"을 찾기위해서는 N단계가 걸린다. 배열의 모든 인덱스를 돌면서 apple이 있는지 없는지 찾아야 하기 때문이다.