자료구조와 알고리즘

자료구조와 알고리즘

• 자료구조는 자료를 담는 그릇(구조)이고, 알고리즘은 그릇에 담긴 자료(입력데이터)를 여러 단계의 연산(명령)을 통해 원하는 값을 계산하는 논리적인 절차이다.
• 가장 간단한 자료구조는 C/C++등의 프로그래밍 언어의 기본 요소인 변수(variable)이고, 가장 널리 쓰이는 자료구조로는 배열(array), 구조체(struct)등이 있다.
• 알고리즘의 어원은 9세기 페르시아(이란-이라크) 수학자 AI_Khwarizmi의 라틴어 이름인 algorismus와 수를 나타내는 그리스어 arithmos가 섞여 만들어졌다는 게 정설이다.
• 결국, 문제를 (수학적,논리적으로) 해결한다는 것은 자료구조에 자장된 값(입력)을 기본적인 연산을 통해 가공하여 원하는 값(출력)을 계산한다는 의미이다.

💻인류 최초의 알고리즘

• 그리스 수학자로 기하학의 아버지로 알려진 Euclid의 유명한 저서인 "Elements"(BC,300)에 설명된 최대공약수(Greatest Common Divisor: GCD)를 계산하는 알고리즘이 최초라고 알려져 있다.
• pseudo code

algorithm gcd(a,b)
	while a*b != 0 do
		if a > b
			a = a % b // %는 나머지 연산자
		else
			b = b % a
	return a + b

• 큰 수에서 작은 수를 빼는 과정을 두 수 중 하나가 0이 될 때까지 반복하면, 0이 아닌 수가 최대공약수이다.

algorithm gcd(a,b)
	while a*b != 0 do
		if a > b
			a = a % b // %는 나머지 연산자
		else
			b = b % a
	return a + b

• 만약 a > b라면, gcd(a,b)는 gcd(a-b,b)이고 동시에 gcd(b, a%b)가 된다. 이 점을 이용하면 gcd함수를 재귀함수로도 작성할 수 있다. 예 : gcd(16,6) → gcd(6,4) → gcd(4,2) → gcd (2,0)

def gcd_sub(a, b):
	while a * b != 0:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a + b
	
def gcd_mod(a, b):
	while a * b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
	
def gcd_rec(a, b):
	if a == 0 or b == 0:
		return a + b
	elif a > b:
		return gcd_rec(a%b,b)
	else:
		return gcd_rec(a,b%a)
# a, b를 입력받는다
# gcd_sub, gcd_mod, gcd_rec을 각각 호출하여, x, y, z에 리턴값을 저장한다
a, b = input().split()
a = int(a)
b = int(b)
x = gcd_sub(a,b)
y = gcd_mod(a,b)
z = gcd_rec(a,b)
print(x, y, z)