제1장 개요

1. 제1장 개요
   1. 1.1 알고리즘이란 무엇인가?
   2. 1.2 알고리즘의 분석
   3. 1.3 유클리드 알고리즘
   4. 1.4 소수를 구하는 알고리즘
   5. 문서에 대하여

1.1 알고리즘이란 무엇인가?

1.1.1 알고리즘의 정의

• 알고리즘의 정의
  • 알고리즘이란 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합이다.
  • 알고리즘에는 우선 주어지는 문제가 있고, 이 문제를 해결하기 위한 순서적인 동작들이 있다.
  • 가장 먼저 선행 되어야 할 것은 주어진 문제를 잘 이해하는 것이다. 그 문제 뿐만 아니라, 문제가 주어지는 상황도 포함.

• 알고리즘의 요건
  • 0개 이상의 외부 입력, 하나 이상의 출력
  • 각 단계가 단순하고 모호하지 않아야 한다.
  • 한정된 수의 작업 후에는 반드시 종료해야 한다.
  • 모든 명령이 수행 가능해야 한다.
  • 효율적이어야 한다.(실용성이 있어야 함)

• 알고리즘 기술 언어
  • 알고리즘 기술방법 : 일상언어, 순서도(흐름도), 의사코드

1.1.2 자료구조

• 알고리즘의 객체
• 구조화되고 조직화된 자료의 저장/추출/관리 방법
• 추상 데이터타입(Abstracted Data Type)
• 배열, 스택, 스택, 큐, 트리 등등..

1.1.3 알고리즘의 선택

• 절대적인 최상의 알고리즘은 없다.
  • 항상 주어진 문제의 상황과 제한점이 주어질 때에만 최상의 알고리즘을 선택할 수 있다.
    즉 주어진 문제와 환경을 먼저 숙지하라
• 속도와 메모리 소요의 상관관계

• 가장 단순한 알고리즘을 사용하는 것이 좋다.
• 사용 빈도가 낮은 서브 프로그램에서는 효율성이 떨어지더라도 간단한 알고리즘이 좋다.
  • 지나친 속도결벽증은 금물
  • 알고리즘의 사용빈도에 따른 선택

1.1.4 알고리즘의 예 - 두 정수의 곱셈

• 전통적인 방법
  • 임의의 정수 * 한자리 정수
  • 두 정수 더하기
  • 사람에게는 적합하지만 컴퓨터는 어렵다.

 45*37 = 45 *(7+30) = (45*7)+(45*30) = 315+1350 = 1665
 

• a la russe 알고리즘 (프랑스어로, 알-라-루에스? 러시아어 아-라-뤼스?)
  ① 두개의 정수를 첫번째 위치, 두번째 위치에 써둔다. 만일 첫번째 수가 홀수이면 두번째 수를 세번째 위치에 또 쓴다.
  ② 첫 번째 수를 2로 나누고(나머지는 버린다.) 두 번째 수에 2를 곱한다.
  만 약 첫번째 수가 홀수이면 두 번째 수를 세번째 위치에 쓰고 짝수이면 세번째 위치를 비워둔다.
  ③ 위의 1과 2의 과정을 첫번째 위치의 수가 1이 될 때까지 반복한다.
  ④ 세번째 위치에 있는 수들을 모두 더한다. 이 더한 결과가 바로 두 정수의 곱의 결과이다.

• 45* 37 을 a la russe 알고리즘으로 구현해 보자

→ 세번째 수를 모두 더하면 : 37+148+296+1184 = 1665

• a la russe 알고리즘의 기본 동작은 아래와 같다.
  • 정수를 2로 나눈다 : C언어의 >> 연산자로 구현
  • 정수를 2로 곱한다 : C언어의 << 연산자로 구현
  • 두 정수를 더한다.

1.2 알고리즘의 분석

1.2.1 경험적 분석과 수학적 분석

• 경험적 분석(Empirical Analysis)
  • 알고리즘을 프로그래밍 언어로 구현을 한 뒤에 이를 실행시켜 보아 실행 시간을 비교하는 것.

• 수학적 분석(Mathematical Analysis)
  • 알고리즘 자체만을 가지고 수학적 분석을 하는 것.

1.2.2 최악의 경우와 최선의 경우

• 최악의 경우(Worst Case)
  • 알고리즘을 수행하는데 가장 많은 시간과 공간을 필요로 하는 경우

• 최선의 경우(Best Case)
  • 가장 작은 시간과 공간을 필요로 하는 경우

• 평균적 경우(Average Case)
  • 평균적인 시간과 공간을 필요로 하는 경우

1.2.4 알고리즘의 유형

• O표기법
  • 알고리즘에서 시간복잡도를 표시하는 방법이 여러가지가 있는데 일반적으로 사용되는 방법이 O표기법이다.
  • 이 O표기법은 최악의 경우에 대한 성능을 나타낸다.
  • O(1) : O(1) 은 모든 연산을 한번만 한다는 뜻이 아니라, 입력 데이터의 크기나 종류에 무관하게 항상 같은 성능을 보여준다는 뜻이다.
  • O(logN) : 로그형, 입력 자료를 나누어 그 중 하나만 처리, ex)이진 탐색
  • O(N) : 선형, 입력 자료를 차례로 하나씩 모두 처리
  • O(NlogN) : 분할과 합병형, 자료를 분할하여 각각 처리하고 합병, ex)퀵 정렬
  • O(N2) : 제곱형, 주요처리(기본연산) loop 구조가 2중인 경우
  • O(N3) : 세제곱형, 주요처리(기본연산) loop 구조가 3중 경우
  • O(2n) : 지수형, 가능한 해결방법 모두를 다 검사하며 처리함

1.3 유클리드 알고리즘

1.3.1 최대공약수(Greatest Common Divisor) 란?

• 주어진 두 정수의 약수 중에서 가장 큰 공통되는 약수를 말한다.
• 예를 들어 280과 30의 최대 공약수를 구해보자
  • 280의 약수 : 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280
  • 30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30
  • 최대 공약수는 10, Page 40 아래 계산법 참고

1.3.2 유클리드 알고리즘

• 1) 임의의 두 정수 u와 v를 입력 받는다.
• 2) v가 u보다 크다면 v와 u의 값을 교환한다.
• 3) u에다 u-v 값을 저장 한다.
• 4) u가 0인가? 0이 아니면 ②로 돌아간다. 0이면 v가 최대 공약수 이다.

1.3.3 JAVA로 풀어본 유클리드 알고리즘

public class EuclidsAlgorithm {
	
	@Test
	public void testGcd(){
		final int u = 250;
		final int v = 30;
		
		System.out.println("최대공약수 : "+getGcd(u, v));		
	}
	
	private int getGcd(int u, int v){
		
		//와 v를 교환하기 위한 임시 변수
		int t;	
		int i=1;
		while(u!=0){
			
			if(u<v){
				t=u;
				u=v;
				v=t;
			}
			u=u-v;
			System.out.println(i++);
		}		
		return v;
	}
}


 

• 위 코드의 문제점은 u와 v의 차이가 클 때 실생 시간이 오래 걸린다.
  • 250과 30의 경우 while문을 11번이나 수행했다.
  • 32767과 1의 경우는 무려 32767번 수행해야 한다.

1.3.4 유클리드 알고리즘의 개선

• 250과 30을 뺄셈하여 만든 결과 10과 30을 자세히 살펴보면 10은 250을 30으로 나눈 뒤의 나머지임을 알 수 있다.
  즉 10 == 250 % 30 이다. 그래서 아래와 같은 식이 성립한다.

• 1) 임의의 두 정수 u와 v를 입력 받는다.
• 2) v가 0인가? 0이면 u가 최대공약수이다.
  • 2.1) 0이 아니면 u에 u%v를 대입한다.
  • 2.2) u와 v의 값을 교환한다.

public class NewEuclidsAlgorithm {
	
	@Test
	public void testGcd(){
		final int u = 250;
		final int v = 30;
		
		System.out.println("최대공약수 : "+getGcd(u, v));
	}
	
	private int getGcd(int u, int v){
		
		//와 v를 교환하기 위한 임시 변수
		int t;	
		int i=1;
		while(v!=0){
			u=u%v;
			t=u;
			u=v;
			v=t;
		}
		System.out.println(i++);
		return u;
	}

}
 

• while문을 한 번 밖에 수행을 안 했다.

1.4 소수를 구하는 알고리즘

1.4.1 정의에 의한 알고리즘

• 소수의 정의는 다음과 같다.
  • 1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수

• 어떤 수 N이 주어졌을 때 N을 2부터 N-1까지 나누어 떨어지는 수가 있으면 소수가 아니고,
  나누어 떨어지는 수가 없으면 N은 소수가 된다.

• 1) 정수 N을 입력 받는다.
• 2) 정수 i에 2를 대입한다.
  • 2.1) N이 i로 나누어 떨어지는가?
    • 2.1.1) 나누어 떨어지면 소수가 아니다. 끝.
  • 2.2) i를 하나 증가 시킨다.
  • 2.3) i가 N보다 작은가?
    • 2.3.1) 작으면 2.1 로 돌아간다.

• 3) 정수 N은 소수이다. 끝.

public class PrimeAlgorithm {	
	@Test
	public void testPrime(){
		final int n = 7777777;
		System.out.println(n+"의 소수 여부 : "+isPrime(n));		
	}
	
	private boolean isPrime(int n){
		
		for(int i=2 ; i<n  ; i++){
			if(n%i == 0)
				return false;
		}		
		return true;
	}
}

1.4.2 개선된 알고리즘

• 2부터 N 까지의 제곱근 까지의 정수로만 나누어도 된다.
• 즉 2부터 sqrt(N)까지의 숫자로만 나눈다.

public class NewPrimeAlgorithm {
	
	@Test
	public void testPrime(){
		final int n = 100;
		System.out.println(n+"의 소수 여부 : "+isPrime(n));		
	}
	
	private boolean isPrime(int n){
		int sqrt = (int)Math.sqrt((double)n);
		for(int i=2 ; i<sqrt  ; i++){
			if(n%i == 0)
				return false;
		}		
		return true;
	}
}

1.4.3 에라토스테네스의 체

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 김정식
• 최초작성일 : 2009년 1월 15일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^