1강: 자료구조 & 알고리즘

파이썬 자료형 종류

1. 문자열 (str)
2. 리스트(list)
3. 사전(dict)
4. 튜플(tuple), 집합(set), ...

일반적으로 문자열과 리스트를 많이 사용한다

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

자료구조: 자료를 효율적으로 처리하기 위한 구조

데이터가 있고 데이터에 행해지는 연산(최대값 찾기, 특정 위치에 새로운 원소 삽입 등)들이 있을 때 데이터가 늘어날수록 소요시간도 늘어난다.

소요시간을 줄이기 위해서는 각 자료구조의 특성을 알고 용도에 적합한 자료구조를 사용해야 한다.

알고리즘 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합

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

복잡하게 나열되어 있는 수열에서 특정 값을 찾는 것보다 정렬되어 있는 수열에서 특정 값을 찾는 것이 쉽다!

🏃‍♂️실습: 리스트 원소 두 개의 합 구하기

문제 설명

입력으로 주어지는 리스트 x 의 첫 원소와 마지막 원소의 합을 리턴하는 함수 solution() 을 완성하세요.

제출

def solution(x):
    return x[0] + x[-1]

2강: 선형 배열

선형 배열(Linear Array)

데이터들이 선(line)처럼 일렬로 늘어선 형태

Python에서는 list 데이터타입을 사용

리스트 연산

배열의 index는 0부터 시작

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

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

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

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

🏃‍♂️실습1: 정렬된 리스트에 원소 삽입

문제 설명

리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution() 을 완성하세요.

• 힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다.
• 주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처리해야 합니다.

제출

def solution(L, x):
    for i in range(len(L)):
        if x < L[i]:
            L.insert(i, x)
            return L
    return L + [x]

🏃‍♂️실습2: 리스트에서 원소 찾아내기

문제 설명

인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수 solution() 을 완성하세요.

• 힌트 1: 리스트의 index() 메서드와 리스트 슬라이싱을 활용하는 것이 한 가지 방법이 됩니다.
• 힌트 2: 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 를 일으킵니다. 이것을 try ... except 로 처리해도 되고, if x in L 과 같은 조건문으로 특정 원소가 리스트 내에 존재하는지를 판단해도 됩니다.

제출

def solution(L, x):
    return [i for i, a in enumerate(L) if a == x] or [-1]

3강: 정렬, 탐색

정렬(Sort)

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

Python에서는 정렬 기능이 내장되어 있음

1. 파이썬 내장함수 sorted()
2. 리스트의 정렬 메서드 .sort()

수치(number)가 아닌 자료형(str, dict 등)이 들어있는 리스트의 정렬은?

문자열을 사전에 등장하는 순서에 따라 정렬해준다.

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

특정 조건을 기준으로 정렬하고 싶다면 lambda를 이용하여 key에 넣어준다.

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

Python에서는 대문자가 소문자에 보다 우선이다.

만약 대소문자를 구별을 무시하고 순전히 알파벳 순서에 따라 정렬하려면 아래와 같이 지정해주면 된다.

>>> arr.append(['Abcd', 'Zzz'])
>>> arr
['xyz', 'abcd', 'efg', 'Abcd', 'Zzz']

>>> sorted(arr)
['Abcd', 'Zzz', 'abcd', 'efg', 'xyz']
>>> sorted(arr, key= lambda x: x.lower())
['abcd', 'Abcd', 'efg', 'xyz', 'Zzz']

dict 자료형의 데이터가 들어있는 리스트에서 정렬할 때에는 dict의 key값을 지정해준다.

여러 데이터의 복합으로 이루어진 데이터 원소를 보통 데이터베이스에서 레코드(record)라고 하며 Python에서는 dict 자료형을 이용하여 표현

레코드들을 높은 점수 순으로 정렬하는 방법은 다음과 같다.

>>> 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(log n)$

일반적으로 이진 탐색이 선형 탐색보다 빠른 방법이기는 하나 무조건 좋은 방식은 아님!

(정렬되어 있지 않다면 정렬하는 시간이 소요되므로 오히려 선형 탐색이 빠를 수도 있음)

🏃‍♂️실습: 이진 탐색 구현해보기

문제 설명

리스트 L과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요.

제출

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

4강: 재귀 알고리즘 기초

재귀함수

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

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

반드시 종결 조건(Trivial Case)을 명시해야 함

재귀적으로 표현된 알고리즘은 사람이 이해하기 좋지만 성능이 좋지 않은 경우가 있음!

def sum_1_to_n(n):
    return n * (n + 1) // 2

🏃‍♂️실습: 피보나치 순열 구현하기

문제 설명

인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

제출

• 재귀적 방법

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

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Ff488b64d-5bc7-4c89-bf8e-54703ebc1140%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Ff488b64d-5bc7-4c89-bf8e-54703ebc1140%2Fimage.png)

• 반복적 방법

  def solution(x):
      fib = [0, 1]
      if x <= 1:
          return fib[x]
      for _ in range(x - 1):
          fib = [fib[1], fib[0] + fib[1]]
      return fib[1]

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fff00a2b7-5a5c-4c13-8709-07a5f014436d%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fff00a2b7-5a5c-4c13-8709-07a5f014436d%2Fimage.png)

5강: 재귀 알고리즘 응용

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

재귀적 알고리즘의 비효율적인 측면

• 조합의 수 계산

  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)

• 하노이의 탑

• 피보나치 수열

재귀적 방법으로 구현할 경우 반복적 방법으로 구현한 것에 비해 시간적 효율이 떨어짐

🏃‍♂️실습: 재귀적 이진 탐색 구현하기(빈칸)

문제설명

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요.

제출

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) # 빈칸

6강: 알고리즘의 복잡도

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

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

시간 복잡도

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

Big-O Notation

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

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

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

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

알고리즘의 복잡도를 표현하는 데에는 Big-O 표기법을 사용!