Studyenthusiast

1805년 겨울에 프랑스의 나폴레옹의 군대는 아우스터리츠(Austerlitz, 현재는 체코의 남동쪽에 위치한 지역)라는 곳에서 오스트리아와 러시아 연합군과 대치하고 전투가 임박한 상태였습니다. 당시에 나폴레옹은 자신의 병력이 연합군보다 약 2만 명이 적은 상황에서, 연합군이 나폴레옹 군대의 옆쪽으로 공격하도록 유도한 후에, 연합군의 중앙을 공격하였습니다.

두개의 무리로 나누어진 연합군은 당황하여 도망가느라 바뻤고 나폴레옹의 군대는 각각의 남은 무리들을 공격하여서 대승을 거두었습니다. 약 3주후에 오스트리아는 나폴레옹과 조약을 맺고 프랑스에게 많은 땅을 내줌과 동시에 거액의 전쟁 보상금또한 지불하였다고 합니다.

2016년 미국 대통령 선거에서 승리한 도널드 트럼프 대통령또한 부통령인 마이클 펜스와 함께 분할 정복 전략으로 단기간에 많은 선거 유세를 소화하여 미국의 45번째 대통령이 되었습니다.

긴 글 읽어주셔서 감사합니다.

​

오일러(Leonhard Euler, 1707~1783)는 스위스의 수학자, 물리학자, 천문학자, 논리학자, 공학자로서 그래프의 창시자라고도 알려져 있습니다.

​

​

특히나 오일러의 등식들은 수학의 아름다움(?)을 표현하는 식으로 유명하게 알려져 있습니다. 이 식을 잘 살펴보면 영역이 다른 다섯 가지 수인 0,1(상수/constant), 자연상수 e (해석학), 원주율 π, 그리고 허수 i (대수학)가 모두 하나의 식에 포함되어 있으며, 수학의 가장 기초가 되는 4가지 연산인 곱셈, 지수, 그리고 등호가 모두 쓰인 책이기 때문입니다. 아인슈타인과 함께 20세기의 최고 물리학자로 불리는 리처드 파인만(Richard Feynman)은 이 식을 "수학에서 가장 비범한 식(the most remarkable formula in mathematics)"이라며 극찬하였습니다.

​

​

한편 1735년 프러시아의 쾌니히스베르크(현재는 러시아의 칼리닌그라드)에 위치한 프레겔 강 한가운데 섬 2개에 놓은 7개 다리가 있는데 주민들이 오일러에게 이 다리들을 빠짐없이 1번씩만 지나서 출발점으로 돌아올 수 있는지 물어보았습니다. 오일러는 그렇게 할 수 없다는 답변을 전달해 주었는데, 이 문제가 최초의 그래프 문제로 알려져 있습니다.

​

이 문제는 한 붓 그리기와 같은 문제이고, 오일러는 다리(그래프의 간선)를 한 번씩만 지나서 출발점으로 되돌아오려면 각 정점의 차수가 짝수여야 한다는 것을 증명하였습니다. 주어진 그래프에서 임의의 정점에서 출발하여 모든 간선을 빠짐없이 한 번씩만 지나면서 출발점으로 돌아오는 경로를 오일러 서킷(Euler Circuit) 또는 오일러 사이클이라고 합니다.

알고리즘이 주어진 경우에는 알고리즘의 연산 수행 횟수를 파악해 함수로 표현할 수 있어야 합니다. 연산 수행 횟수란 선언 및 초기화 문이난 조건문, 반복문을 제외한 순수한 실행문으로, 산술연산 뿐만 아니라 출력문이나 return문이 수행되는 횟수를 포함합니다. 

특히 산술연산은 하나의 식 내에 포함된 연산자의 수만큼 실행된다고 가정하고 연산횟수를 파악합니다. 예를 들어

a= (a+b) / c + 1 의 경우 연산 과정이 다음과 같습니다.

x = a + b,                     y = x / c         ,            a = y + 1

그러므로  a = (a+b) / c + 1의 연산 실행 횟수는 3이 됩니다.

하나의 문제를 해결하기 위한 다양한 알고리즘 중 가장 효율성이 좋은 것을 선택하기 위해서는 알고리즘의 수행시간, 차지하는 기억 공간 등의 비용으로 판단합니다.

복잡도( Complexity:O(n) )

알고리즘 수행 시 필요한 시간 또는 공간 비용

1. 시간 복잡도 (Time Complexity)

- 프로그램이 수행되는 시간

2. 공간 복잡도 (Space Complexity)

- 프로그램이 차지하는 기억 공간

f(n) = O(g(n))     f  ,  g: 음수값을 갖지 않는 함수

알고리즘은 복잡도가 낮을수록 효율적입니다. 즉, 수행 시간이 짧거나 기억 공간을 적게 사용하는 알고리즘이 효율적이라고 할 수 있습니다. 그런데 최근 하드웨어 기술의 발달로 기억장치에 대한 비용이 줄어 기억 공간보다는 수행 시간에 단축에 대해 더 고려하고 있습니다. 그래서 일반적으로 복잡도는 시간 복잡도를 의미하게 됩니다.

알고리즘의 복잡도는 'Big-O 표기법'을 사용하는데 복잡도 f(n) = O(g(n))는 "f(n)은 g(n)의 차수"라고 읽습니다.

이 복잡도는 f(n)은 n ≥ n0 인 모든 자연수 n을 입력으로 하는 알고리즘이 수행될 때, 그 수행시간이  f(n) ≥ c * g(n)이 되는 양의 정수 c와 n이 존재하면 성립하는 공식으로 알고리즘이 n개의 입력으로 수행될 때, 그 수행 시간이 |g(n)|에 양의 정수 c를 곱한 것보다 같거나 작은지를 확인하면 됩니다.

코끼리를 냉장고에 넣는 법은 다음과 같이 표현할 수 있습니다.

1) 냉장고 문을 연다.

2) 코끼리를 냉장고에 넣는다.

3) 냉장고 문을 닫는다.

위와 같은 설명도 어떻게 보면 하나의 알고리즘입니다. 이와 같이 알고리즘을 일반적인 언어로 작성할 수 있지만 순서도와 의사코드와 같은 표현으로 작성할 수도 있습니다.

순서도(Flow Chart)

- 명령의 종류와 기능에 따라 도표를 만들고 명령들의 순서대로 도표를 나열해 표현하는

의사코드(Pseudo-code)

- 일반적인 언어와 프로그램 코드를 적절히 이용해 명령어들을 나열한 방식입니다.

알고리즘(Algorithm)이란 문제를 해결하기 위한 체계적인 단계를 뜻합니다.

알고리즘은 입력부터 출력에 이르기까지 모든 단계를 포함하는 것으로 하나의 문제를 해결하더라도 다양한 알고리즘이 존재할 수 있습니다. (예를 들어 똑같은 수학 문제를 푸는데 있어서도 여러가지 방식의 공식을 사용해서 문제를 푸는 것과 같다고 볼 수도 있습니다.)

*** 무엇보다도 알고리즘은 가장 효과적인 것을 선택하는 것이 중요합니다. ***

알고리즘은 다음과 같은 특성들을 가지고 있습니다.

1. 입력 (Input)

문제와 관련된 입력이 반드시 존재해야 합니다.

2. 출력 (Output)

입력을 처리한 출력(결과)이 반드시 존재해야 합니다.

3. 정확성 (Correctness)

입력을 이용한 문제 해결 과정과 출력은 논리적이고 정확해야 합니다.

4. 유한성 (Finitenss)

입력에 제한된 개수의 명령 단계를 거쳐 출력을 내고 반드시 종료되어야 합니다.

5. 효율성 (Effectiveness)

문제 해결 과정이 효율적이어야 합니다.

6. 일반성 (Generality)

같은 유형의 문제에 대해 항상 적용될 수 있어야 합니다.

7. 확정성 (Definiteness)

같은 입력에 대해 출력이 항상 확정적이어야 합니다.