[TIL - 1일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (1)

안녕, 자료구조 & 알고리즘!

자료구조

• 문자열, 리스트, 사전, 순서쌍(튜플), 집합 등의 자료형이 존재하는데 "자료구조"는 왜 알아야 하는가?
• 리스트와 max 함수를 활용해서 최댓값을 찾아내는데, 원소의 개수에 비례하여 실행시간이 증가
• 무작위의 숫자가 주어졌을 때, 최댓값을 빠르게 얻을 수 있도록 하는 특정 자료구조가 존재
• 어떤 문제를 해결할 것인가에 따라 적절한 자료구조가 달라짐

알고리즘

• 사전적 정의 : 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
• 프로그래밍 : 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택
• 해결하고자 하는 문제에 따라 최적의 해결 방법이 달라지며, 방법을 선택하기 위해 자료구조 이해가 필요

선형배열(Linear Array)

• 배열 : 원소들을 순서대로 늘어놓은 것(ex. 2 7 -2 5 10)
• 리스트 : 서로 다른 자료형을 갖고 있어도 가능한 python의 데이터형

L = ['Bob', 'Cat', 'Spam', 'Programmers']

L[1]
# 'Cat'

L[-2]
# 'Spam'

리스트 연산

• L.append(x) : 맨 뒤 원소 덧붙이기, O(1)
• L.pop() : 맨 뒤 원소 하나 꺼내기, O(1)
• L.insert(i, x) : 중간 원소 삽입하기, O(n)
• L.del(x) : 중간 원소 제거하기, O(n)
• L.index(x) : 원소 탐색하기, O(n)

del()과 pop()의 차이점

• pop()은 지워진 원소를 반환하지만, del()은 반환하지 않음
• del이 pop() 보다 수행속도가 미세하게 더 빠름
• del()의 파라미터는 원소값, pop()의 파라미터는 인덱스

실습

리스트에 새로운 요소 삽입하기

정렬된 리스트 L에 새로운 원소 x를 올바른 위치에 삽입하는 문제이다.

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

리스트에서 원소 찾아내기

가장 먼저 생각난 방법과 배운 내용을 활용한 방법으로 해결해 보았다. 첫 번째 코드는 리스트 L을 한 번 순회하며 x값을 가진 원소의 인덱스를 찾아낸다. 두 번째 코드는 index()와 try-except 구문을 활용하여 x값을 가진 원소의 인덱스를 찾아낸다. try-except 구문과 index()는 자주 사용하는 문법이 아니었기에 코드를 작성하는데 시간이 꽤 걸렸고, 효율적으로 작성된 코드인지도 잘 모르겠다.

# index() 메소드 사용 X
def solution(L, x):
    index_list = []
    
    for i in range(len(L)):
        if x == L[i]:
            index_list.append(i)
    if len(index_list) == 0:
        index_list.append(-1)
    return index_list

# index() 메소드 사용 O
def solution(L, x):
    index_list = []
    i = 0
    
    while i < len(L):
        try:
            index_list.append(L[i:].index(x) + i)
            i = index_list[-1] + 1
        except:
            break
            
    if len(index_list) == 0:
        index_list.append(-1)   
    return index_list

정렬(Sort), 탐색(Search)

정렬

• 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업
• 문자열 리스트는 사전 순서(알파벳 순서)를 따름
• sorted() : 내장 함수, 정렬된 새로운 리스트를 반환 => 원래 리스트는 변화 X
• sort() : 리스트의 메서드, 해당 리스트를 정렬 => 원래 리스트가 변화 O
• 정렬의 순서를 반대로 하려면 reverse = True 인자를 추가(ex. L.sort(reverse=True))

문자열 리스트를 길이로 정렬하는 방법

정렬에 이용하는 키(key)를 지정하여 문자열 길이 순서로 정렬이 가능하다. 만약 길이가 같다면 앞에 있는 원소가 앞에 위치하도록 정렬된다.

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

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

키를 지정하는 또 다른 예

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

# 이름 순서대로 정렬
L.sort(key=lambda x: x['name'])

# 점수를 기준으로 내림차순으로 정렬
L.sort(key=lambda x: x['score'], reverse=True)

 

탐색

• 선형 탐색(Linear Search) : 순차적으로 모든 요소들을 탐색하여 원하는 값을 찾음, O(n)
• 이진 탐색(Binary Search) : 리스트가 이미 정렬돼 있는 경우에만 적용 가능, O(log n)

실습

이진 탐색을 구현해보는 실습 문제이다. lower과 upper를 활용하여 divide & conquer을 진행한다. 만약 L[mid] < x일 경우, L[mid]보다 큰 원소를 탐색해야 하므로 lower의 값을 변경한다. 또한 L[mid] > x일 경우, L[mid]보다 작은 원소를 탐색해야 하므로 upper의 값을 변경한다. lower <= upper의 조건은 lower과 upper이 엇갈렸을 때, 종료하는 것을 의미한다. 값이 엇갈리면 x값이 리스트에 존재하지 않는 것이므로 -1을 반환한다.

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

    return -1

재귀 알고리즘(Recursive Algorithms) 기초

• 재귀 함수 : 하나의 함수에서 자신을 다시 호출하여 작업을 수행
• 종결 조건(trivial case) : 재귀 알고리즘에는 반드시 필요
• 재귀적 표현은 사람이 이해하기는 좋지만, 성능은 효율적이지 않은 부분이 많음
• 이진 트리(Binary Tree), 자연수의 합(1 ~ n), 팩토리얼

실습

피보나치 수열을 구현해 보는 문제이다. 재귀적 방법과 반복적 방법으로 해결해 보았고, 실행시간의 경우 반복문이 훨씬 빠르다는 것을 확인하였다.

# 재귀적 방법
def solution(x):
    return fibo(x)

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

# 반복적 방법
def solution(x):
    if x <= 1:
        return x
     
    n1, n2 = 0, 1
    for i in range(x - 1):
        tmp = n1 + n2
        n1 = n2
        n2 = tmp
    return n2

재귀 알고리즘(Recursive Algorithms) 응용

• 조합의 수 구하기, 하노이의 탑, 피보나치 수열

실습

이진 탐색을 재귀 알고리즘을 활용하여 해결하는 문제이다. 빈칸 문제로 이뤄져 있었고 l > u, solution(L, x, l, mid - 1), solution(L, x, mid + 1, u)를 채워 넣었다.

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)

알고리즘의 복잡도(Complexity of Algorithms)

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

시간 복잡도

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

Big-O Notation

• 점근 표기법(Asymoptotic Notation)의 하나
• 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
• O(log n), O(n), O(n^2) 등으로 표기하며 계수는 중요하지 않음

복잡도 별 예시

• O(n) 예 : 무작위로 나열된 수에서 최댓값을 찾기 위한 선형 탐색
• O(log n) 예 : 크기 순으로 정렬된 수에서 특정 값을 찾기 위한 이진 탐색
• O(n^2) 예 : 삽입 정렬(Insertion Sort)
• O(nlog n) 예 : 병합 정렬(Merge Sort)
• 정렬 문제에 대해 O(nlog n) 보다 낮은 복잡도는 알고리즘은 존재할 수 없음이 증명돼 있음

결론

느낀 점

• 자료구조, 알고리즘 내용은 대학 수업에서 다뤘었기 때문에 수월하게 진행
• 문자열의 길이 별로 정렬하는 방법은 몰랐었는데, 생각보다 쉽게 가능한 부분이라 놀람

어려웠던 내용

• 아직 Python에 익숙하지는 않기에 문법이나 메서드 사용 미숙
• 재귀 알고리즘의 경우 항상 어렵다고 느끼는 내용 중 하나인데, 여러 번 학습하니 이해가 되는 듯함

참고 링크

[Python] 리스트 slice, pop, del 성능 비교 및 사용방법

https://brownbears.tistory.com/452