자료구조와 알고리즘

자료구조와 알고리즘에 대해 알아보자

 

그 동안 자료구조와 알고리즘을 막연하게 생각해왔는데 본질적으로 알아 봐야겠다

https://www.youtube.com/watch?v=M2mcJvmYpWY 

한국외대 신창수 교수님의 자료를 보고 정리해볼까 한다.

자료구조란 어떤 data를 저장하기 위한 구조인데 이는 저장공간(memory) + 연산(읽기, 쓰기, 삽입, 삭제, 탐색) 의 구조를 가지고 있다.

 

이런 자료구조를 활용해 어떤 입력이 들어왔을 때 이를 유한한 횟수의 연산들을 통해 정답을 출력하는 논리적인 절차를 알고리즘이다.

 

자료구조의 예:

1. 변수(variable)

    a = 5 (쓰기연산)

    print(a) (읽기연산)

변수에는 값이 하나만 들어가기 때문에 삽입, 삭제, 탐색은 의미가 없다

python 내부에서는 a 안에 5가 저장되는 것이 아니라, 5라는 값이 저장되어있는 공간을 가리키는 주소를 a에 저장하게 된다. c에서의 pointer 주소와 같다.

2. 배열(array) , 리스트(list)

    A = [3, -1, 5, 7]

   

    접근 : 원소의 index를 통해 읽기, 쓰기가 가능 A[3]

    삽입 : A.append(X) , A.insert(a, b) -> a번쨰 위치에 b를 삽입

    삭제 : A.pop( ) -> 가장 마지막 값이 제거 , A.pop(2) 2번쨰 index의 값이 리턴(이경우에는 O(N))

gcd 구현

def gcd_sub(a,b):
    while a!=0 and b!=0:
        if a > b:
            a = a-b
        else:
            b = b-a
    return a + b
    
def gcd_mod(a,b):
    while a!=0 and b!=0:
        if a > b:
            a = a%b
        else:
            b = b%a
    return a + b
    
def gcd_recursive(a,b):
    while a!=0 and b!=0:
        if a > b:
            return gcd_recursive(a%b, b)
        else:
            return gcd_recursive(a, b%a)
    return a + b