[위코드] TIL(Today I am learned) -09

Data 구조 

 1. 데이터 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조작하는 방법

 2. 자료 구조의 종류에는 여러가지가 있으나 모든 목적에 부합하는 자료구조는 없습니다. 따라서 각각의 데이터 구조가 갖는 장단점을 잘 이해하여 상황에 맞는 데이터 구조를 사용하는 것이 중요함.

 3. 데이터 구조의 종류와 그것에 대한 사용방법을 익히는 것이 중요하지만, 제일 중요한 것은 자료구조의 본질과 컨셉을 이해하여 상황에 맞는 적절한 데이터 구조를 선택하는 것이 중요함.

 

왜 데이터 구조인가?

 1. 데이터에 맞는 적절한 자료 구조를 사용하는 것은 전제 개발 시스템에 큰 영향을 끼칩니다.

 왜 그럴까요? 예시를 들어보겠습니다. 17인치 3kg 짜리 노트북이 있습니다.

이때 여러분은 이 노트북을 직접 들고다니거나 아니면 가방, 파우치, 크로스백, 메신저백 등을 사용할 수 가 있습니다.

만약 직접 들고다니면 어딘가에 부딪히거나 아니면 들고다니기 힘들어 무척 피곤해할 수 도 있습니다.

메신저, 크로스백에도 넣고 다니기 힘들어 매우 끙끙 될수가 있죠. 결국 여기선 가방이 제일 편한 데이터구조가 되는 것입니다. 다른 데이터(메신저, 파우치, 직접들기, 크로스백 등)은 너무 무겁거나 힘들게 작동되는 구조가 되는 것입니다. 그렇기에 올바른 자료(data) 구조는 매우 중요합니다.

 

자료구조의 분류

  1.Primitive Data Structure(단순구조)

     프로그래밍에서 사용되는 기본 데이터 타입

  2.None-Primitive Data Structure(비단순 구조)

     단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조

      2-1) Linear Data Structure(선형구조)

               저장되는 자료의 전후관계가 1:1인 구조(List, Stacks, Queues)

      2-2) None-Linear Data Structure(비선형구조)

               데이터 항목 사이의 관계가 1:N 또는 N:M(Graphs, Tress)

 

이외에도 일반적으로 가장 사용되는 자료 구조로

Array (파이썬에선  list)

Tuple

Set

Dictionary

Stack & Queue

Tree

 

Array(list)

 1. 정의

    1-1) 자바스크립트에선 Array, 파이썬에선 list로 칭함.

    1-2) Array(list) 배열은 가장 기초적이고 단순하면서도 가장 자주 사용되는 자료구조.

일반적으로 파이썬에서는 Array보다 List가 더 많이 사용되며 대부분의 경우 큰 차이가 없으므로 LIST를 사용하면 된다. 사실 파이썬에서는 List가 Array라고 생각해도 무방. 하지만, List == Array이지 List === Array는 아님을 기억해야한다. 메모리 효율면에서 Array가 유리하지만, 사용하기에는 List가 편하니 이점을 기억하자.

  2. Array의 특징

    2-1) 순차적으로 데이터를 저장하는 자료(data)구조

      2-1-1) Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 점.

      2-1-2) 자료구조에 저장하는 데이터는 일반적으로 요소(element).

      2-1-3) Array는 주로 서로 연결된 데이터들을 순차적으로 저장할때 사용함.

      2-1-4) 순서가 상관없더라도 서로 연결된 데이터들을 저장할때 일반적으로 사용.
               (객체와 비슷한데? 참고로 객체는 순서가 없다.)

      = Array가 가장 사용되는 자료구조 중 하나가 되는 이유.

 

      2-2) 기타특징

         삽입되는 순서대로 저장

         이미 생성된 리스트도 수정 가능

         동일한 값도 여러번 삽입 가능

         Multi-dimensinal Array(다중차원 배열)

             Array의 요소가 array가 될 수 있다. 이러한 이중이상의 구조를 다중차원 array라고 함.

 

 

      3. Array 내부구조

        3-1) Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것.

        3-2) 이렇게 순서가 있다보니 당연히 순차적으로 번호를 지정할 수 있습니다.

                이를 index라고 함.

        3-3) 인덱스 요소는 0부터 시작하는데, 특이하게도 마이너스(-)를 가질 수도 있습니다. 

              이 경우에는 오른쪽(맨 순서 마지막)부터 시작합니다.

 

        3-4) 그렇다면 왜 Array가 순차적으로 데이터를 저장할 수 밖에 없을까요?

            3-4-1) 실제 메모리에서 물리적으로 데이터가 순차적으로 저장되므로 그러함.

            3-4-2) 데이터에 순서가 있으므로

                    3-4-2-1) index가 존재

                                 0부터 index의 길이까지 존재.

                    3-4-2-2) indexing 

                                 index를 이용한 특정한 요소부터 Array(List)를 읽어 들이는 것이 가능.

                    3-4-2-3) Slicing

                                요소의 특정 부분을 분리해 따로 조작이 가능

        4. 단점

           4-1) Removing or Adding Elements

                중간의 특정요소를 삭제해야하는 경우 추가적으로 다른 요소들을 한칸씩 앞으로 이동시켜야합니다.

                이는 배열에서 요소를 삭제하는 경우 다른 자료구조에 비해 느릴 수 있다는 뜻이므로 

                정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않습니다.

            4-2) Array Resizing

                리사이징이란 사이즈를 다시 조정한다는 뜻을 가집니다.

                배열은 메모리가 순차적으로 채워짐에 따라 배열을 처음으로 생성했을 때 미리 할당하는데, 이를 Pre-                        allocation이라 합니다.  하지만, 새로 추가되는 요소가 처음 할당한 메모리 이상으로 많아진다면 resizing이                  필요합니다. 메모리를 기존보다 추가하는 것을 resizing이라고 합니다.

                하지만, 이러한 리사이징은 메모리 사용에 비효율적입니다. 

                우리가 생각하기에는 단순히 그 다음부터 추가해야하지만, 컴퓨터는 분산저장을 하기때문에 이를 수집하여                  다시 저장해야하기때문입니다.

                간단히 100만큼을 사용하다가 101부터 필요하다고 칩시다.

                우리가 생각하기에는 그냥 101부터 쓰면 되지만, 컴퓨터에선 이를 100을 복사하고, 100만큼의 숫자를 더                    할당합니다. 즉, 200만큼의 공간이 추가적으로 필요하기 때문입니다.

              * 이러한 이유로 Array는 사이즈 예측이 되지 않는 데이터를 다루는 데 있어서 적절하지 못 합니다.

              * 그렇기때문에 데이터의 사이즈(용량)이 급격하게 증가할 필요가 있는 데이터(data:자료)들에게는

                다른 구조가 필요합니다.

 

          5. 언제 사용하면 되는가?

             5-1) 순차적인 데이터를 저장할 때

             5-2) 다차원 데이터 사용

             5-3) 어떤 특정한 요소를 빠르게 읽을때

             5-4) 데이터의 사이즈가 급변하지 않을 경우

             5-5) 요소가 자주 삭제되거나 추가 되지 않는 경우             

 

  Tuple 

     1. 정의

        튜플이란? 

          list와 마찬가지로 데이터를 순차적으로 저장하는 순열 자료구조

          하지만 list와 다르게 한번 정의되고 수정이 불가능합니다.

          2~3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 사용합니다.

          함수에서 리턴값을 한개 이상 리턴할 때 자주 사용됨.

     

파이썬에는 튜플이 있고, 자바스크립트에는 없습니다. 이것은 파이썬이 우월한 언어인 것이 아니라 그냥 자바스크립트에서 안 만든 것입니다.

 

      2. 튜플의 장점

        2-1) 간단한 값을 빨리 표현하고 싶을때 많이 사용.

        2-2) 예를 들어 함수에서 리턴 값을 한개 이상 리턴하고 싶을 경우(ex 지도 좌표)

      

 

      3. 튜플의 단점

         3-1) 데이터가 무슨 의미인지 명확하지 않음.

         3-2) 데이터의 의미를 문맥을 보고 가정해야 한다.

              key-value가 있는 경우 쌍으로 이루어졌기에 무슨 데이터인지 의미 파악이 쉽지만 

              튜플의 경우 단순히 괄호안에 있어 문맥에 따라 의미를 추측해야합니다.

          3-3) 튜플은 소규모 데이터 다루기에 적합합니다.

          *  이러한 단점을 해결하기 위한 Named Tuple이란 것도 존재합니다.(파이썬)

 

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

          Array(list)를 쓰기에는 간단한 데이터를 표현할 떄 사용합니다.

            Tuple이 Array(List)보다 가볍고 메모리를 더 적게 먹습니다.