2024.06.07 TIL - 코딩테스트 강의 시작

자료구조

• 데이터를 저장하고 관리하는 방식
• 데이터를 체계적으로 저장, 메모리를 효율적으로 사용할 수 있게 함
• 빠르고 안정적인 데이터 처리
• 메모리 알고있어야 함
• 선형 자료구조, 비선형 자료구조

알고리즘

• 문제 해결, 방법
• 자주 쓰이는 문제 해결 방법이 있음 -> 패턴화
  (BFS, DFS, Binary Search, Dijkstra 등)
• 알고리즘을 평가할 수 있는 정도가 되어야 함

알고리즘 평가 기준

• 시간 복잡도 (Time Complexity) - 주로 이거 준비해게 될 것
• 공간 복잡도 (Space Complexity) - 우리나라에선 거의 안물어봄
• 구현 복잡도 - 얼마나 깔끔하게 구현하는지
  \
• 시간 복잡도 <-> 공간 복잡도는 trade-off 관계임
• 실행 시간을 계산할 수 있어야 함

메모리

• 데이터를 저장하는 곳

• HDD (하드디스크)

• RAM (램 메모리) : 비효율적인 자료구조 -> 램메모리 낭비 -> 프로그램 성능 저하

• 램 : 전기신호를 저장할 수 있는 트랜지스터라는 작은 반도체 반도체 소재로 이루어져 있음

  • 트랜지스터에 불 들어오면 1, 꺼지면 0 -> 2진수 (binary Digit) 표현 -> bit (한자리 - 0 또는 1 표현 가능)
  • 2 bit : 00, 01, 10, 11 4가지 숫자 표현 가능
  • 8 bit = 1 byte : 2의 8제곱가지 숫자 표현 가능
  • 16진법 (hexadecimal) : 2진법 앞에는 0b 붙이고, 16진법 앞에는 0x 붙임

메모리 할당

• List 구현 방법 2가지 : Array, Linked List
  = Array : 메모리상에서 연속적으로 할당됨
  
• Linked List : 메모리상에서 불연속적으로 저장됨
  -> value, address도 함께 저장 -> 둘이 함께 저장된걸 Node라 칭함

시간 복잡도

• Big-O : 점근 표기법
  

• O(1)
  

• O(n)
  

->
최고차항으로 Big-O를 표기함

• C = O(1)
• an + b = O(n)
• an2 + bn + c = O(n2)