[📗c언어 쉽게 풀어쓴 자료구조1] 자료구조와 알고리즘

👑 자료구조와 알고리즘

• 자료구조: 자료를 정리하여 보관하는 구조(배열, 큐, 스택,,,등)
• 알고리즘: 자료들을 처리하는 절차(순서)-> 명령어들의 집합
  -> 의사코드

👑 추상자료형

: 명세와 구현이 분리된 자료형 (구현은 공개하지 않음)
-> 정보은닉기법: 핵심ㅈ먹인 구조나 동작에만 집중
-> 객체와 함수들 저장(인터페이스만)

👑 알고리즘 성능 분석

-> 알고리즘의 효율성 중요!!! (수행시간↓, 기억 공간↓)

1. 시간복잡도: 입력의 갯수(n)에 따른 수행시간

-> 수행 횟수(연산의 개수)와 연관: T(n)

• 빅오 표기법(O(n)): 불필요한 정보들 제거 (차수가 가장 큰 항이 가장 큰 영향, 계수는 영향 적음)
  -> 가장 큰 차수의 계수까지 모두 다 제거
  -> 상한 표시 (최대 요정도 걸려~~)

✔ 수행시간 비교: O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2n)<O(n!)

• 오메가 표기법: 하한 표시 (요것보다 더 걸려~)

• 세타 표기법: 상한, 하한 표시

2. 공간복잡도: 자료들이 차지하는 공간의 양

⭕ TIL (Today I learned)

& 배운 내용 내 언어로 정리: 자료를 저장하는 형태가 자료구조이고, 그 자료들을 어떤 절차로 처리할지 그 순서를 정리해놓은 명령어들의 집합이 알고즘이다. 그래서 이 책에서는 그런 자료구조들을 배울 것임(스택, 큐, 그래프 등...)
알고리즘에서는 효율이 되게 중요해서 각 자료들 문제들에 대해서 적절한 알고리즘을 선택하는 것이 중요한데, 입력의 개수에 따른 시간복잡도 분석을 통해 효율적인 알고리즘을 선택할 수 있어. 그 시간복잡도를 알기 위한 방법 중 하나가 상한을 표시하는 빅오표기법임.
또, 추상자료형이라는 게 뭔지 헷갈렸는데, 그냥 어떤 객체가 해야할 일들을 표현하는 자료형을 말한다. 구체적으로 어떻게 구현되어있는지는 표현하지 않고, 이 객체로는 이러한 함수를 실행해라. 이정도로 표현하는 자료형이다. 그래서 여러 자료구조들에서 필요한 함수들과 작동 방법들을 이 추상자료형을 이용해서 나타낼 수 있음!