[CodingTest] 자료구조, 알고리즘, 시간복잡도

자료 구조 (Data Structure)

• 대량 데이터를 효율적으로 관리할 수 있는 데이터 구조, 자료구조라고도 한다.
• 효율적인 데이터 처리를 위해, 데이터의 특성에 따라, 체계적으로 데이터를 구조화하는 것
• 효율적으로 데이터를 관리하는 예:
  • 우편번호: 5자리 우편번호로 국가의 기초구역을 제공
    • 5자리 우편번호에서 앞 3자리는 시, 군, 자치구를 표기, 뒤 2자리는 일련번호로 구성
  • 학생 관리: 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리
    • XX학년, X반, X번 학생
    • 만약 위 관리 기법이 없다면 3000명 학생중 특정 학생을 찾기 위해, 전체 학생부를 모두 훑어야 함

 

알고리즘 (Algorithm)

• 어떤 문제를 풀기 위한 절차/방법
• 어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍

 

알고리즘 복잡도 계산 항목

1. 시간 복잡도 : 알고리즘 실행 속도
2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

 

알고리즘 성능 표기법

• Big O (빅-오) 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ⁿ) < O(N!)

 

• Ω (오메가) 표기법 : Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법 : Θ(N)
  • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

---

잔재미코딩 온라인 강의 사이트입니다