📚 자료 구조란?
자료 구조란 데이터를 조직하는 방법이다.
let x = "Hello!";
let y = "How are you ";
let z = "today?";
console.log(x + y + z);
let arr = ["Hello!","How are you ","today?"];
console.log(arr[0] + arr[1] + arr[2]);데이터 조직이 코드의 실행 속도에 미치는 영향은 크다.
데이터를 어떻게 조직하는가에 따라 프로그램은 수십 수백 배 빠르게 혹은 느리게 실행될 수 있다.예를 들면, 만약 1000만개의 데이터를 처리해야 하는 프로그램이나 다수의 사용자가 동시에 사용하는 프로그램을 개발한다고 하면 1000만개의 데이터와 트래픽을 처리하기 위해 선택한 자료 구조가 트래픽과 데이터 처리량을 감당할 수 없어 멈춰버릴 수 있다.
=> 이와 같은 상황 때문에, 소프트웨어를 문제없이 빠르게 실행할 수 있는 코드를 작성하는 능력을 갖추고 다양한 자료 구조를 알고, 각각의 자료 구조가 프로그램의 성능에 어떤 영향을 미칠지 확실히 이해하고 있어야 한다.
1. 배열
배열은 컴퓨터 과학에서 기초적인 자료 구조 중 하나이다.
배열은 단순히 데이터 원소들의 리스트이다.
- 배열의 크기 : 배열에 데이터 원소가 얼마나 있는지 알려준다.(Array.length-javascript)
- 배열의 인덱스 : 특정 데이터가 배열 어디에 있는지 알려주는 숫자이다.(0부터 시작한다-javascript)
let fruits = ["apple","banana","lemon","orange"];
apple은 fruits[0], banana는 fruits[1] orange는 fruits[3]에 위치한다. [] 안에 들어있는 숫자가 인덱스이다.
1-1. [배열] 자료 구조 연산
❗️자료 구조 연산
- 읽기 : 읽기는 자료 구조 내 "특정 위치"를 찾아보는 것이다. 배열에서는 특정 인덱스의 값을 찾아보는 것을 의미한다.
- 검색 : 검색은 자료 구조 내 "특정 값"을 찾는 것이다. 배열에서는 특정 값이 배열에 들어 있는지, 만약 있다면 어떤 인덱스에 있는지 알아보는 것을 의미한다.
- 삽입 : 삽입은 자료 구조에 새로운 값을 추가하는 것이다. 배열이라면 배열 내에 공간을 더 만들어 새 값을 추가하는 것을 의미한다.
- 삭제 : 삭제는 자료 구조에서 값을 제거하는 것이다. 배열에서는 배열의 값 중 하나를 제거하는 것을 의미한다.
💡 연산의 속도 측정
: 연산이 얼마나 빠른가를 측정할 때는 순수하게 "시간" 관점에서 빠른가가 아니라 얼마나 많은 "단계"가 필요한지를 논해야 한다....?
왜냐하면 같은 연산도 컴퓨터마다 다르기 때문에, 시간을 기준으로 속도를 측정하는 것은 신뢰할 수 없다고 한다.
=> 여기서 단계는 계산 단계를 말하는데, 이것은 결국 시간 복잡도 측정을 의미한다.
읽기
https://velog.io/@lshyun955/01.JavaScript-sykh8f6w 에 자바스크립트에서 객체가 메모리 상에 저장되는 방식을 도식화 해놨다.
만약 배열let fruits = ["apple","banana","lemon","orange"];이 메모리 5001번에 fruits가 저장되면 데이터 영역에 각 원소들이 저장되어진다.
원소의 첫 번째 값 apple이 7001번 메모리에 저장되면 banana는 7002번 메모리에 저장되는 방식으로 배열은 메모리 상에 저장된다.
위와 같이 동작하기 때문에, 컴퓨터는 어떤 메모리 주소든 한 번에 접근해 어떤 인덱스든 읽을 수 있으니 배열의 읽기는 매우 효율적은 연산이다.
검색
검색은 읽기와는 다르게 배열에 "특정 값"이 있는지 알아본 후, 있으면 어떤 인덱스에 있는지 찾는 것이다.
읽기는 컴퓨터에게 인덱스를 제공하고 컴퓨터는 배열의 메모리 주소를 기반으로 인덱스를 더해 값을 반환하고,검색은 컴퓨터에게 값을 제공하고 값을 기반으로 인덱스를 반환하라고 한다.
=> 효율성 측면에서 엄청난 차이가 존재한다. 단순히 생각해도 읽기는 컴퓨터가 이미 배열의 주소를 기억하고 있고, 메모리 주소에 인덱스를 더한 값을 주면 컴퓨터는 바로 접근해서 값을 찾는다.
하지만 검색은 읽기와는 달리 컴퓨터가 특정 값에 바로 접근을 할 수 없다.
예를 들면, 메모리 상에는 만약 배열
let fruits = ["apple","banana","lemon","orange"];이 존재한다고 가정하자.
우리는 fruits라는 배열이 존재하는 것은 알고 있고 해당 배열 안의 원소들은 뭐가 있는지 모르는 것이다.
만약 "grape"라는 특정 값을 fruits 배열에서 검색을 한다고 하면, 컴퓨터는 배열의 첫 번째 메모리 셀부터 모두 확인하는 방법밖에 없다.
만약 5번째 인덱스에 "grape"가 존재하면 5번째 인덱스까지 탐색을 계속 해야 한다.
알고리즘이 중요한 이유를 어느정도 느낄 수 있다.
=> 이와 같은 검색연산, 즉 컴퓨터가 한 번에 한 셀씩 확인하는 방법을 선형 검색이라 부른다.
크기가 500인 배열에서 선형 검색에 걸리는 최대 단계 수는 500개이다. 최악의 경우 마지막 셀까지 검색 해야 하기 때문이다.
삽입
배열에 새 데이터를 삽입하는 연산은 배열의 어느 위치에 데이터를 삽입하는가에 따라 효율성이 다르다.
배열의 제일 맨 끝에 요소를 추가하는 데는 딱 한 단계만 필요하다.
-> 이것은 컴퓨터가 배열을 할당할 때 항상 배열의 크기를 기록한다는 특징에 기인한다.
-> 배열의 크기를 알기 때문에 맨 끝에 요소를 추가하는 데는 한 단계만 필요하다.
하지만 만약 맨 처음이나 중간에 데이터를 삽입하면 얘기가 달라진다. 이 때는 맨 앞의 데이터를 삽입하기 위해 나머지 원소들을 한 칸씩 뒤로 밀어야하고, 마찬가지로 중간에 데이터를 삽입는 경우도 해당 위치 뒤의 데이터들을 한 칸씩 뒤로 이동시켜야 하기 때문에 단계가 늘어난다.
배열 삽입에서 최악의 시나리오는 맨 앞에 삽입하는 경우이다. 왜냐하면 크기가 N인 배열이 있고 맨 앞에 원소를 삽입하기 위해서는 기존 N개의 데이터들을 한 칸씩 뒤로 이동시켜야 하기 떄문에 N개의 단계가 필요하고 마지막으로 맨 앞에 삽입하는 단계까지 총 N+1 단계가 걸린다.
삭제
배열의 삭제는 "특정 인덱스의 값"을 제거하는 과정이다.
let fruits = ["apple","banana","lemon","orange"]; let newFruits = fruits.splice(1,2); console.log(newFruits); // ["apple","orange"]코드 상으로는 한 단계만 걸리지만, 배열 중간에 비어 있는 메모리 셀이 문제이다. 배열 중간에 빈 공간이 있으면 비효율 적이므로 "orange"를 왼쪽으로 2칸 이동시켜야 한다.
=> 즉, 삭제하는 1단계, "orange"를 이동시키는 1단계 총 2단계가 필요하다.
삽입과 비슷하게 삭제에서의 최악의 시나리오는 첫 번째 원소를 삭제하는 것이다.let fruits = ["apple","banana","lemon","orange"]; let newFruits = fruits.splice(0,1); console.log(newFruits); // ["banana","lemon","orange"]=> 맨 앞의 요소를 삭제하는 1단계, 뒤의 요소들을 1칸씩 움직여서 요소가 3개이므로 3단계, 총 4단계가 필요하다.
=> 삭제의 최악의 단계는 N-1개의 요소를 움직이는 N-1단계, 삭제하는 1단계, 총 N단계이다..
집합과 배열의 차이
집합은 배열과 비슷하지만, 중복 값을 허용하지 않는 자료 구조이다.
배열과 집합은 4가지의 연산 중 1가지의 연산이 매우 효율성 측면에서 차이가 난다.
바로 삽입이다..
왜냐하면, 집합은 중복을 허용하지 않는 자료 구조이다.
그렇다는 것은 어떤 데이터를 삽입할 때 집합 안에 해당 데이터가 있는지 검색까지 해야한다는 것이다.
=> 배열에서는 딱 한 단계만 필요했던 맨 끝에 삽입하는 경우도 집합에서는 최악의 경우 N개의 요소를 모두 중복하는지 확인한 후에 삽입하므로 N+1단계가 소요된다.
그리고 맨 앞에 삽입하는 경우에는 모두 탐색하는 N단계, N개의 데이터를 한 칸씩 뒤로 이동시키는 N단계, 마지막으로 삽입하는 1단계까지 총 2N+1단계가 소요된다.
결론
자료 구조의 성능 측정은 연산에 필요한 단계 수를 생각하며, 부하를 감당할 수 있을지 판단하여 프로그램에 맞는 자료 구조를 선택해야 할 것 같다.
