[Datastructure] 자료구조와 알고리즘

자료구조와 알고리즘

자료: data
구조: 저장공간(memory) + 연산(읽기,쓰기,삽입,삭제,탐색)

알고리즘: 입력된 data를 기준으로 유한한 횟수의 연산을 반복해서 정답을 출력하는 것

자료구조

자료구조의 예시

1. 변수(variable)

```
a = 3 (쓰기연산)
print(a) (읽기연산)
```
3이 a에 담기는 것이 아닌,  
3이 들어있는 <u>객체의 주소</u>가 a에 담기는 것이다. ### 2. 배열(array)
```
a = [1,2,3,4]

접근: 각 원소의 index(0부터시작)
a[0] = 1


읽기, 쓰기: index값을 이용해 접근하고, 읽기쓰기가능.
print(a[0]) = 1
a[0] = 3 
-> a = [3,2,3,4]

삽입
a.append(9) 
-> a = [3,2,3,4,9] 
a.insert

삭제
a.pop()
->리스트의 마지막 원소 삭제하고 리턴한다.
a.pop(2)
->리스트의 인덱스2를 가진 원소를 삭제하고 리턴한다.
```
리스트도 변수와 동일하게 
각 원소는 각 원소 객체의 주소가 리스트의 인덱스에 담기는 것이다.

알고리즘

알고리즘의 예시

최대공약수(gcd) gcd(8,12) = max{1,2,4} = 4 한쪽이 0이 될때까지 큰수에서 작은수를 빼자

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

만약 gcd(2,100) 이라면 50번의 while문을 반복해야한다.



이런 불필요함을 해결하기위해, 우리는 새로운 함수를 만들어야한다.
작은 수를 큰 수로 나눈 나머지로 표현을 한다면,

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

1번만에 gcd(2,100) -> gcd(2,0)이 된다.


또 다른 방법으로는 재귀함수를 만드는 방법이 있다.

    def gcd_rec(a,b):
        if a > b:
            gcd_rec(a%b,b)
        else:
            gcd_rec(a,a%b)

참고자료

개인적인 공부를 위한 글이며, 모든 저작권은 신천수 교수님께 있습니다.
자세한 강의 내용은 신천수 교수님 강의를 참고하시면 좋을 것 같습니다.
신천수 교수님 자료구조 강의