1. 자료구조란📂

• 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미
• 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

---

1.1 자료 구조의 구분

1.1.1 선형 구조

스택 : 후입선출, 나중에 저정된 것이 제일 먼저 나온다
큐 : 선입선출, 먼저 저장된 것이 제일 먼저 나온다
데크 : 스택과 큐의 혼합 형태. 양 쪽으로 삽입과 삭제가 가능하다

1.1.2 비선형 구조

그래프 : 꼿짓점(Node)와 변(Edge)로 구성된다
트리 : 뿌리(Root)와 단 하나의 부모를 갖는 꼭짓점(Node)로 구성

2. 알고리즘이란📐

• 문제를 해결하기 위한 여러 동작들의 의미
• 어떤 기능이 일어나기 위해 내재된/독립된 단계적 명령어들의 집합
• 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 컴퓨터의 처리속도, 사용된 언어의 종류, 컴파일러의 속도에 달려있다.

3. 복잡도

• 입력값의 크기에 따른 함수의 증가량, 우리는 이것을 성장률이라고 부른다.
  이때 중요하지 않는 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한
  성장률에 집중할 수있는데 이것을 점금적 표기법(Asymptotic notation)이라 부른다
• 점금적 표기법은 오메가 표기법(최상), 세타 표기법(평균), 빅오 표기법(최악)이 있다. 일반적인 경우 최악의 경우인 빅오 표기법을 사용한다.

---

3.1 빅오 표기법(Big-O)

시간 복잡도 : 입력 크기에 따라 실행되는 조작의 수
공간 복잡도 : 실행 시 사용하는 메모리의 양

3.1.2 시간 복잡도

알고리즘의 성능을 설명하는 것으로 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 것이다. 시간복잡도에서 중요하게 여기는 것은 n의 단위 이다.

1				O(1)
2n + 20				O(n)
3n^2				O(n^2)

시간 복잡도의 문제 해결 단계

O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.

O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.

O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.

O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)

O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.

O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

3.1.3 자료구조와 복잡도

출처

https://opentutorials.org/course/2471/13912
https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0
https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity
https://blog.chulgil.me/algorithm/