[Certi 세미나] 알고리즘 기초-선형 자료 구조

안녕하세요. 인턴 생활을 하면서 교육 받았던 내용을 복습하고 정리하고자 이렇게 찾아왔습니다..! 

이번 포스팅은 '알고리즘 기초'에 대해서 정리해볼텐데요, 크게 시간 복잡도, 공간 복잡도, 자료 구조와 같은 내용으로 준비해봤습니다. 재미있게 봐주세요 :)

---

📌 시간 복잡도

• 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간
• O(n), 빅-오 : 알고리즘의 성능을 나타내는 표기법.
  • 보통 알고리즘의 최악의 경우의 계산량을 나타내며, 낮을수록 성능이 좋다.
  • O(1) / O(log n) / O(n) / O(n^2)

📌 공간 복잡도

• 특정 알고리즘이 얼마나 많은 메모리를 차지하는가를 나타냄
• 시간 복잡도와 동일한 표기를 사용한다.

📌 자료 구조

자료의 표현과 관련된 연산으로, 자료의 구조에 따라 실행 시간이 달라짐.

• 자료 연산 : 추가, 제거, 정렬, 검색
• 선형 구조(Linear) : 자료를 구성하는 데이터가 순차적으로 나열된 형태
  • 배열, 연결 리스트, 스택, 큐
• 비선형 구조(Non Linear) : 자료를 구성하는 두 데이터 간의 연결이 순서가 없거나, 여러 개의 경로(path)가 존재하는 형태
  • 트리, 그래프

---

📌 큐(Queue)

선입선출(FIFO) : 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 자료구조

• 활용 : 운영체제 작업 스케쥴링, 프린터 대기목록
• 연산자 - Enqueue(=put/add)
• 파생 자료 구조
  • Circular Queue(원형 큐) : 큐를 원형으로 만드는 것으로 나머지 연산(모듈라) 필요
  • Priority Queue(우선순위 큐) : 들어간 순서와 상관없이 우선순위가 높은 데이터가 나온다.
• Tip : 큐 구현할 일이 있다면, 원형 큐를 만들도록 한다. → 배열로 간단하게 만들기 쉽다.

 

📌 스택

후입 선출(LIFO : Last In First Out) : 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 구조

• 활용 : 함수호출시 복귀 주소, 계산기 구현
• 연산자 - Push, Pop, isFull, isEmpty