📘 Data Structure & Algorithm w/ 노마드코더

Preface

📌 개발 공부 8개월 차인 to-be 개발자의 자습 blog🙂ﾠMar 20 ~ 26, 2022

현재 상태
너무 어려워 보여서 외면하다가 이제서야 들여다본 자료 구조와 algorithm

Summary

Data Structure

data는 현대의 기름과 같다.
FE는 BE로부터 못생긴 JSON data를 가져가 예쁜 UI로 구현하고 BE는 data를 검색, 편집, 수정, 추가 등을 관리한다.
data를 어떤 구조로 정리하느냐에 따라 application의 속도가 좌우된다.
어떤 목적에 두고 있는지에 따라 어떤 구조로 관리할지가 달라진다.

Algorithm

목적을 달성하기 위해 computer가 수행해야 하는 여러가지 지시 사항이다.
즉 따라야 하는 절차 (step) 이다.
e.g. 지도, 압축, 암호 algorithm

✔️ Time Complexity

data 구조의 operation 혹은 algorithm이 얼마나 빠른지 측정하는 방법이다.
시간으로 측정하는 속도는 computer라는 hardware가 결정하므로 algorithm의 속도는 실제 시간을 측정하는 것이 아닌 '완료까지 걸리는 절차의 수 (단계)'로 측정한다.

평균 scenario가 기준이므로 best scenario가 있는지 살펴보아야 한다.
worst scenario가 기준이나 경우에 따라 best scneario가 있는지 살펴보아야 한다.

• Big-O
  • O(1)
  • O(N)
    • linear search
  • O(N²)
    • nested loops가 있을 때 발생
  • O(logN)
    • binary search

✔️ Memory

• Volatile Memory
  • computer를 끄면 data가 모두 휘발되고 없음
  • 변수를 설정하면 RAM에 저장됨
  • RAM에서 data를 읽는 것이 hard drive에서 읽는 것보다 빠름
    *RAM : Random Access Memory
    (memory 주소에 '접근'하기 쉽다고 했지 값을 알기 쉽다고는 안 했다...)
• Non-volatile Memory
  • computer를 껐다 켜도 hard drive의 data가 휘발되지 않고 그대로 있음

(1) 자료 구조를 설계할 때의 네 가지 operation 상황

• reading
• searching
• insertion
• delete

(2) 자료 구조의 종류

• array
  • RAM 덕분에 많은 자료를 읽을 때 유용
  • 검색할 땐 하나하나 열어보고 확인해야 해서 오래 걸림
    • linear search여서 시간 복잡도 O(N)
  • 맨 앞에 삽입하거나 미리 배정한 공간을 초과해서 data를 삽입해야 할 때 단계가 많아짐
    • 맨 끝에 삽입하는 게 빠름
  • 맨 앞을 삭제할 때 뒤에 있는 요소를 다 당겨야 함
    • 맨 끝을 삭제하는 게 빠름
• hash table
  • 'key: value' system으로 자료를 정리
  • 내부가 array 구조이지만 hash function이 내가 저장하고 싶은 key를 숫자로 변경해 index로 저장하므로 index 없이 key에 해당하는 value를 찾을 수 있음
  • 읽기, 찾기, 삽입, 삭제 모두에서 step이 한 개이므로 시간 복잡도 O(1)
    ref. JavaScript의 Object, Python의 Dictionary, Go의 Map...
  • hash collision이 발생하면 내부에 새로운 array를 만들어 linear search로 value를 찾는데 이 때문에 hash table이 항상 O(1)은 아니게 됨 (평균이 O(1)라는 말)
• queue
  • programming 언어에 존재하지는 않음
  • code로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 추상적 data 구조 (Abstract Data Type)
  • first in first out (FIFO) : 맨 앞에 있는 data만 읽거나 삭제할 수 있음
    e.g. web site 뒤로가기 button, Ctrl + Z
• stack
  • programming 언어에 존재하지는 않음
  • code로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 추상적 data 구조 (Abstract Data Type)
  • last in first out (LIFO) : 맨 뒤에 있는 data만 읽거나 삭제할 수 있음
    e.g. mail 전달, push 알림, shopping mall 선착순 주문, call center의 back-end

(3) algorithm 종류

배열에서

• searching
  • linear search
    • 시간 복잡도 O(N)
    • 처음부터 순서대로 목표 값을 찾음
    • 목표 값이 맨 끝에 있거나 없을 때 오래 걸림
    • input이 많아짐에 따라 수행 시간도 오래 걸림 : linear time complexity
  • binary search
    • 정렬된 배열에서만 사용 가능
    • 정렬에 맞게 적합한 자리를 찾은 후 배치해야 하므로 삽입할 때 오래 걸림
    • 반씩 쪼개어 필요 없는 쪽은 버리면서 값을 비교하므로 검색할 때 빠름
    • 큰 배열에서 검색하기 좋지만 정렬이 선행되어야 함
• sorting
  • bubble sort
    • 시간 복잡도 O(N²)
    • N-1만큼 비교
    • 가장 많이 하면 N만큼 swap
    • 이해하기 쉬운 sorting 방법이나 비효율적이어서 잘 안 쓰임
  • selection sort
    • 시간 복잡도 O(N²)
    • N-1만큼 비교
    • 가장 많이 하면 한 cycle에 한 번 swap
  • insertion sort
    • 시간 복잡도 O(N²)
    • 셋 중 유일하게 O(N)라는 최고의 scenario가 발생함

---

Endnote

🔗 related documents

VISUALGO

🙇 the source of this content

노마드 코더 Nomad Coders - 알고리즘.데이터구조 with Nico