자료구조란?

• 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법
• 자료구조 종류에는 여러가지가 있으므로 각각의 자료구조가 갖는 장점과 한계를 잘 이해하고 상황에 맞게 올바를 자료구조를 선택하여 사용하는 것 중요하다.
• 언어별로 지원하는 양식이 다름
• 각 언어가 가진 자료구조의 종류와 그것에 맞는 사용법을 익히는 것도 중요하지만,각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료구조 선택이 중요하다.
• 언어별로 자료구조의 양상이 다르더라도 올바른 개념을 이해한다면 해당 언어에 맞춰 사용하기만 하면 된다.

왜 사용하는가?

• 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조
• 데이터에 맞는 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼칩니다.

  "코딩은 알고리즘과 자료구조, 이 두가지로 이루어진다" -리누스 토르발스-

자료 구조의 분류

• Primitive Data Structure(단순 구조)
  : 프로그래밍에서 사용되는 기본 데이터 타입

• None-Primitive Data Structure(비단순 구조)
  : 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조

  • Linear Data Structure(선형 구조)
    : 저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues)
  • Non-Linear Data Structure(비선형 구조)
    : 데이터 항목 사이의 관계가 1:n 또는 n:m (ex. Graphs, Trees)

자주 사용되는 자료구조

• Array(Python에서는 List)
• Tuple
• Set
• Dictionary
• Stack & Queue
• Tree

Data Structure

1. Array(List)

• Javascript에서는 Array,Python에서는 List
• Array는 가장 기초적이고 단순하면서 자주 사용되는 자료구조

2. Array 특징

순차적으로 데이터를 저장하는 자료구조

• Array의 가장 큰 장점: 데이터를 순차적(ordered)으로 저장한다.
• 자료구조의 저장하는 데이터는 일반적으로 요소(Element)라고 한다.
• Array는 주로 서로 연결된 데이터를 순차적으로 저장할 때 사용합니다.
• 순서와 상관 없어도 서로 연결된 데이터들을 저장할 때 일반적으로 사용합니다.
• Array는 가장 많이 사용되는 자료구조중 하나 입니다.

기타 특징

• 삽입(insertion) 순서대로 저장(새로 삽입되는 요소는 array의 꼬리가 된다)
• 이미 생성된 리스트도 수정 가능(mutable)
• 동일한 값도 중복 삽입 가능
• Muti-dimensional Array(다중차원 배열)
  Array의 요소가 array가 될 수 있다. 이를 다중차원 배열 array라고 하고 일반적으로 2D(2차원) array가 많이 사용됨.
  
  

3. Array 내부 구조

• 순차적으로 번호를 지정할 수 있다 이를 index라고 합니다.
• index는 0부터 시작하고 -부호도 가질수 있습니다(-1은 맨 마지막 요소)

Array가 순차적으로 데이터를 저장하는 이유

• 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 떄문
• 데이터에 순서가 있기에
  - index가 존재(0부터 시작하는 index)
  • indexing(index를 사용해 특정 요소를 array로 부터 읽어 들이는 것이 가능)
    - Slicing(요소의 특정 부분(n번째 ~ m번째) 분리 조작이 가능)

4. 단점

1. Removing or Adding Element

• 중간에 특정요소를 삭제하는 경우 메모리는 항상 순차적으로 이어져있어야 하기 때문에 삭제된 요소로 부터 뒤에 있는 모든 요소들이 앞으로 한칸씩 이동해야됨
• 이뜻은 배열에서 요소를 삭제하면 다른 자료구조에 비해 느릴수 있다
• 중간에 추가하는 것도 마찬가지로 특정 위치에 요소를 새로 추가하면 그 뒤 요소들이 하나씩 밀리게 됨
• 그렇기에 Array는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절하지 않음

2. Array Resizing

• 사이즈를 다시 조정한다는 뜻

• 배열은 처음 생성될 때 어느 정도 메모리를 미리 할당함(pre-allocation)

• 처음 할당한 메모리 이상으로 요소가 추가된다면 resizing이 필요

• 추가적으로 할당된 메모리 또한 순차적이어야 함

• 그러므로 배열의 resizing은 상대적으로 오래걸리는 operation이다
  - 100개의 메모리 공간이 다 차서 100개를 추가하는 경우
  - 200개 크기의 메모리를 생성 후 > 기존 100개를 복사 > 101번 부터 데이터가 순차적으로 추가
  

• 그렇기에 Array는 사이즈 예측이 잘 안되는 데이터를 다루기에는 부적절 함

• 일반적으로 대부분의 언어는 배열의 메모리 pre-allocation,resizing을 자동으로 실행 하지만 이러한 점을 알고 있어야 사이즈가 급변할 확률이 있는 데이터는 array 말고 더 적절한 자료구조를 선택해야 한다

5. 언제 사용하면 좋을까?

• 순차적인 데이터를 저장(ex 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요)
• 다차원 데이터를 다룰 때 >>> Multi-dimensional Array
• 어떤 특정 요소를 빠르게 읽을 때 >> index를 통해 곧바로 읽을 수 있음
• 데이터의 사이즈가 급변하지 않을 떄
• 요소가 자주 삭제되거나 추가 되지 않을 때

2. Tuple

1. 정의 - Tuple

• List와 마찬가지로 데이터를 순차적으로 저장하는 순열 자료구조
• 한번 정의되면 수정할 수 없다(immutable)
• 2~3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 쓰임

Tuple Is Not For Every Language!
: Python 은 tuple이 있고 JavaScript는 없습니다. 그렇다고 Python > JavaScript 는 아닙니다! 다만 JavaScript에서는 tuple을 굳이 따로 안만든것 뿐입니다. Tuple은 list와 너무 비슷하기 때문에 굳이 제공하지 않는 언어도 많습니다. JavaScript에서는 그냥 array를 사용해도 상관없습니다.

2. 장점

• 간단한 값을 빨리 표현할때 사용

3. 단점

• Tuple 단점은 데이터가 무슨 의미인지 명확하지 않다는 것
• 데이터의 의미를 문맥을 보고 가정
  - 예를 들어 객체의 경우 key-value 쌍으로 이뤄져 있어 무슨 데이터 인지 파악이 쉽지만, Tuple 경우 괄호 안에 데이터만 담겨있어 문맥을 보고 가정해야 함
• 그렇게에 소규모 데이터를 다루기에 적합

4. 언제 사용하면 좋을까?

• Array(List)를 쓰기엔 간단한 데이터들을 표현할 때
  - Tuple이 Array(List)보다 더 가볍고 메모리도 더 적게 차지함
  • 예를 들어 좌표 데이터:

    coordinations = [
        (1, 2),
        (3, 4),
        (5, 6)
    ]

1. 자료구조의 정의와 중요한 이유를 설명하세요. *
   정의 - 데이터를 편리하게 접근하고 조작하기위해 데이터를 저장하거나 조장하는 방법
   중요한 이유 - 데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 괴장히 큰 영향을 끼친다.
   의견 보내기
   모범 답안 )
   자료 구조란 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법입니다. 문맥과 데이터의 종류에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼칩니다. 그렇기 때문에 자료구조의 다양한 종류와 각각의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요합니다.

2. Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요. *
   Array(List)의 가장 큰 특징 - 데이터를 순차적으로 저장한다.
   장점 - 다중차원 배열(Array요소가 array가 될 수 있음), 특정 요소를 빠르게 읽을 수 있음
   단점 - 배열의 요소를 추가 또는 삭제 시 해당 특정 요소들이 모두 이동을 해야되기 때문에 다른 자료구조 보다 느림
   의견 보내기
   모범 답안 )
   Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다. 이렇게 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다. 반면에 이에 따른 단점도 존재하는데, 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제 되는 경우 그 뒤의 모든 요소들을 한칸씩 뒤로 밀거나 당겨줘야 하는 단점이 있습니다. 이러한 경우 메모리 상에서 이루어지는 작업이 다른 자료구조에 비해 커지기 때문에 Array 는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절치 않습니다.

3. Array를 적용 시키면 좋을 데이터의 예를 구체적으로 들어주세요. (ex. 주식 차트) 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요. *
   Array를 적용시키면 좋은 예로 주식 차트가 있습니다. 주식 차트는 일정 시간 별로 변동한 주식 가격이 새로 저장되어야 되기 때문에 순차적으로 데이터를 저장할 수 있는 Array로 사용하는 것이 좋습니다. Array를 사용하지 않는 경우 순차적이지 않아 일정 시간별로 주식 가격을 확인하기 어려워 모든 데이터를 비교해야되는 비합리적인 일이 발생합니다.
   의견 보내기
   모범 답안 )
   Array를 적용시키면 좋은 예로 주식 차트가 있습니다. 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다. 즉, 순서가 굉장히 중요한 데이터 이므로 Array 같이 순서를 보존 해주는 자료구조를 사용하는 것이 좋습니다. 이와 같은 데이터에 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.