자료구조 & 알고리즘 - 1

자료구조

- 데이터를 효율적으로 조직화, 저장 및 관리하기 위한 방법을 제공

예시) 배열(Array)은 데이터를 순차적으로 접근하기에 적합한 자료구조

 

알고리즘

- 어떤 문제를 해결하기 위한 절차나 방법론

- 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

 

자료구조와 알고리즘의 관계

- 적절한 자료구조를 선택하면 문제를 해결하는 알고리즘의 성능을 향상

 

선형 배열(Linear Arrays)

- 선형 배열(Linear Array)은 데이터를 일렬로 저장하는 자료구조

- 일반적으로 인덱스를 사용하여 각 요소에 접근할 수 있고 Python에서는 리스트(List)라는 데이터형

- 메모리 상에서 연속된 공간에 데이터를 저장하며, 데이터를 빠르게 접근 가능

- 데이터를 순서대로 저장하며, 인덱스를 사용하기 때문에 원하는 위치에 삽입이나 삭제 간 다른 요소들의 이동 필요

 

Python List 연산

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

- append() - 리스트의 마지막에 요소를 추가

- pop() - 리스트의 마지막의 요소를 추출

 

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

- insert() - 리스트의 특정 위치에 요소를 추가

ex) list_name.insert(index, value)

- del() - 리스트의 특정 위치의 요소를 삭제

- index() - 리스트의 특정 요소의 위치를 반환

ex) list_name.index(value, start, end)

 

정렬(Sort)

- 주어진 데이터를 일정한 기준에 따라 순서대로 나열하는 것

Python 리스트의 정렬

- sorted() - 내장 함수(원본 리스트는 변하지 않음)

- sort() - 리스트의 메서드(원본 리스트는 변함)

* 기본값은 오름차순 / 내림차순(reverse = True 옵션 추가)

 

sorted안에 key에 lambda를 통해서 정렬 기준을 자유롭게 추가할 수 있다.

sorted(list_name, key=lambda x : x)

 

탐색(Search)

- 주어진 데이터에서 특정 값을 찾는 것

알고리즘 종류

- 선형 탐색(Linear Search): 리스트 길이에 비례하는 시간 소요(표기: O(n))

- 이진 탐색(binary Search): 리스트를 절반씩 분할하여 탐색 범위를 좁혀가며 찾는 알고리즘(표기: O(log n))

* 리스트가 이미 정렬되어있어야 함.

코드 예시)

def binary_search(list_, x):
    # 리스트의 인덱스 범위를 저장
    low, high = 0, len(list_) - 1
    
    # low와 high 변수가 교차할 때까지 반복
    while low <= high:
        # 리스트의 중앙에 위치한 인덱스를 계산
        mid = (low + high) // 2
        
        # 중앙값이 찾고자 하는 값과 같은 경우, 인덱스를 반환
        if list_[mid] == x:
            return mid
        
        # 중앙값이 찾고자 하는 값보다 작은 경우, 오른쪽 절반에 대해 이진 탐색을 수행
        elif list_[mid] < x:
            low = mid + 1
        
        # 중앙값이 찾고자 하는 값보다 큰 경우, 왼쪽 절반에 대해 이진 탐색을 수행
        else:
            high = mid - 1

 

재귀 알고리즘

- 재귀함수(recursive functions): 함수가 자기 자신을 호출하여 문제를 해결하는 것

- 이전 두 항을 더하여 현재 항을 구하는 수열로, 첫 번째 항과 두 번째 항은 각각 0과 1이고, 그 이후의 항은 이전 두 항의 합으로 구해진다.

- 하노이의 탑

- 조합의 수

- 피보나치 순열

코드 예시)

# 재귀함수
def solution(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return solution(x-1) + solution(x-2)

# 반복문
def solution(x):
    a, b = 0, 1
    for i in range(x):
        a, b = b, a+b
    return a

 

알고리즘의 복잡도

1) 시간 복잡도(Time Complexity): 알고리즘이나 프로그램이 실행되는 동안 소요되는 시간의 양

- 평균 시간 복잡도(Average Time Complexity): 알고리즘의 평균적인 수행 시간

- 최악 시간 복잡도(Worst-case Time Complexity): 알고리즘이 최악의 경우에 얼마나 오래 걸리는지

- Big-O Notation: 알고리즘의 성능을 분석하고 표현하는 방법 중 하나

표기법)

O(1) : 상수 시간 알고리즘
O(log n) : 로그 시간 알고리즘
O(n) : 선형 시간 알고리즘
O(n log n) : 로그 선형 시간 알고리즘
O(n^2) : 이차 시간 알고리즘
O(n^3) : 삼차 시간 알고리즘
O(2^n) : 지수 시간 알고리즘

 

2) 공간 복잡도(Space Complexity): 알고리즘이나 프로그램이 실행되는 동안 소요되는 메모리공간의 양

---

공부하며 어려웠던 내용

- 재귀함수의 구성과 재귀함수를 for문으로 변환시킬 때

- sorted의 key 조건에 쓰이는 lambda