알고리즘(Algorithm)

Algorithm

한글로 번역하기 힘든 용어 중 하나가 '알고리즘'이다.

단순하게 풀이법, 해법, 계산방법 정도로 번역해도 되겠지만 이걸로는 컴퓨터 사이언스에서 쓰이는 의미를 다 담아내지는 못한다. 예를 들어 '알고리즘 매매'라고 하면 이 번역이 어색해진다. 프로그램하는 사람들에게 알고리즘은 그냥 알고리즘이다. Process, Tree, Algorithm 등 컴퓨터공학엔 우리말로 바꾸기 힘든 용어가 몇 가지 있다. 

그 중에서 알고리즘은 더욱 독특한데 사실 이건 영어도 아니다. 원래 페르시아 수학자의 이름, 압둘라 무함마드 이븐 무사 알콰리즈미에서 따온 용어다. 

 

 

알콰리즈미는 페르시아 최초의 수학책을 만들고, 인도에서 도입된 아라비아 숫자를 이용하여 최초로 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈)을 만들고 0과 위치값을 사용한 수학자다. 생존 연대는 남긴 책들을 볼때 780~850년경으로 추정된다.

 

그는 ‘대수학의 아버지’로 불리기도 한다. 알고리즘 뿐 아니라 대수학을 뜻하는 영단어 알제브라 (Algebra)도 그의 저서 'al-jabr wa al-muqabala' 로부터 유래했다. 알 콰리즈미는 엄청난 양의 책을 저술했는데, 그 주제로는 천문학, 수학, 지리학 등이 있다.

 

주 업적으로 이차 다항식에서 양수 해를 구하는 방법을 연구하고 체계화하였다. 825년 '인도 숫자를 사용한 계산', 830년 '복원과 대비의 계산'이 대표 저서다. 특히 기하, 천문, 측량 등에서 실용적인 연구를 많이 하고 중세 수학사에 큰 영향을 끼쳤다.

 

인도식 십진법 표기

현재 세계 공용으로 쓰는 아리비아 숫자는 원래 인도식 (힌두) 십진법에서 시작된 것이다. 기수법 자체는 인도식이고 표기모양은 아라비아 숫자 모양을 사용한다. 이 인도-아라비아 수체계를 발전시키고 서구 유럽까지 영향을 준 것이 알 콰리즈미의 저서들이다.

 

알고리즘의 정의와 특성

알고리즘(Algorithm)

• 페르시아의 수학자인 무함마드 이븐 무사 알콰리즈미(대수학의 아버지로 불림)에서 유래함.
• 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 기술
• 컴퓨터 공학에서 알고리즘은 명확한 입출력을 가져야 함

 

가장 오래된 알고리즘은 2개의 자연수 사이의 최대 공약수를 구하는 유클리드 호제법

• 2개의 자연수 a,b에 대하여 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대공약수와 같음(a>b)
• 큰 수(a)를 작은 수(b)로 나눈 나머지(r)를 구하는 계산을 재귀적으로 반복(나머지가 0이 될 때까지)
• 나머지가 0이 되는 마지막 b(연산에서 나누는 수)가 최대공약수가 됨
• 유사코드

Euclid(m,n)
if n=0
	return m
return Euclid(n, m mod n)

 

알고리즘의 요건

• 입출력 : 입력과 출력을 가지고 있어야 함
• 정확성 : 주어진 입력에 대해 항상 올바른 답을 주어야 함
• 유한성 : 유한 시간 내에 종료되어야 함
• 효율성 : 시간적, 공간적 효율성을 가져야 함
• 수행성(컴퓨터) : 컴퓨터로 수행이 가능해야 함

<알고리즘 분석>

알고리즘 분석의 목적

• 정확성 확인 : 모든 유효한 입력에 대해 유한 시간 내에 올바른 해를 찾아내는가를 판단하기 위함
• 효율성 확인 : 한정된 자원(기억 장소 사용량, 수행 시간)에서 효율적으로 작동하는지 확인하기 위함
• 알고리즘을 분석하여 체계적이고 효율적으로 생각하는 훈련을 할 수 있음
• 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 판단할 수 있음
• 문제를 단순화하여 생각할 수 있음
• 다른 사람의 아이디어에 대한 효율성을 판단할 수 있음

 

알고리즘의 분석 기준

• 정확성 : 모든 유효한 입력에 대해 유한 시간 내에 올바른 해를 찾아내는가
• 기억 장소 사용량 : 해를 찾아내는데 사용되는 기억 장소의 사용랑, 입력 개수에 따른 증가율이 중요
• 수행 시간 : 해를 찾아내는 데 걸리는 시간, 절대 시간보다는 입력 개수에 따른 증가율이 중요

 

<알고리즘의 분류 : 주요 알고리즘에 대해서만 정리>

분류 방식	알고리즘	특징
문제 해결 방법에 따른 분류	분할 정복 알고리즘	주어진 문제의 입력을 분할하여 문제를 해결 분할된 입력에 똑같은 알고리즘을 적용(주로 재귀 활용) ex) 병합 정렬, 퀵 정렬, 선택 정렬 등
	그리디 알고리즘	가능한 해들 중 가장 좋은 해를 찾음 근시안적인 최적해를 찾고, 이 해들을 모아 문제의 최적해를 찾음 ex) 동전 거스름돈 문제, 최소 신장 트리, 최단 경로 찾기, 부분 배낭 문제 등
	동적 계획 알고리즘	최적해 문제 해결 알고리즘 입력 크기가 작은 부분 문제를 해결하고 이를 이용해서 보다 큰 부분 문제들을 해결하여 최종적으로 주어진 입력 크기의 문제를 해결하는 방법 ex) 모든 쌍 최단경로, 연속 행렬 곱셈, 배낭 문제, 동전 거스름돈 문제 등
	근사 알고리즘	지수 시간이 걸리는 문제(NP 문제)에 대한 근사해를 찾는 알고리즘 ex) 여행자 문제, 정점 커버 문제, 통 채우기 문제, 클러스터링 문제 등
	백트래킹 기법	NP 완전 문제의 해를 탐색하기 위한 알고리즘 ex) 여행자 문제, 체스 퀸 배치 문제 등
	분기 한정 기법	큰 입력에 대해서 백트래킹 기법이 갖는 단점을 보완하기 위해 고안된 기법 ex) 여행자 문제 등
문제에 따른 분류	정렬 알고리즘	원소들을 번호순이나 사전 순사와 같이 일정한 순서대로 열거하는 알고리즘
	그래프 알고리즘	노드(정점)와 엣지(간선)으로 연결된 자료 구조인 그래프의 경로를 구하는 알고리즘
	기하 알고리즘	점, 선, 면 등의 기하 객체로 이루어진 문제를 해결하기 위한 알고리즘

 

<알고리즘의 수행 시간>

시간 복잡도

• 입력 크기에 비례하여 작업 시간이 어떠한 바율로 증가하는지 확인
• 절대시간(실측 시간)을 측정하는 경우 프로그래밍 언어, 컴퓨터 성능, 프로그래머의 실력 등의 변수에 따라 값이 달라질 수 있기 때문에 상대 시간을 활용
• 최선의 경우, 최악의 경우, 평균적 시간 분석으로 나눌 수 있으며, 최선의 경우는 현실적으로 좋은 분석 방법이 아님
• 상수 시간(1) : 입력 크기 n이 변해도 시간복잡도가 변하지 않음
• 수행 시간이 입력 n에 비례(n) : 입력 크기인 n이 변하면 수행 시간은 n의 개수에 비례하여 증가(팩토리얼 등)
• 수행 시간이 입력 n^2에 비례(n^2) : 입력 크기인 n이 변하면 수행 시간은 n^2에 비례하여 증가(이중 반복문 등)

 

가짜 동전 찾기 알고리즘 

• 많은 수의 동전 중에서 1개의 동전이 가짜(진짜 동전과 모양이 동일하며 무게가 약간 가벼움)인 경우, 양팔 저울만 사용 가능
• 방법 1 : 한쪽에 1개의 동전을 올려 놓고 나머지 동전을 하나씩 차례대로 올림(최선 : 1번 /최악 : n-1번)
• 방법 2 : 동전을 2개씩 선택하여 2개의 동전을 양팔 저울에 올려놓고 무게를 잰 후 가벼운 동전을 찾음(최선 : 1번, 최악 n/2번)
• 방법 3 : 동전을 똑같은 개수로 반으로 나누어 무게를 잰 후 가벼운 쪽을 다시 반으로 나누어 반복(일반적으로 log2n번 수행)
• 알고리즘 3의 경우 어떠한 경우에도 log2n번 수행으로 동전을 찾을 수 있기 때문에 가장 효율적

공간복잡도

• 입력 크기에 비례해서 작업 공간이 어떠한 비율로 증가하는지 분석
• 실측으로 공간사용량을 측정하는 경우, 시간 복잡도와 마찬가지로 여러 변수에 따라 크기가 달라질 수 있기 때문에 시간 복잡도와 함께 사용

 

<알고리즘의 표현 방법>

• 일반 언어로 표현된 알고리즘은 인간이 읽기는 쉽지만 단어를 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있음
• 순서도 : 다이어그램 종류 중 하나로, 여러 종류의 상자와 이를 이어주는 화살표를 이용해 명령의 순서를 보여주는 그림
• 유사 코드 : 특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓음(쓰는 사람에 따라 다양하게 표현 가능)
  • 유사코드 작성 시 주의사항
    • 프로그래밍 언어로 변환하는데 어려움을 느끼지 않아야 함
    • 명확해야 하며, 지나치게 세부사항을 기재하는 것은 오히려 알고리즘의 명확성을 떨어뜨림)

 

<재귀 함수>

• 문제를 해결하는 과정에서 해결하려는 문제와 크기만 다르고 자신의 해결 방법을 동일하게 적용하여 해결할 수 있는지 파악하여 주어진 문제를 푸는 방법(=Recursion, 되부름, 자기 호출)
• 병합 정렬, 퀵 정렬, 하노이의 탑, 팩토리얼 등 다양한 알고리즘에 사용

 

<수학적 귀납법>

• 어떤 성질이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법
  • 첫 번째 자연수에 대해 참임을 증명
  • 어떤 자연수에 대해 참이면 다음 자연수도 참임을 증명
• 재귀 호출의 정당성은 수학적 귀납법과 관련됨, 즉 자기보다 작은 문제에 대해서 이 알고리즘이 제대로 작동한다고 가정
  • 자신보다 작은 문제에 대하서 결론이 참임을 가정
  • 작은 문제와 자신의 문제의 관계를 파악하고, 자신의 문제에서도 결론이 맞음을 보임
• 알고리즘 설계 시 유의점
  • 무한 루프에 빠지지 않도록 주의해야 함
  • 재귀적인 관계를 잘 파악해야 함