데이터 구조와 알고리즘 기초

데이터 구조와 알고리즘의 정의

💡 데이터란?

글자와, 숫자로 이루어진 기호들의 집합

💡 알고리즘 이란?

어떤 문제를 해결하기 위한 절차
살펴보게 될 알고리즘, 데이터 구조 관련 알고리즘 (데이터 추가, 탐색, 삭제 알고리즘)
"Smart data structures and dumb code works a lot better than the other way around."
좋은 데이터 구조를 선정하고 최적의 알고리즘을 사용하는 것은 코드의 효율성을 높여준다.

알고리즘 복잡도

💡 알고리즘의 효율성?

알고리즘의 복잡도에 대한 점근적 분석 (n이 무한하게 커질 때 알고리즘의 효율성 분석)

• BigO 표기법
  - 빅오 표기법은 알고리즘의 시간 복잡도나 공간 복잡도의 상한을 나타내는 방법으로, 알고리즘의 최악의 성능을 나타내고 싶을 때 사용합니다.
  

1. O(1) : 이상적인 알고리즘로써 n이 아무리 커져도 실제로 소요되는 시간은 사실상 증가하지 않는다.
2. O(n) : 괜찮은 알고리즘로써 n이 커지면 그의 비례해서 실제로 소요되는 시간도 증가한다.
3. O(logn) : 바람직한 알고리즘로써 n이 커지면 실제로 소요되는 시간도 증가하지만 그 증가폭이 완만하게 증가한다.
4. O(n^2) : 부담스러운 알고리즘로써 n이 커지면 급격하게 실제로 소요되는 시간도 증가한다.
5. O(k^n) : 피해야 하는 알고리즘로써 n이 조금만 커져도 사실상 실행할 수 없는 알고리즘이 된다.

데이터 구조의 유형

💡 선형 데이터 구조

• 대표적인 선형 데이터 구조
  - Array, List, Stack, Queue

💡 트리 데이터 구조💡 해시 데이터 구조

• 해시 데이터 구조 특징
  1. key - value로 구성된 구조
  2. key값을 알면 value를 찾을 수 있기 때문에 시간 복잡도가 O(1)이다.
• 대표적인 선형 데이터 구조
  - dictionary, hash table

💡 그래프

• node와 edge로 이루어진 임의의 형태를 가진 자료구조