개발 아티클 스터디 4일차

배열과 리스트가 어떤 차이가 있는지 알아보자.

1. 배열

배열은 `연관된 데이터를 모아서 관리하기 위한 데이터 타입' 이다.

이렇게 변수는 하나의 데이터, 배열은 여러 개의 데이터가 담겨 있다.

그러면 배열은 어떤 특징을 가지고 있을까?

• 정적 자료구조

  • 배열의 크기를 선언할 떄 미리 정해놓아야 한다. 해당 크기 만큼의 연속된 메모리 주소를 할당 받기 때문이다. (하지만 자바스크립트는 동적 할당이기 때문에 자동으로 조절이 된다)

• 연속된 메모리 주소

  • 데이터는 선언이 되면 메모리 주소라는 것을 가진다. 해당 메모리주소에 접근하면 안에 있는 데이터를 사용할 수 있는 것이다. 때문에 변수의 이름을 다 외우지 않아도 된다.

• 인덱스 접근

  • 배열의 각 요소는 인덱스(Index)를 통해 접근이 가능하다.
  • 인덱스는 0부터 시작하며, array[0]과 같이 꺽쇠안에 인덱스를 명시하여 배열의 특정 위치에 있는 요소에 접근할 수 있다.

🙂배열은 이렇게 하나의 주제로 여러 변수를 선언할 필요 없이 연속된 공간을 만들어 데이터를 담아 편하게 접근하여 활용할 수 있다!

그러면 배열의 장단점을 알아보자!

배열은 다음과 같은 장단점이 있다.

• 장점

  • 인덱스를 통해 빠르게 접근이 가능
    : 여러 변수를 선언하는게 아니라 인덱스로 편하게 불러오는게 가능하다

  • 특정 인덱스에 접근하는 시간 복잡도가 O(1) 이다.
    : 정확한 인덱스를 알고 있다면 100, 많게는 10000 개의 데이터가 담긴 하나의 배열에서 콕 집어 데이터에 접근이 가능하다! (시간 복잡도는 나중에 설명)

• 단점

  • 배열의 크기는 고정되어 있기 떄문에 배열의 크기보다 더 많은 데이터를 저장할 수 없다.
    : 배열도 선언하고 데이터를 담는 공간이기 때문에 무한대의 크기일 수 없다.

  • 데이터를 중간에 삽입과 삭제하기가 번거롭다.
    : 한쪽이 막힌 뚫려있는 막대라고 생각하면 쉽다. 중간에 삽입하려면 배열에 담긴 요소를 움직여서 공간을 만들어야 하기 때문에 O(n)의 시간 복잡도 소요된다.

🤔 배열의 장점은 접근성이 빠르다는 것! 하지만 삽입과 삭제에는 번거롭다.

---

2. 리스트

리스트는 배열과 마찬가지로 여러 변수들이 담겨있는 것은 맞다.

하지만 데이터가 연속된 메모리 공간으로 있는 것이 아니다.

🤔 연속된 메모리 공간?

이렇게 배열의 경우 옆의 데이터와 '딱' 붙어 있는 것을 알 수 있다.
실제로 메모리 주소값도 연속적으로 되어 있다.
예를 들어, Array[0] 의 메모리 주소가 0001 이라고 치면
20->30->50->25의 메모리 주소가 연속적으로
0002->0003->0004->0005 라는 뜻이다.

하지만 리스트는 이런 연속적인 구조가 아니라는 뜻!

리스트는 새로운 것이 보인다
1. 데이터가 담긴 한 공간이 2개로 나누어져 있다.
2. Head와 Tail이 있다.
3. 다음 데이터 공간을 향하는 화살표가 있다.

위에 보이는 3개의 특징이 바로 리스트의 특징과 같다.

기본적으로 리스트는 노드(Node)라고 하는 데이터를 저장하는 부분과 다음 노드의 주소를 가리키는 포인터로 나누어진 공간을 가지고 있다.

🤔 포인터란?
포인터는 다른 변수, 혹은 그 변수의 메모리 공간 주소를 가리키는 '변수'이다.

사진에서 보이는 것처럼 하나의 노드 우측에 다음 노드를 가리키는 화살표를 볼 수 있을 것이다.
이것이 바로 포인터이다.

포인터에는 다음 노드의 주소가 담기기 때문에 이런 주소들이 이어져 하나의 연결된 리스트를 만드는 것.
이것이 바로 연결 리스트 (Linked List) 이다.

👉🏻 Head 와 Tail
리스트는 맨 앞부분을 뜻하는 Head, 맨 뒷부분을 뜻하는 Tail이 있다.

이는 리스트안에 담긴 데이터에 접근할 때 위치를 구분하기 위해 필요하다.
삽입과 삭제, 정렬, 데이터 찾기 등 여러 기능에서 쓰이게 된다.

리스트의 특징은 다음과 같다.

• 동적 자료구조

  • 크기를 미리 지정할 필요가 없다.
    필요에 따라 메모리를 할당받기 때문에 연속된 메모리 공간을 요구하지 않는다.

• 데이터 추가 및 삭제가 빈번할 때 유용

  • 이러한 이유는 포인터라는 노드가 가진 특징 덕분이다.
    중간에 데이터를 삽입하고자 할 때 포인터가 가리키는 방향을 새로운 데이터에 연결하기만 하면 되기 때문이다.

그렇다면 리스트의 장단점은 무엇일까?

• 장점
  • 크기에 제한이 없기 때문에 데이터 추가 및 삭제가 용이
  • Head, Tail에 가까운 노드를 삽입할수록 빠르게 처리 가능
• 단점
  • 특정 인덱스에 바로 접근이 불가
    : 배열과 다르게 인덱스를 탐색해야하기 때문에 Head, Tail에서 먼 노드일수록 시간 복잡도가 증가
  • 배열과 같이 인덱스를 통해 접근이 불가

이렇게 리스트는 배열과 같이 여러 데이터를 담을 수 있지만 포인터를 통한 동적 연결 및 메모리 구조를 가졌다.

---

3. 알고리즘과 시간 복잡도

우리는 어떠한 기능을 프로그래밍할 때 어떤 방법으로 하는 것이 최적인지 고민을 하게된다.
스스로도 이 방법이 제일 나을까? 할 것이다.

이러한 고민을 하는 이유에는 바로 최적의 결과물을 만들기 위해서이다.
버그, 에러, 결함을 최대한 방지하기 위해서이다.

알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정을 의미한다.
루트가 굉장히 다양하고 만들어낸 과정에 따라 도달하는 시간이 다르기 때문에 시간 복잡도가 가장 낮은 알고리즘을 선택해야 한다.

👉🏻 알고리즘 실행시간
알고리즘 실행시간은 입력값의 크기에 따라 검증해볼 수 있다.
입력값의 크기에 따른 함수의 증가량, 이것을 성장률이라고 부른다.

이 때, 중요하지 않은 상수와 계수들을 제거하면 알고리즘 실행시간에서 중요한 성장률에 집중할 수 있고, 이것을 점근적 표기법(Asymprotic notation)이라 부른다.

이 점근적 표기법이 바로 시간 복잡도를 나타내는 표기법이다.

⏲ 시간 복잡도

점근적 표기법은 세가지가 있다.

• 오메가 표기법 (Big-Ω Notation)
  : 알고리즘이 상한선이 없이 최소한의 실행 시간을 표기하고 싶을 때 쓰인다.
• 세타 표기법 (Big-θ Notation)
  : 알고리즘이 상한, 하한의 경계를 구분하고 그 사이의 근접한 실행 시간이 있음을 의미한다.
• 빅오 표기법 (Big-O Notation)
  : 세타 표기법에서 표기한 상한보다 더 큰 상한선(실행 시간이 더 커질수 있음)을 의미한다.

👉🏻 빅오 표기법(Big-O)
빅오 표기법은 불필요한 연산(상수나 계수)을 제거하여 알고리즘 분석을 쉽게할 목적으로 쓰인다.

Big-O로 측정되는 복잡성은 시간과 공간복잡도가 있다.

• 시간복잡도는 입력된 (N)의 크기에 따라 실행되는 조작의 수를 나타낸다.
• 공간 복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다.
  다만, 요즘은 메모리의 발전으로 중요도가 낮아진 편

위 그림은 Big-O 표기의 복잡도를 나타내는 사진이다.

각 표기는 추후 정렬, 자료구조, 반복, 입력 등을 최악, 최선, 평균, 최악의 상황에서 복잡도를 추론할 수 있다.

---

참고 자료
1. [개념 콕] 배열과 연결리스트
2. 알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기
3. Big-O Cheat Sheet
4. khanacademy - 점근적 표기법