6.006 Lecture1 - 알고리즘이란

안녕하세요 집DS입니다. 저는 알고리즘 공부를 하다말다 그러곤 했습니다. 지금까진 특별한 목적이 없었기 때문에 그랬던 것 같습니다. 최근엔 다시 목표가 생겨 차근차근 해나가고 있습니다. 그 중 6006이라는 MIT 수업이 가장 마음에 들어서 다시 내용을 보고 공부하고 있습니다. 공부중에 가장 큰 공부는 누군가를 가르치는 것이라고 합니다. 그럼 누군가를 가르친다는 마음으로 내용을 정리해보도록 하겠습니다.

 

알고리즘이란?

알고리즘을 글자 그대로 말하면 매우 쉽습니다. 수업 내용대로 한다면 다음과 같습니다

알고리즘 : 주어진 문제를 1)정확 2)효율적으로 해결하는 절차, 방법, 규칙들의 집합

쉽습니다. 말은. 그럼 문제란 무엇일까요? 우리는 흔히 문제를 해결한다는 말을 씁니다. 그리고 실생활의 문제를 해결하는 방법은 여러가지 입니다. 다시말해 하나의 문제에 대한 해결책이 여러가지 일 수 있습니다. 하지만 알고리즘은 그렇지 않습니다. 알고리즘은 주어진 입력값에 대해 오직 하나의 값만을 내보내야 합니다. 이를 영어로는 deterministic이라 하며 한국말로는 결정론적이라고 합니다.

그럼 여기서 저는 문제라는 말보다는 Computation Problem이라는 말로 이야기를 이어가도록 하겠습니다. Computation Problem은 무엇일까요?

 

Computation Problem이란?

앞서 말했듯, 우리가 실생활에 접하는 문제는 다양한 해결책을 가지고 있을 수 있습니다. 하지만 위에서 언급했듯 알고리즘은 하나의 인풋에 대해 하나의 아웃풋을 내보내야 합니다. 다시말하면 문제도 하나의 인풋에 대해 하나의 결과값을 가져야 합니다. 이런 관계를 영어로는 다음과 같이 표현해 놓았습니다.

A problem is a binary relation connecting problem inputs to correct outputs

 

이말을 해석하면 다음과 같습니다.

문제란 입력값과 결과값 사이의 이항관계다

이항 관계. 너무 오랜만에 들어서 까먹고 있던 이야기였습니다. 하지만 저는 그림쟁이 오늘도 그림으로 설명해봅니다.

이항 관계 예시(위는 어떤 문제일까요?)

이항관계라는게 이런 것이었습니다. 입력값의 집합과 출력값의 집합을 연결시켜 놓은 것입니다. 이러한 관계가 주어져 있을때 알고리즘은 해당 문제에 대해 임의의 큰수에 대해 문제를 해결할 수 있어야 합니다. 위 경우 Computation Problem의 케이스를 일일이 쓸 수 있었습니다. 그러나 보통 입력값과 출력값의 가짓수가 너무 많기 때문에 보통은 이들이 충족해야하는 관계를 설명해놓은 것이 Computation Problem이 됩니다.

그리고 정확하게 푼다는 것은 모든 입력값과 출력값의 관계를 만족시킨다는 뜻이 됩니다. 그럼 다시 알고리즘이란 무엇일까요? 위 그림을 통해 다시 이해를 해봅시다.

알고리즘 : 입력값과 출력값 사이의 매핑

아주 옛날 옛적으로 돌아가보면 우리는 이런 것을 배웠습니다

$$y=f(x)$$

어떤 주어진 값이 있다면 이를 수학적 함수를 이용해 다른 값으로 만드는 것입니다. 이를 매핑이라고 표현할 수 있습니다. 그럼 위 그림을 매핑하는 수학적 함수는 무엇일까요?

쉽습니다 제곱입니다.

네 이미 보자마자 아셨겠지만, 각 값을 제곱하면 출력값이 나오게 됩니다. 주어진 입력값과 출력값의 관계를 만족하는 함수. 이것은 수학적인 함수라고 볼 수 있을 것입니다. 저는 저 나름의 언어로 알고리즘이라는 말을 써보면 다음과 같습니다.

주어진 입력값과 출력값의 관계를 만족하는 함수를 컴퓨터에 적합한 언어로 쓴 것

알고리즘은 저는 이렇게 정의할 수 있다고 생각합니다. 결국 문제란 입력값과 출력값의 관계입니다. 이를 함수로 쓴다는 표현은 수학적 함수와 큰 차별점을 가지지 못할 것입니다. 그렇기 때문에 컴퓨터에 적합한 언어로 쓴 것 이라고 했습니다. 컴퓨터에 적합한 언어란 Pseudo code(의사코드) 또는 python과 같은 각 프로그래밍 언어를 지칭합니다.

그럼 컴퓨터에 적합한 언어로 써 봅시다.

def f(x):
	return x**2

python에서는 제곱을 **를 써서 표현합니다. 따라서 위 문제에 대한 함수는 위와 같습니다.

 

끝맺으며

오늘은 알고리즘이 무엇인지 간략히 정리했습니다. 다시 설명하면 주어진 입력값과 출력값의 관계를 만족하는 함수를 컴퓨터에 적합한 언어로 쓴 것 이라 할 수 있습니다. 실제 문제를 풀때 이런 정의가 크게 중요하지 않을 수도 있으나 차근차근 하나씩 쌓아간다는 생각으로 정리해 보았습니다. 보시는 분께 도움이 됬길 바랍니다.

 

열심히 하는 것보다 중요한 것은 잘하는 것이다
그러나 잘하기 위해서는 열심히 해야 한다
집 DS

 

참고자료

---

[1]

“6.006 Introduction to Algorithms, Recitation 1 | Introduction to Algorithms | Electrical Engineering and Computer Science,” MIT OpenCourseWare. Accessed: Jan. 16, 2024. [Online]. Available: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_r01/