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

출처 [신찬수 교수님 유튜브_자료구조와 알고리즘] : https://www.youtube.com/watch?v=M2mcJvmYpWY&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=2

1. 자료구조와 알고리즘의 개념

자료 : data

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

• 읽기 : 저장된 정보를 읽어온다.
• 쓰기 : 새로운 정보를 써넣는다.
• 삽입 : 필요에 따라서는 새로운 정보를 삽입한다.
• 삭제 : 기존에 불필요한 정보가 있다면 삭제한다.
• 탐색 : 원하는 정보를 탐색한다.

즉, 단순히 자료를 담을 수 있는 저장공간만 제공 하는 것이 아니라, 저장 공간에 담겨있는 자료를 읽고, 쓰고 할 수 있는 연산 기능으로 구성된 형태가 자료구조이다.

알고리즘 (algorithm) : 입력 데이터(자료구조에 저장된 자료)를 가지고, 유한한 횟수의 연산들을 반복하여, 원하는 정답을 출력하는 논리적인 절차

2. 자료구조의 예

1. 변수 (variable)

a=5 #쓰기연산
print(a) #읽기연산
"""
python에서는 변수 a에 5라는 값이 들어가는 것이 아니라, 5가 저장되어있는 객체의 주소가 a에 담긴다.
"""

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

A=[3,-1,5,7]
"""
A[0]은 3이라는 객체를, A[1]은 -1이라는 객체를~ 가리킨다.
자료 접근 방법 : 각 원소의 index
"""
A[3] #읽기, 쓰기
A.append(9) #삽입: 맨 마지막에 원소를 하나 더 마련하여, A[4]에 9라는 주소값을 저장한다.
A.insert #삽입
A.pop() #삭제: 아무런 매개변수가 없을 경우, 가장 마지막에 있는 원소 A[4]에 위치한 9를 return하고 이를 삭제한다.
A.pop(2) #삭제: 두번째 index에 있는 값이 삭제되고, 그 값이 return된다.

알고리즘 예) 100개의 정수가 리스트 A에 저장(입력)되어 있고, 이를 오름차순으로 정렬(출력)하라.

3. 알고리즘에 대하여

인류 최초의 알고리즘 : 최대공약수 (GCD) 계산 알고리즘 (By Euclid)

gcd(8,12) = max{1,2,4} = 4
#8과 12의 최대 공약수 = 8과 12의 약수인 1,2,4 중 최대값 = 4

방식 1. 빼기 (subtract)

<그림에 대한 설명>

1. 8은 길이가 4인 막대가 2개, 12는 길이가 4인 막대가 3개 있는 것과 같다.

2. 큰 수에서 작은 수를 빼준다.
8은 작은 수이기 때문에 막대의 길이가 변하지 않는다. 12는 8만큼 빠지기 때문에, 길이가 4인 막대 하나만 남는다.
gcd(8,12) = gcd(8,4) 이기 때문에, 8과 12의 최대공약수를 구하기 위해서 8과 4의 최대 공약수를 구해도 된다.

3. 8과 4 중 8이 더 크기 때문에, 8에서 4를 빼고, 4만 남는다.
작은 수 4는 변하지 않기 때문에, 두 막대의 길이가 같아졌다.

4. 두 막대의 길이가 같아진다면 둘 중 아무거나를 선택하여 하나를 빼준다. 윗 막대의 길이는 4로 유지하고, 아래 막대를 4만큼 빼주어 0으로 만든다. 남아있는 4와 0 두 막대기 중 0이 아닌 쪽, 즉 4가 gcd다. 그리고 이 방식은 항상 옳다.

이 방식을 코드로 작성하면 아래와 같다.

#gcd_sub 방식
def gcd(a,b) #a와 b의 최대공약수를 구하라
	while a*b!=0:  #a와 b가 0이 아닐때까지 반복한다. 둘 중 하나라도 0이라면 빠져나온다.
    		#a와 b 둘 중 어느 숫자가 더 큰 숫자인지 모르기 때문에,
    		if a>b: a=a-b  
  		#a가 b보다 크다면, a-b 연산
        	else: b=b-a
  		#b가 a보다 크다면, b-a 연산을 한다.
   	 return a+b 
     """
     a,b 둘 중 하나가 0이므로, 값은 a이거나 b이기 때문에,
     굳이 if a>b return a
     else b>a return b 작성해줄 필요 없다.
     """

 #gcd_sub 예시
 gcd(2,100) = gcd(2,98) = gcd(2,96) = ... = gcd(2,2) = gcd(2,0)
 #값 2가 리턴 될 때까지 = 큰 수(100)가 작은 수(2)보다 작아질 때까지 연산(while문)을 50번 반복한다.

방식 2. 나머지 (modulo)

큰 수에서 작은 수를 빼는 과정을 큰 수가 작은 수보다 작아질 때까지 반복하고 큰 수와 작은 수의 역할이 바뀌어 이 과정을 반복해서 작은 수가 0이 될 때까지 진행된다. 여기서 큰 수가 작은 수보다 작을 때까지 작은 수만큼을 줄이게 된다는 것은 결국 큰 수를 작은 수로 나눈 나머지를 구하는 과정과 같다. 결국 반복해서 뺄 것이 아니라 단순히 큰수 % 작은수를 하면 된다는 것을 알 수 있다.

#gcd_mod 방식
def gcd(a, b):
    while a != 0 and b != 0:
        if a > b: a = a % b
        else: b = b % a
    return a + b
  """
  a%b는 a에서 b를 나누고 난 나머지 값을 구하는 연산
  a/b는 a 나누기 b 연산
  """

 #gcd_mod 예시
 gcd(2,100) = gcd(2,0)
 #b%a는 0, 한번만 반복. 빼기 연산보다 나머지를 구하는 연산이 훨씬 빠르고 효율적이다.

방식 3. 재귀 (reculsive)

하나의 함수에서 자신(함수)을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.

#gcd_rec 방식(재귀함수)
gcd(a,b) = gcd (a,a%b) or gcd(b,b%a)