[Algorithm] 배열/정렬/탐색/재귀,복잡도_TIL Day1

1. 자료구조 & 알고리즘

자료구조 (data structure)

 - 문자열(string), 리스트(list), 사전(dictionary), 순서쌍(tuple), 집합(set) ...

 - 문제를 해결하기 위해 적합한 자료구조를 선택하고 활용할 수 있어야함 

 

알고리즘

 - 사전적 정의 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합

 - 프로그래밍 관점 : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

---

2. 선형 배열(Linear Array)

배열(Array)

 - 배열 : 원소들을 순서대로 늘어놓은 것

 - append() : 리스트 끝에 원소를 덧붙임 _ O(1)

 - pop() : 끝의 원소 삭제 및 해당 값 반환 _ O(1)

 - insert() : 원하는 인덱스에 원소 추가 후 뒤에 있는 원소들을 한개씩 뒤로 밈 _ O(n)

 - del() : 원하는 인덱스의 원소 삭제 뒤에 있는 원소들을 한개씩 앞으로 당김 _ O(n)

---

3. 정렬(Sort), 탐색(Search)

정렬 (L = list)

- 파이썬 내장 함수 sorted(L) : 사용 시 정렬된 리스트를 반환

- 리스트에 사용하는 함수 L.sort() : 사용 시 입력된 리스트를 정렬된 형태로 변경

- reverse = True 를 사용해 역순으로 정렬

- 문자열 리스트의 경우 알파벳 순서를 따름 (문자열 길이 상관없음)

- 문자열 길이로 정렬방법 : sorted(L, key = lambda x: len(x))

- Hash 정렬방법 :

   L = [{'name':'John',Score':83}. {'name':'Paul','score':92}]

   L.sort(key=lambda x:x['score'],reverse=True) -> 레코드가 높은 순으로 정렬

 

탐색 

- 선형 탐색 : 리스트의 앞에서 부터 순차적으로 탐색 _ O(n)

- 이진 탐색 : 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능 (크기 순 정렬을 이용한 알고리즘) _ O(log n)

- 이진 탐색 원리 : 리스트의 중간을 구함 -> 탐색 목표보다 작을경우 -> 중간의 왼쪽 원소들의 중간 값을 구하며 탐색범위를 좁힘 -> 반복 (중간 값이 탐색 목표보다 큰 경우 오른쪽을 탐색)

---

4. 재귀 알고리즘

재귀 알고리즘(recursive algorithms)

- 하나의 함수에서 자신을 다시 호출하여 작업을 수행

- 이진 탐색 구조를 트리형태로 만들어 재귀적으로 탐색하는 방법이 있음

- 주의 사항 : 무한루프가 될 수 있으므로 종결 조건이 매우 중요

- 재귀 알고리즘의 효율 : 일반적인 반복문과 시간복잡도는 같으나(O(n)) 재귀 알고리즘 사용 시 함수를 호출 및 리턴하는 비용이 추가되는 차이가 있음

일반적으로, 주어진 문제에 대해서 반복적인 알고리즘이 재귀적인 알고리즘보다 시간 효율이 높으나 트리(tree)와 같은 자료 구조를 이용하는 알고리즘에는 매우 직관적으로 적용할 수 있는 경우가 많습니다.

---

5. 알고리즘 복잡도

시간 복잡도(Time Complexity)

 - 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

 - 흔히 평균 시간 복잡도와 최악 시간 복잡도를 이야기함

공간 복잡도(Space Complexity)

 - 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

 

Big-O Notation

 - 점근 표기법의 하나로써 어떤 함수의 증가 양상을 다른 함수와 비교할 때 표현 (알고리즘의 복잡도를 표한할 때 표현)

 - O(logn), O(n) ... 등 입력의 크기에 얼마나 비례하는지

 - 병합정렬(O(nlogn)) = 데이터를 나눠 각각 정렬 후 작은 수 부터 병합을 진행

 - O(nlogn) 보다 복잡도가 낮은 알고리즘은 없음