자료구조(Data Structure)?

  • 데이터를 표현하는 방법 및 구조

알고리즘(Algorithm)?

  • 데이터를 처리하는 방법

시간복잡도

시간복잡도 비교

  • 문제를 해결하는데 걸리는 시간으로 Big-O 표기법을 사용한다
  • 빅오를 구할 때 계수와 낮은 차수의 항은 제거한다
  • 시간 복잡도를 구하는 방법은 핵심 연산의 반복횟수를 구하면 된다

알고리즘에서 재귀함수를 사용하는 경우

  • 재귀로 접근하여 문제가 쉽게 풀리는 경우에 사용한다
  • 비재귀를 사용할 때보다 가독성이 높은 경우에 사용한다

선형 자료구조

선형 자료구조

  • 자료를 구성하는 원소들을 순차적으로 나열한 구조
  • 자료구조는 선형 자료구조비선형 자료구조로 구분된다

선형 자료구조의 예시

  • 배열: 데이터의 주소가 일정하게 붙어있다.
  • 배열리스트: 배열을 이용하여 항목의 추가, 삭제 등의 연산이 효과적으로 이루어지는 리스트 자료구조
  • 연결리스트: 포인터에 의하여 인접데이터들이 연결된 자료구조, 동적할당을 기반으로 한 리스트
  • 스택: 위에서 삽입, 삭제 ex) 프링글스 통
  • 큐: 앞에서 삽입, 삭제 ex) 줄 서기

비선형 자료구조의 예시

비선형 자료구조

  • 트리: 노드와 간선들로 이루어진 자료구조로 계층적 관계를 표현한다
  • 그래프: 연결되어 있는 객체 간의 관계를 표현하는 구조

ADT(추상 자료형)

  • 데이터 구조를 명세한 것
  • 다루는 데이터와 데이터를 다루는 작업의 집합

리스트(List)

리스트

  • Ex) 물품, 사람의 이름 따위를 일정한 순서로 적어놓은 것
  • 순차 리스트(배열 기반 리스트)
  • 연결 리스트(동적할당 기반 리스트)
  • 데이터를 나란히 저장한다
  • 데이터의 중복 저장을 허용한다

스택(Stack)

스택

  • 데이터 위에 데이터가 쌓이는 구조
  • LIFO(Last In First Out) -> 선입후출

큐(Queue)

큐

  • 데이터 앞에 데이터가 쌓이는 구조
  • FIFO(First In First Out) -> 선입선출

트리(Tree)

트리

  • 루트노드가 존재한다
  • 각 노드는 0개 이상의 자식노드를 가질 수 있으며 간선을 통해 노드를 연결한다.

예전에 정리한 자료