(23.04.10) 자료구조/알고리즘1 - 선형배열, 시간복잡도

TIL은 그날 하루 본인이 어떤 공부를 하였는지 파악하기 위함입니다.
상세하게 기록하여 이후 본인이 어떤 공부를 어떻게 하였는지 파악할 수 있도록 하는 것이 중요합니다.

 

학습 주제

1. 자료구조를 왜 알아야 할까

- 파이썬에서 제공하는 데이터 타입으로 문제는 해결할 수 있다

- 그러나 그것만으로 해결하기 어렵거나, 효율적인 해결을 위해 자료구조를 알아야 한다

 

2. [특강] 코딩테스트에 대한 대비

- 문제의 본질을 이해하고 정보의 처리 흐름으로 추상화하는 과정을 갖는다

- 코드로 구현하기 위한 자료구조, 알고리즘 어휘력이 필요하다

---

주요 메모 사항 

자료구조

- 정보의 표현 방식과 여기에 정의되는 연산들의 집합 (삽입, 삭제)

- 자료구조에 따라 적용할 알고리즘이 달라진다

 

선형배열(Linear Arrays)

- 데이터들이 선처럼 일렬로 늘어선 형태 

- Python 의 List

연산	함수/예약어	시간 복잡도
덧붙이기	append(val)	O(1)
꺼내오기	pop()	O(1)
원소삽입	insert(i, val)	O(n)
원소삭제	del L[i]	O(n)
원소탐색	index(val)	O(n)

 

정렬

- 복수의 원소로 주여진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업

 

 

탐색 알고리즘

탐색 알고리즘	시간 복잡도	설명
선형 탐색(Linear Search)	O(n)	- 앞에서 부터 뒤로 순차적으로 찾는 방식 - 리스트 길이에 비례하는 시간소요 - Python의 index와 유사
이진 탐색(Binary Search)	O(log n)	- 정렬되었다는 전제가 필요 - 비교할 때마다 리스트를 절반씩 줄어들임

 

재귀 알고리즘

- 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법

- 종결조건을 명시해야 한다

 

재귀함수 VS 반복문
재귀함수와 반복문의 복잡도는 모두 O(n) 이나
재귀함수는 중복되는 함수를 호출해 효율적인 측면에서 불리함이 있다

 

알고리즘의 복잡도

• 시간복잡도 : 문제의 크기와 이를 해결하는데 걸리는 시간의 관계
• 공간복잡도 : 문제의 크기과 해결하는데 필요한 메모리 공간의 관계
• 평균 시간 복잡도 : 임의의 입력 패턴을 가정할 때 소요되는 시간의 평균
• 최악 시간 복잡도 : 가장 긴 시간을 소요하는 입력의 경우 소요되는 시간

종류	Big-O	설명	예시
상수시간	O(1)	입력 크기와 상관없이 일정한 실행 시간을 가짐	배열의 덧붙이기, 꺼내오기
선형시간	O(n)	입력 크기에 비례하여 시간이 증가함	선형탐색 알고리즘 (Avg, Worst) 삽입정렬 (Best)
로그시간	O(log n)	입력 크기가 커져도 실행 시간이 크게 증가하지 않음 *정렬을 전제한다	이진탐색 알고리즘
이차시간	O(n^2)	입력 크기의 커질수록 실행 시간이 급격히 증가함	삽입정렬 (Worst)
로그선형시간	O(n log n)	입력 자료가 커져도 실행 시간이 느리게 증가함 *입력이 무작위인 경우 로그선형이 효율적	병합 정렬

 

---

공부하며 어려웠던 내용

 

병합정렬