알고리즘(Algorithm)에 대해 알아보자

 

알고리즘이란?

(문제) ----------(해결) > "문제 해결 방법의 절차"

특정한 요리를 완성하기 위한 레시피와 같은 개념으로 생각하도록 하자

 

알고리즘 조건

• 입력 (Input) : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 것
• 출력 (Output) : 수행 후, 하나 이상의 결과를 출력할 것
• 명확성 (Definiteness) : 알고리즘 수행 작업 과정을 나타내는 명령어들은 명확한 형태를 띄고 있을 것
• 유한성 (Finiteness) : 알고리즘은 수행 후, 반드시 종료될 것
• 효과성 (Effectiveness) : 실무에서 실행 가능한 알고리즘 명령어일 것

 

알고리즘의 표현 방법

 

(1) 순서도(flow chart)의 도식화 but 하나하나 풀어 나타내는만큼, 복잡한 알고리즘의 경우 상당히 복잡해진다.

 

 

(2) 자연어로 서술해 표현

여기서 자연어는 인간 언어를 말한다 (ex. 한국어, 영어…)

but 개인에 따라 생기는 해석의 차이로 명확한 의미 전달에 오류가 생길 가능성이 높다

 

(3) 가상코드(Pseudo-code)를 이용한 추상화

형태는 프로그래밍 언어와 유사하나, 알고리즘 핵심 로직을 직관적으로 구현하기 위하여 표현되는 방법이다

 

가상 코드? 알고리즘 기술 언어(ADL)+자연어 → "유사코드", "의사코드"

형태는 프로그래밍 언어와 유사하나, 알고리즘 핵심 로직을 직관적으로 구현하기 위하여 표현되는 방법이다

[케이크 레시피 알고리즘]


반죽1 = egg + mill ;
반죽2 = egg + ssal ;

사용자_선택 = scanf(원하는 반죽 입력)

switch (사용자_선택) {
	case '1': cooking(3);
	break;
	case '2': cooking(4);
	break
}


함수 cooking (num<-횟수) {
	for(int i=0; i<num; i++){
		count+=i;
	} //for문은 정해진 횟수만틈 쿠키를 돌리는 오븐 역할 
		
	if(count==3){
		printf("밀쿠키 완성입니다");
	} 
	else if(count==4){
		printf("쌀쿠키 완성입니다");
	}
	else
		printf("쿠키를 완성하지 못했습니다");
}

실행이 아닌 이해 틀을 만드는 것이 주목적이기 때문에 보기 쉽고 이해하기 쉽게 작성하는 것이 좋다

 

(4) 프로그래밍을 이용한 구체화

알고리즘의 가장 정확한 기술이 가능.

but 실제 구현, 실행을 진행하기 때문에 알고리즘의 핵심적인 내용을 제외한 부수적 요인 또한 함께 충족시켜줘야 한다.

 

---

 

알고리즘 성능 분석

• 수행 시간 측정
  • 2개의 알고리즘의 실제 수행 시간을 측정
  • 실제로 구현 필요
  • 동일한 하드웨어 사용
  • 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터 상에서 실행시킨 다음, 수행 시간 측정
• *알고리즘 복잡도 분석
  • 직접 구현하지 x → 수행 시간 분석
  • 알고리즘이 수행하는 연산 횟수 측정
  • 연산의 횟수는 n의 함수
  • 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지 숫자로 표시

알고리즘의 복잡도를 계산하는 방법은 2가지로 나뉜다

• 시간 복잡도(time complexity) 
  알고리즘을 이루고 있는 연산들의 수행 횟수를 숫자로 표시한다 자료의 개수가 많은 경우 차수가 가장 큰 항이 영향을 크게 미치기에 다른 항들은 상대적으로 무시될 가능성이 높다*
• 공간 복잡도(space complexity)]

  알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 나타낸다.

  그러나 실상 컴퓨팅 환경의 메모리 용량이 증가하여,

  특정한 경우가 아니면 알고리즘 설계는

  메모리 공간 부족 우려에 대한 고려사항은 크게 존재하지 않는다.

  특정한 경우 → 제한된 환경, 대규모 데이터 등…
  

 

복잡도를 표현하는 방에는 크게 3가지가 존재하는데, 간단히 짚고 넘어가보자

빅오(Big O) 표기법

연산 횟수를 대략적으로 표기한 것으로 함수의 상한을 표시한다

입력 크기에 따라 알고리즘 실행 시간이 어떻게 증가하는지나타내는 방법.

f(n) → O(g(n))
n : 입력 크기 g(n) : f(n)의 상한값
⇒ 입력크기 n이 증가함에 따라, g(n)에 대한 f(n)의 증가율을 나타낸다

 

빅오메가(Big Ω) 표기법

시간과 공간의 하한을 나타내는데 사용되는 방법으로,

알고리즘이 최소한 이만큼의 자원을 사용함을 말한다.
→ 최소한 그 복잡도만큼 자원을 사용한다는 것

f(n)=n^2+3n ⇒ Ω(n^2)

 

빅세타(Big θ) 표기법

 

함수의 하한인 동시에 상한을 표시한다.

f(n) = O(g(n)) && f(n) = Ω(g(n)) ⇒ “ f(n) = θ(n) “

---

 

알고리즘은 문제 과정의 절차를 나타내는 것을 말하다보니,

문제 해결 과정을 실행하는 다양한 경우의 가능성을 품고있다

 

• 최선의 경우 (best case) : 가장 빠른 수행 시간의 경우
• 평균의 경우 (average case) : 평균적인 수행 시간의 경우
• 최악의 경우 (worst case) : 가장 늦은 수행 시간의 경우

> 보통 최악의 경우를 기준으로 고려한다. 

 

 

이런 알고리즘 수행 시간의 경우는 입력되는 자료 집합에 따라 차이가 존재한다.

자료집합과 알고리즘은 깊은 상관관계로 얽혀있는데

다음에는 자료구조에 대해 알아보는 시간을 가져보자 😊