Data Structure, 자료구조

• 데이터를 담는 '무언가', 공간 === 자료구조
• 데이터를 어떻게, 언제, 무엇에 이용할 것인지에 맞춰 자료구조를 선택
  (ex. 사과를 언제, 어떻게, 무엇으로 이용할 것인지에 맞춰 적당한 용기나 저장 공간이 필요)
• 자료구조가 많은 이유: 데이터를 가지고 활용을 하는 range가 다양하므로
• 가장 자주 사용하는 자료구조: array

1. array

• element를 나열한 것

• 순서가 있다, 메모리상에서도 순서를 가지고 저장(순차적으로 저장) ==> 'index' 존재

• 원하는 순서의 element에 바로 접근 가능(순서가 있기 때문에)

• slice도 가능

• Multi Dimentional Array: 다차원 배열

  • matrix
  • 2차, 3차, ....n차까지 가능

• array 단점:

• 연속적인 정보를 나열하기 위해 그에 걸맞는 정도의 공간을 확보하고 연속적인 정보를 넣어야 한다는 점. 'array resizing' 문제 발생
  ==> 이러한 문제가 자주 발생할 것 같으면 array가 아닌 다른 자료 구조를 사용해야 한다.

• 중간에 정보를 지우는 작업이나 앞에 자료를 넣는 작업이 자주 있어도 array 자료구조는 적합하지 않음

• When to Use Array:

• 순차열적인 데이터를 저장할 때

• 어떠한 특정 요소를 빠르게 읽어야 할 때

• 데이터의 사이즈가 급변하게 자주 변하지 않을 때

• 요소를 자주 삭제해야 하지 않을 때
  ex. 등수

2. Tuple

• 데이터를 순차적으로 저장할 수 있는 순열 자료구조. 하지만 업데이트가 안 됨(불가변성).
• 소규모 데이터를 정리할 때.
  ex. 좌표, 위치 데이터
• 여러 데이터가 아닌 2~5개 정도의 데이터를 넣을 때.
• 리스트보다 효율적으로 사용 가능, 메모리 상으로도 더 가벼움
• 클래스를 굳이 만들 필요 없는 자료구조일 경우
• 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 때.
• 단점:
• 값을 표기해줄 수가 없음(필드명이 없어 '가정'으로 대체)
  ==> 'Named Tuple' 등장, 필드명을 지정해줄 수 있음

3. Set

• list처럼 순열 자료구조, 순서가 없는 나열 => 인덱스가 없다.

• 중복된 값이 허용 안 됨. 중복된 값이 있으면 하나로 치환
  ex. 전화번호, 자동차 번호판,

• set가 저장되는 방법: 값이 들어오면 단방향 해쉬를 적용해 해쉬값에 해당하는 메모리에 그 값을 저장. 똑같은 값이 들어오면 원본값이 같으므로 똑같은 해쉬값이 도출되므로 하나의 메모리로 치환되는 것.

• 해쉬값으로 원하는 해당 메모리에 가서 값을 찾아볼 수 있음. 값을 찾는 속도가 빠름. lookup이 엄청 빠르다. 빠르게 원하는 값을 찾을 때 쓰면 좋다.

원하는 결과를 어떤 자료구조를 이용해 어떻게 도출할 것인지가 정말 중요하다

• When to Use Set:
• 중복된 값을 골라내야 할때
• 빠른 look up이 필요할 때
• 순서가 상관없을 때

4. HashMap

• 'key'가 해쉬 기반의 자료구조로 순서가 없다.
  ==> 중복된 키로 저장이 안 됨. 중복된 키로 vlaue가 들어오면 늦게 들어온 value로 치환됨.

5. Stack / Queue

: 먼저 들어간 게 마지막으로 나오고, 마지막으로 들어간 게 먼저 나오는 ex. browser의 뒤로 가기. : 먼저 들어간 게 먼저 나오고, 마지막으로 들어간 게 마지막으로 나오는 ex. 줄 서는 거.

6. Tree 구조

: 나무 형태로 자료를 저장하는 구조

• binary search tree 구조: 작은 값이 왼쪽, 큰 값은 오른쪽, 중복된 값을 넣을 수 있음(set와 다른 점)