자료구조와 알고리즘

자료 (Data Structure), 알고리즘(Algorithm)

자료구조

• 자료는 즉 data를 말하며 해당 데이터를 담는 저장공간(memory)이 필요
  => 데이터 값의 모임

• 저장된 데이터를 효과적으로 "읽기, 쓰기, 삽입,삭제, 탐색"와 같은 연산을 제공하여 수행할 수 있어야 한다.

알고리즘

• 입력된 데이터를 가지고 문제를 해결하는 논리적인 절차 / 방식

최대 공약수 알고리즘 GCD

gcd(8, 12) => max {1,2,4} => 즉, 4!

1. 빼기 방식

• 두 수를 비교해서 큰 수, 작은 수를 나타내고,
• 큰 수에서 작은 수를 빼고 값을 대입,
• 이 행동을 반복해서 한 수가 0이 되는 경우 그 때 큰수가 최대 공약수인 것.

gcd(a, b) {
	while(a !== 0 && b !== 0) {
    	if(a > b) a -= b;
       	else b -=a;
    }
    
    return a + b; // 둘 중에 하나가 0일테니
}

하지만 큰 수가 100, 작은 수가 2와 같이 큰 차이가 나는 두 수라고 하면 반복되는 횟수가 많아진다.

2. 나누기 방식

• 두 수를 비교해서 큰 수, 작은 수를 나타내고,
• 큰 수에서 작은 수를 나누고 나머지 값을 대입
• 이 행동을 반복해서 한 수가 0이 되는 경우, 그때 큰 수가 최대 공약수

gcd(a, b) {
	while(a !== 0 && b !== 0) {
    	if(a > b) a %= b;
        else b %= a;
    }
    
    return a + b;
}

1번 방식으로는 gcd(2,100) -> gcd(2,98) -> gcd(2, 96)... gcd(2,0) 으로 2가 나오지만,

2번 방식으로는 gcd(2,100) -> gcd(2, 0) 한 번 만으로 결과 출력 가능

즉 더 빠른 결과 값을 나타낼 수 있음

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하며 작성되어 있습니다. 🙏🏻