LIT_0 알고리즘(0)

LIT(Learn I Today) 내가 오늘 배운 것들에 대한 정리

---

선형 배열

---

선형 배열(Linear Arrays)이란 데이터들이 선처럼 일렬로 늘어선 형태. Python 에서는 리스트(list)라는 데이터형으로 구현.

---

리스트의 길이와 관계 없이 빠르게 실행 결과를 보게되는 연산

• 원소 덧붙이기 .append()
• 원소 하나 꺼내기 .pop()

리스트의 길이에 비례해서 실행 시간이 걸리는 연산들

• 원소 삽입하기 .insert()
• 원소 하나 꺼내기 .del()

추가 다른 연산

• 원소 탐색하기 .index()

---

정렬과 탐색

---

정렬이란? 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업.
Python에서는 리스트(list)를 이용한다면, 내장된 정렬 기능 사용 하여 직접 구현할 필요가 없다.

• Python 내장 함수 sorted()
• 리스트에 쓸 수 있는 메서드 .sort()

---

수치(number)가 아닌 데이터형의 정렬?

문자열을 사전에 등장하는 순서에 따라 정렬.
Python 문자열은 대문자가 소문자에 비해서 무조건 우선. 

---

탐색 이란? 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업.

• 선형 탐색 or 순차 탐색
  순차적으로 모든 요소들을 탐색하여 원하는 값을 찾는다.
  배열의 길이에 비례하는 시간이 걸린다. O(n)

• 이진 탐색
  탐색하려는 배열이 이미 정렬되어 있는 경우에만 적용.
  배열의 가운데 원소와 찾으려하는 값을 비교하면, 왼쪽에 있을지 오른쪽에 있을지 알 수 있다.
  이 과정을 반복하여 원하는 값을 찾는다.

재귀 알고리즘

---

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

수학시간 때 배우는 점화식과 같다.
알고리즘의 종결조건이 매우 중요하다

---