알고리즘

누구나 자료구조와 알고리즘 #1

세모이 2023. 1. 14. 15:26
반응형

자료 구조가 중요한 까닭

  • 좋은 코드 품질은 코드 유지 보수성(가독성, 조직, 코드 모듈성), 효율성 등을 가지고 있다
  • 자료 구조란 데이터(가장 기초적인 수와 문자열로 이뤄짐)를 조직하는 방법
  • 데이터 조직이 코드의 실행 속도에 미치는 영향이 크다
  • 데이터를 어떻게 조직하는가에 따라 프로그램은 수십 수백 배 더 빠르게 혹은 더 느리게 실행 될 수 있다

그러므로 다양한 자료 구조를 알고, 각각의 자료 구조가 개발중인 프로그램의 성능에 어떤 영향을 미칠지 확실히 이해해야 한다.




배열

배열 : 단순히 데이터 원소들의 리스트

  • 배열의 크기 - 배열의 데이터 원소의 개수
  • 배열의 인덱스 - 특정 데이터가 배열의 어디에 알려주는 숫자(인덱스는 0부터 시작)

자료 구조 연산

대부분의 자료 구조는 네 가지 기본 방법을 사용하며, 이를 연산이라 함

  1. 읽기 : 자료구조 내 특정 위치 찾기
  2. 검색 : 자료 구조 내에서 특정 값을 찾기
  3. 삽입: 자료 구조에 새로운 값을 추가
  4. 삭제 : 자료 구조에서 값을 제거
const fruits = ['apple', 'banana', 'tomato', 'grape']
1. 읽기 - 인덱스 1에 들어 있는 것 찾기 -> banana
2. 검색 - 배열 내에 banana가 있는지 찾기
3. 삽입 : 배열에 melon 추가
4. 삭제 : 배열의 grape 제거



속도 측정

연산이 얼마나 빠른가를 측정할 때는 시간관점에서 연산이 빠른가가 아니라 얼마나 많은 단계가 필요한지 논해야함

시간은 연산을 실행하는 하드웨어에 따라 바뀌므로 시간을 기준으로 측정하면 신뢰할 수 없다.

연산의 속도를 측정할 때 얼마나 많은 계산 단계가 필요한가를 따져볼 수 있다. 연산 A에 5단계가 필요하고 연산 B에 10단계가 필요하다면 모든 하드웨어에서 연산 A가 연산B보다 빠를 거라고 가정할 수 있다.




읽기

읽기 - 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것

컴퓨터는 배열의 특정 인덱스에 있는 값을 읽을 때 한번의 단계로 바로 갈 수 있다.

배열 읽기는 한 단계 만에 끝나는 매우 효율적인 연산

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



검색

검색 - 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것


컴퓨터는 모든 메모리 주소에 한 번에 접근 가능하지만 각 메모리에 어떤 값이 잇는지는 바로 알지 못한다
-> 각 메모리를 하나씩 조사해야한다.

const fruits = ['apple', 'banana', 'tomato', 'grape'];

위의 배열에서 tomato라는 값을 검색한다면 배열의 인덱스 0을 확인하고 찾고 있는 값이 아니므로 다음 인덱스 1을 확인하고 tomato라는 값을 발견할때까지 셀을 확인한다(이 연산은 총 3단계가 걸렸다)


위와 같이 컴퓨터가 한 번에 한 셀씩 확인하는 방법을 선형 검색이라 한다.

컴퓨터가 배열에서 선형 검색을 수행하는 데 필요한 최대 단계수는 셀(배열)의 개수

ex) 5개의 셀로 이뤄진 배열에서 찾고 있는 값이 마지막 셀에 있다면 발견할 때까지 모든 셀을 검색해야하므로 5이고 값이 없으면 마찬가지로 모든 셀을 검색해야 배열에 값이 없다고 확신할 수 있음

즉 N개의 셀로 이뤄진 배열은 선형 검색에 최대 N개의 단계가 필요함




삽입

삽입 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.

배열의 맨 끝에 단어를 추가한다면 이 삽입에는 딱 한단계만 필요하다. 왜? 컴퓨터는 배열을 할당할 때 항상 배열의 크기를 기록한다는 특징에 기인

컴퓨터는 배열이 시작되는 메모리 주소를 안다 위의 특징과 맞물려 생각해보면 마지막 항목의 메모리 주소를 계산하기 쉽다.

ex) 배열이 메모리 주소 1010에서 시작하고 크기가 5면 마지막 메모리 주소는 1014고 그 뒤에 항목을 삽입하면 다음 메모리 주소인 1015에 항목을 추가


맨 끝이 아닌 처음이나 중간에 삽입하면 삽입할 공간을 만들기 위해 많은 데이터 조각을 이동해야 하므로 단계가 늘어난다.

const fruits = ['apple', 'banana', 'tomato', 'grape'];

인덱스 1에 melon을 추가한다면 banana, tomato, grape를 셀로 표현할 때 오른쪽으로 옮기고 melon이 들어갈 공간을 만들어야 한다.

-> 즉 grape를 오른쪽으로 옮기고, tomato를 오른쪽으로 옮기고 banana를 오른쪽으로 옮기고 melon을 인덱스 1에 삽입해야한다(4단계가 걸림)

-> 만약 인덱스 0에 삽입을 하게 된다면 5단계가 걸림 (배열 내 모든 값들을 옮기고 값을 삽입하므로)

최악의 시나리오일 때 삽입에는 N+1단계가 걸린다.




삭제

삭제 - 특정 인덱스의 값을 제거하는 과정

const fruits = ['apple', 'banana', 'tomato', 'grape'];

인덱스 1의 값을 삭제해보자

banana를 삭제하는데는 한 단계가 걸리지만 중간에 배열이 비어있으므로 tomato, grape를 왼쪽으로 옮겨야 하므로 2단계가 더 걸린다.(총 3단계가 걸림)

-> 삭제하는데 1단계 이동하는데 2단계

삽입과 비슷하게 인덱스 0 을 삭제하게 되면 나머지 원소들을 모두 왼쪽으로 이동시켜야 하기 때문에 원소 N개를 삭제하는데 필요한 최대 단계수는 N단계라고 볼 수 있다.(1개의 삭제 단계 n-1의 이동 단계)




집합

집합 - 중복 값을 허용하지 않는 자료 구조

배열 기반 집합 - 값들의 단순 리스트로 배열과 비슷

배열 기반 집합과 일반적인 배열의 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않는다.


중복을 허락하지 않는 제약으로 인해 일반 배열의 주요 연산 읽기, 검색, 삭제의 단계의 경우는 아무런 차이가 없지만 삽입의 경우에는 효율성이 크게 달라진다.

일반 배열에서 최악의 시나리오일때 삽입의 경우 N+1의 단계가 걸림(맨 앞의 삽입의 경우), 최선의 경우 배열 맨 뒤의 삽입은 1단계가 걸림


집합에서는 삽입을 할때 새 데이터가 집합에 있는지 없는지의 여부를 모르기 때문에 먼저 ①검색을 해야한다.그리고 해당 인덱스에 ②삽입을 해야함


집합의 끝에 삽입을 하려면 배열 N일 때 값이 없음을 검색하는 N개의 단계와 삽입하는 1개의 단계 총 N+1의 단계가 필요하다.

집합의 맨 앞에 삽입하는 최악의 시나리오는 검색을 하는 N단계, 모든 데이터를 오른쪽으로 옮기는 N단계, 삽입을 하는 1단계 총 2N+1의 단계가 필요하다




마무리

자료 구조의 성능 측정은 연산에 필요한 단계 수를 구하는 게 핵심.(프로그램에 맞는 자료구조를 선택했느냐에 따라 바뀔 수 있으므로 )


집합이 일반적인 배열보다 느려서 쓰지 말아야 할수도 있지만 중복 데이터가 없어야 할 때는 집합을 써야한다.(즉 애플리케이션의 요구 사항에 따라 어떤 자료 구조가 적합한지 결정해야 함)


이 글은 '누구나 자료구조와 알고리즘' 책을 읽고 정리한 내용입니다.
틀린 내용이 있다면 알려주시면 감사합니다

반응형