[1주차 - Day01] 어서와! 자료구조와 알고리즘은 처음이지?(1-1)

1. 자료구조와 알고리즘

---

파이썬의 기본적인 데이터 타입

문자열(str) : "This is a string"

리스트(list) : [5, 8, 2, 7]

사전(dict) : {'a':6, 'bc':4}

순서쌍(tuple)

....

자료구조를 왜 알아야할까?

자료구조라 함은, 어떤 데이터가 있고, 그 데이터에 대해서 행할 수 있는 연산들이 있는 무엇인가의 구조로 생각할 수 있다.

즉, 자료를 효율적으로 처리하기 위한 구조이다.

데이터가 있고 데이터에 행해지는 연산들이 있을 때 데이터가 늘어날수록 소요시간도 늘어난다.

따라서 각 자료구조의 특성을 알고 용도에 적합한 자료구조를 사용해야한다.

알고리즘(algorithm)이란?

• 사전적 정의 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
• 프로그래밍 : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대해 선택

해결하고자 하는 문제에 따라(응용 종류와 범위에 따라) 최적의 해법은 서로 다르다.

-> 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다.

2. 선형 배열

---

배열의 index는 0부터 시작

• 마지막에 원소 삽입하기 : .append()
• 마지막 원소 꺼내기 : .pop()

리스트 길이에 비례하여 실행 시간이 걸리는 연산

• 원소 삽입하기 : .insert()
• 원소 삭제하기 : .del()
• 원소 탐색하기 : .index()

3. 정렬, 탐색

---

정렬(sort())

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

1. 파이썬 내장함수 : sorted()
   정렬된 객체를 새로 생성
2. 리스트의 정렬 메서드 : .sort()
   현재 객체를 정렬

문자열(str)이나 사전(dict)인 경우의 정렬

문자열은 사전에 순서에 따라 정렬해준다.

>>> arr['xyz', 'abcd', 'efg']
>>> sorted(arr)
['abcd', 'egf', 'xyz']

lambda를 이용하여 soted의 key에 조건을 넣어줄 수 있다.

>>> sorted(arr, key= lambda x: len(x))
['xyz', 'efg', 'abcd']

사전(dict) 자료타입인 경우는 dict의 key값을 지정해준다.

>>> arr2
[{'name': 'abc', 'score': 50}, {'name': 'xyz', 'score': 30}]
>>> sorted(arr2, key= lambda x: x['score']) # score 항목을 기준으로 정렬
[{'name': 'xyz', 'score': 30}, {'name': 'abc', 'score': 50}]

탐색(Search)

복수의 원소로 이우러진 데이터에서 특정 원소를 찾아내는 작업

1. 선형 탐색(Linear Search)
   순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아냄
   (순차탐색(Sequential Search) 라고도 함)
   최악의 경우 모든 원소를 검사해야 함 -> O(n)
2. 이진 탐색(binary Search)
   한번 비교가 일어날 때마다 리스트의 반씩 줄어듬 (배열이 정렬이 되어 있어야한다.)
   -> O(logn)

4. 재귀 알고리즘 기초

---

재귀함수

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

반드시 종결 조건(Trivial Case)이 있어야한다.

def sum(n):
    if n <= 1:    #종결 조건(Trivial Case)
        return 1
    else:
        return sum(n-1) + n

재귀적 방법은 사람의 생각을 코드로 표현하기 편하지만, 반복적 방법에 비해서 효율성이 떨어지는 경우가 있다.

6. 알고리즘의 복잡도

---

알고리즘이 실행함에 있어 문제의 크기(일반적으로 데이터 원소의 개수)가 커짐에 따라서 자원(시간 또는 공간)을 얼마나 필요로 하는 가를 뜻함

• 시간 복잡도 : 문제의 크기와 이를 해결하느느 데 걸리는 시간 사이의 관계
• 공간 복잡도 : 문제의 크기와 이를 해결하는 필요한 메모리 공간 사이의 관계

시간 복잡도

• 평균 시간 복잡도(Average Time Complexity) : 임의의 입력 패턴을 가정 했을 때 소요되는 시간의 평균
• 최악 시간 복잡도(Worst-Case Time complexity) : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-O Notation

점근 표기법(asymptotic notation)의 하나

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현(알고리즘의 복잡도를 표현할 때 흔히 쓰임)

입력의 크기가 n일 때, O(n)은 입력의 크기 n에 비례하는 시간 소요를 뜻함

• O(n) : 선형 시간 알고리즘 ex) n개의 무작위로 나열된 수에서 최댓값 찾기
• O(logn) : 로그 시간 알고리즘 ex) n개의 크기 순으로 정렬된 수에서 이진 탐색을 이용하여 특정 값 찾기
• O(n^2) : 이차 시간 알고리즘 ex) 삽입 정렬의 Worst-Case
• O(n^3) : 삼차 시간 알고리즘