[Data Structure & Algorithm] 자료구조 필요한 까닭

자료구조 알고리즘

자료구조

데이터: 모든정보 망라하는 유형, 가장 기초적인 수와 문자열로 이뤄진다.

자료구조: 데이터를 조직하는 방법

데이터를 어떻게 조직하는가 =⇒ 자료구조를 어떻게 구성하는게 따라 프로그램은 수십 수백 배 더 빠르게 혹은 더 느리게 실행될 수 있다.

그러므로 소프웨어개발자에겐 자료구조를 알고, 개발하는 것은 중요한 덕목이다.

배열과 집합

배열: 컴퓨터 과학에서 기초 자료구조

자료구조연산: 배열의 자료구조 성능을 알려면 코드가 자료구조와 상호작용하는 분석하여야한다. 읽기, 검색, 삽입, 삭제 네가지 방법을 사용한다.

자료구조연산속도를 측정할 때 계산단계를 기준으로한다.

자료구조 연산

읽기

• 기능: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아준다.
• 단계: 1단계 (가장 빠른 연산 유형)
• 배열기본: 컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이다. 아래 격자로 된 셀이 있고 배열을 선언하게되면 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당한다.

	9		10
1	2	3	4

• 각 셀은 특정주소(메모리주소)가 존재한다.
• 배열이 어떤 메모리주소에서 시작하는지도 기록
• 컴퓨터는 모든 메모리주소에 한 번에 접근 할 수 있다. (주소 1063번에 있는 값을 읽을 때 검색 없이 바로 읽기 가능하다. )

검색(선형검색)

• 기능: 배열에 특정 값이 있다면 어느 인덱스에 있는지 찾아준다.
• 단계: 최대 N단계 (N:배열길이)
• 컴퓨터는 모든 메모리주소에 한 번에 읽기가능하지만 주소에 어떤 값이 들어있는지는 바로 알 수 없다.
• | ? (0) | ? (1) | ? (2) | ? (3) | | --- | --- | --- | --- |
• 각 셀을 한 번에 하나씩 조사

삽입

• 기능: 특정 인덱스 위치에 삽입
• 단계: 맨 뒤 인덱스에 추가시 1단계 / 최대 N+1단계
• 특징: 맨 처음, 중간 삽입시에 인덱스값을 오른쪽으로 하나씩 옮겨 배열에 자리를 마련한뒤에 삽입된다.

삭제

• 기능: 특정 인덱스의 값 제거
• 단계: N단계
• 특징: 삭제하고 비어진 셀을 채우기 위해 인덱스 값들이 한 칸씩 이동한다.

배열기반 집합

• 배열과 비슷, 중복을 허용하지 않는다는 차이점 존재

자료구조 연산

• 읽기, 검색, 삭제 일반 배열 자료구조연산과 똑같다.
• 삽입만 다르다. 중복을 허용하지 않기 때문이다.
  • 검색을 먼저하고 삽입한다. 검색을 통해 중복을 먼저 확인하고 삽입하게 된다.
• 삽입 단계: 집합 끝에 삽입(최선) N+1단계 / 맨 앞 삽입(최악, 최대) 2N+1 N번 검색 + N번만큼 인덱스값 이동 + 삽입

정리

어플리케이션에 맞는 자료구조를 적용하여야한다. 중복이 필요한 경우엔 배열집합이 효율이 떨어지더라도 사용하는 것이 맞다.