자료구조 - 자료구조와 알고리즘(2022.09.13)

1. 자료구조

---

1)  자료구조란? 

data가 있을 때, 이를 저장할 저장공간과 읽기, 쓰기, 삽입, 삭제, 탐색 등 data를 다룰 수 있는 연산이 필요하다.

이 저장공간과 연산을 통틀어 우리는 자료구조라고 부른다.

 

2) 자료구조의 예

 

▶변수(variable) 

 

a = 1

print(a) 

 

위 코드에서 첫째줄에는 a에 5가 들어있는 객체의 주소를 입력하는 쓰기 연산이 사용되었으며, print(a)에는 a에 쓰인 data를 읽는 읽기 연산이 사용되었다. 이처럼 변수도 자료구조의 간단한 예 중 하나이다.

 

▶배열(array) / 리스트(list)

 

A[9,1,-7,2] 

 

위와 같은 배열에서 각 배열의 자리에 각 숫자가 들어있는 주소가 입력되는 쓰기 연산이 사용되었고 이를 출력한다면 읽기 연산이 사용되게 된다.

뿐만 아니라 삽입, 삭제 연산도 아래와 같이 사용될 수 있다.

 

 A. append(-1)

 A. pop()

 

첫째줄을 통해 배열 A의 가장 끝에 -1이 추가되며 두번째 줄을 통해 가장 뒤에 있는 값이 삭제되는 연산이 작동한다.

 

 

2. 알고리즘(Algorithm)

---

1) 알고리즘이란?

입력된 데이터를 가지고 유한한 횟수의 연산을 통해 정답을 찾아 출력하는 것을 알고리즘이라고 한다.

 

 

2) 알고리즘 이름의 유래

알고리즘은 9세기 Algebra에 능했던 수학자인 Al-Khwarizmi(알콰리즈미)의 이름이 라틴화되면서 Algorismus와 Arithmos가 합쳐지면서 만들어진 표현이라고 알려져 있다.

 

3) 최대공약수 찾기

 

8과 12의 최대공약수를 찾아보자. 수학을 전공한 나로서는 4라는 답이 보자마자 툭 하고 튀어나오지만, 숫자가 커질 수록 바로 찾는 것은 쉽지 않다.  수가 매우 커졌을 때 최대공약수를 찾는 방법으로는 학부 때 정수론의 유클리드 호제법을 배웠다. 이를 알고리즘을 통해 컴퓨터로 구현하는 방법에 대해 생각해보자.

 

우선 유클리드 호제법이란 큰 수에서 작은 수를 빼면 ( 혹은 나누면 //나누는 것은 빼는 것의 반복이라 볼 수 있다) 큰수-작은수의 값과 작은수의 최대공약수는 (혹은 나눈 수와 나머지의 최대공약수는 ) 처음 두 수의 최대공약수와 같다는 것을 이용한 방법이다.

 

이를 코드화 하면 아래처럼 표현할 수 있다.

 

gcd(a,b) ;

while a!=0 and b!=0 ;

if a>b ; a = a-b

else ; b = b-a

return a+b

 

위 코드를 해석해보자면, 우선 a와 b가 둘 중 하나라도 0이 되면 해당 연산이 끝나므로 while 구문이 작동하는 조건으로 반드시 두 수 모두 0이 아니라는 조건은 필수적이다. 이 코드가 반복되다가 두 수 중 하나라도 0이 되면 그 때 0이 아닌 수가 최대공약수가 되므로 a+b 가 최대공약수가 된다. ( 이 때 a와 b 중 어떤 수가 최대공약수로 산출될 지 알 수 없으며, 두 수 중 하나는 0이므로 최대공약수의 값에 어떤 영향도 끼치지 못하고 0이 아닌 수(최대공약수)가 나오게 되므로 문제는 없다.)

 

하지만 위 방법이 가장 효율적인 것은 아니다.

예를 들어 gcd(2,100)을 구하기 위해 a=2, b=100 을 입력한다고 하자. 

그럴 경우에 while 반복 구문이 1회 작동하면 a=2, b=98 / 2회 작동하면 a=2, b=96이 되고 이 과정을 50회 반복해야 겨우 b가 a보다 작아져 0이 되어 a+b=2라는 결과를 얻게 된다.

이러한 예처럼 큰 수와 작은 수의 차이가 커서 큰 수에서 작은 수를 뺀 값이 작은 수보다 클 때 비효율적인 상황이 발생한다. ( 여기서 크다는 표현은 다소 기준이 모호한 것처럼 보일 수 있으나, ｜a-b｜>min{a,b}인 경우에 차이가 크다고 보겠다.) 

 

따라서 최대공약수를 구하는 좀 더 효율적인 방법을 고안해보자.

 

gcd(a,b) ;

while a!=0 and b!=0 ;

if a>b ; a = a%b

else ; b = b%a

return a+b

 

첫번째 코드와 두번째 코드의 차이점은 빼기를 사용했냐, 나눗셈의 나머지를 사용했냐의 차이이다. 나눗셈을 하게 되면 첫번째 코드의 비효율적인 상황에서의 반복을 줄일 수 있다.

유클리드 호제법에 대해 처음 소개하는 부분에서 언급했듯이 큰 수에서 작은 수를 반복적으로 빼는 방식과 큰 수를 작은 수로 나누는 방식은 0과 양의 정수에 한해서 같은 맥락이다. ( 뺄셈을 할 때는 음수가 될 때까지 반복해서 빼지 않고,  나눗셈을 할 때는 1보다 작아지는 유리수가 되는 상황은 고려하지 않는다. )

따라서 뺄셈을 사용하는 것과 나눗셈의 나머지를 사용하는 것은 같은 맥락을 가지고 같은 결과값을 주지만, 그 사이의 효율은 후자가 훨씬 좋다.

 

 

 

---

 

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

 

자료구조 과목 소개 - YouTube