[DEV] 2주차. 자료구조/알고리즘(1)

1. 파이썬 데이터타입과 알고리즘

데이터타입

문자열 (str) : “string”
리스트 (list) : [5, 2, 3,7]
사전 (dict) : {“A” : 45, “B” : 3}
순서쌍 (tuple), 집합 (set), ..

데이터타입이 있음에도 자료구조를 알아야 하는 이유
- 기본적인 데이터타입으로 해결할 수 없는, 해결하기 어려운, 또는 자료구조로 더 효율적으로 해결할 수 있는 문제들이 있기 때문!
ex) 최댓값 찾기

import time

n = int(input("Number of elements: "))
haystack = [k for k in range(n)]

print("Searching for the maximum value...")

ts = time.time()
maximum = max(haystack)
elapsed = time.time() - ts

print("Maximum element = %d, Elapsed time = %.2f" %(maximum, elapsed))

알고리즘

주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
해결하고자 하는 문제에 따라 최적의 해법은 서로 다름!
이 선택을 하기 위해 자료구조를 이해해야 함

2. 선형 배열

파이썬의 list
- 0부터 시작
- 원소들의 데이터타입 상관없음
- l = ['Bob', 'Cat', 1, [3, 6]]

list 연산

리스트의 길이와 무관 (상수 시간) : $O(1)$

원소 덧붙이기 l.append('New')
끝에서 꺼내기 l.pop() -> ‘New’

리스트의 길이에 비례 (선형 시간) : $O(n)$

L = [20, 37, 58, 72, 91]
원소 삽입 L.insert(3, 65)
- index 3의 위치에 원소 65 삽입
- L = [20, 37, 58, 65, 72, 91]
- 원소를 삽입하고, 뒤의 원소들을 한 칸씩 오른쪽으로 옮기는 원리
원소 삭제 del(L[2])
- index 2 위치 원소 삭제 (58)
- L = [20, 37, 65, 72, 91]
- 원소를 삭제하고, 뒤의 원소들을 한 칸씩 앞으로 당기는 원리
del(L[2]) vs. L.pop(2)
- del은 원소 삭제만
- pop은 삭제 후 삭제한 원소 반환
원소 탐색 L.index(72)
- 72라는 원소의 인덱스 번호 반환 (3)

3. 정렬

sorted()
- 내장 함수
- 정렬된 새로운 리스트를 얻어냄
sort()
- 리스트의 메서드
- 해당 리스트를 정렬함 (리스트 변경)

L = [3, 8, 2, 7, 6, 10, 9]

L2 = sorted(L)
# L2 = [2, 3, 6, 7, 8, 9, 10]
# L = [3, 8, 2, 7, 6, 10, 9]


L.sort()
# L = [2, 3, 6, 7, 8, 9, 10]

반대로 정렬 : reverse = True
문자열로 이루어진 리스트: 알파벳 순서를 따름 & 대문자 > 소문자
문자열 길이로 정렬하려면 정렬에 이용하는 key 지정

L = ['abcd', 'xyz', 'spam']

sorted(L, key = lambda x: len(x))
# ['xyz', 'abcd', 'spam']

L = ['spam', 'xyz', 'abcd']
# ['xyz', 'spam', 'abcd']
# 길이가 같을 경우 상대적인 순서는 바뀌지 않음

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

L.sort(key = lambda x: x['score'], reverse = True)
# L = [{'name':'Paul', 'score':92},
#      {'name':'John', 'score':83}]
# 점수가 높은 순으로 정렬

4. 탐색

선형 탐색 (Linear Search)

앞에서부터 하나씩 순차적으로 비교하는 방법
리스트의 길이에 비례하는 시간 소요 -> $O(n)$
최악의 경우 모든 원소를 다 비교해 보아야 함

def linear_search(L, x):
    i = 0
    while i < len(L) and L[i] != x:
        i += 1
    if i < len(L):
        return i
    else:
        return -1

이진 탐색 (Binary Search)

리스트가 이미 정렬되어 있는 경우에만 적용 가능
크기 순으로 정렬되어 있다는 성질 이용
중간값과 찾으려는 값을 비교하여 리스트의 길이를 절반으로 줄여나가는 방법
한 번 비교가 일어날 때마다 리스트 반 씩 줄임 (divide & conquer) -> $O(logn)$

def solution(L, x):
    lower = 0
    upper = len(L) -1
    mid = (lower + upper) // 2
    
    while lower <= upper:
        mid = (lower + upper) // 2
        
        if x == L[mid]:
            return mid
        elif x > L[mid]:
            lower = mid+1
        else:
            upper = mid-1
    return -1

def solution(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid-1)
    else:
        return solution(L, x, mid+1, u)

5. 재귀 알고리즘

재귀 함수 (recursive functions)
- 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

ex) 이진 트리 (binary trees)
- 어떤 노드를 기준으로 왼쪽 서브트리의 원소들은 모두 작거나 같을 것
- 오른쪽 서브트리의 원소들은 모두 클 것
- 이 원칙을 모든 노드에 대해 재귀적으로 적용!
ex) 자연수의 합 구하기
- 1부터 n까지 모든 자연수의 합 구하기
- $S = \sum_{k=1}^{n} k$ -> $S = n + \sum_{k=1}^{n-1} k$
```
  def sum(n):
  if n <= 1:
      return n
  else:
      return n + sum(n-1)
```
- 중요! 종결조건을 반드시 명시해야 함

재귀 알고리즘의 효율

모든 재귀 알고리즘은 반복문으로 변경 가능
복잡도 측면
- Recursive version: $O(n)$
- Iterative version: $O(n)$
효율성 측면
- Recursive version은 n의 크기에 따라 함수를 호출하고 return하는 부가적인 작업이 필요
- 효율성은 Iterative version이 더 뛰어남

ex) 피보나치 순열

  def fibo(x):
      if x <= 1:
          return x
      return fibo(x-1) + fibo(x-2)

ex) 조합의 수 계산

n개의 서로 다른 원소에서 m개를 택하는 경우의 수
$nCm = \frac{n!}{m!(n-m)!}$

재귀적이지 않은 방법

  from math import factorial as f

  def combi(n, m):
      return f(n) / (f(m) * f(n-m))

재귀적인 방법

$nCm = (n-1)Cm + (n-1)C(m-1)$

  def combi(n, m):
  if n == m:
      return 1
  elif m == 0:
      return 1
  else:
      return combi(n-1, m) + combi(n-1, m-1)

효율성 측면에서는 떨어짐

재귀 알고리즘의 유용성

사람이 생각하는 방식을 그대로 코드로 옮길 수 있음

6. 알고리즘의 복잡도

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

평균 시간 복잡도 (ATC)
- 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
최악 시간 복잡도 (WTC)
- 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-O Notation

점근 표기법의 하나
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
$O(logn), O(n), O(n^2), O(2^n)$ 등으로 표기
입력의 크기가 n일 때
- $O(logn)$ : 입력의 크기의 로그에 비례하는 시간 소요
- $O(n)$ : 입력의 크기에 비례하는 시간 소요
입력의 크기가 커짐에 따라 얼마나 실행 시간이 증가하는가
계수는 그다지 중요하지 않음

선형 시간 알고리즘 $O(n)$

ex) 무작위로 배치된 수에서 최댓값을 찾기 위한 선형 탐색 알고리즘
- 끝까지 다 살펴보기 전까지는 알 수 없음
- Average case: $O(n)$
- Worst case: $O(n)$

로그 시간 알고리즘 $O(logn)$

ex) 크기 순으로 정렬된 수에서 특정 값을 찾기 위한 이진 탐색 알고리즘

이차 시간 알고리즘 $O(n^2)$

ex) 삽입 정렬 (insertion sort)
- Best case: $O(n)$
- Worst case: $O(n^2)$

보다 낮은 복잡도를 갖는 정렬 알고리즘

정렬 문제에 대해 $O(nlogn)$ 보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있음
ex) 병합 정렬 (merge sort)
- $O(nlogn)$
- 정렬할 데이터를 반씩 나누어 각각을 정렬시킴