자료구조 알고리즘

알고리즘이

: 연산을 풀어나가는 절차

자료구조

: 목적에 맞게끔 데이터를 논리적으로 정리한 구조

배열의 특징

:인덱스: 데이터가 배열에서 있는 위치

:0에서 시작.

:연산 속도는 단계 수로 측정.

A 읽기

:특정 인덱스에 있는 값 확인

:컴퓨터 메모리 내에 주소가 있는 셀에 인덱스를 줌.

컴퓨터 perspective

컴퓨터에 인덱스 3에 있는 값을 읽으라고 명령

1 배열의 인덱스는 0부터 시작. 메모리 주소를 찾음

2 인덱스 3은 정확히 세 슬록 뒤에 있음

3 따라서 현재 0 위치의 메모리 주소 +3을 해서 찾음.

검색

컴퓨터 perspective

1 인덱스 0을 확인 값이 없으면 다음 셀로 넘어가서 확인 찾을 때 까지 한단계씩 올림.

2 배열 3을 찾을 경우 총 4단계를 거침 . 0 -> 1 -> 2 -> 3 -> 4

B 삽입

1 맨 끝에 추가시 메모리 주소를 정확히 계산해서 한 단계만 필요.

2 처음 또는 중간 입력시 삽입할 공간을 위해 데이터 조각을 전체 이동함.

3 최악의 시나리오 원소 N 개 포함 배열에서 N+1 걸림.

C 삭제

1 중간 배열에 삭제하면 비어 있는 셀이 발생해서 우측에 있는 다른 데이터를 전부 왼쪽으로 옮겨서 빈 공간을 메꾸는 데이터 이동이 필요함.

2 최대 단계 N 개 필요.

집합

: 중복값을 허용하지 않음

: 집합에서는 CRuD시 값이 집합에 이미 있는지 확인

: 0-5 로되어 있는 데이터의 경우. 0-5 인덱스의 요소를 전부 탐색해서 중복 값이 없는지 확인한 후 값을 CRuD한다.

: 최악의 경우 총 2N+1 단계가 필요함.