[python 19] 알고리즘 연습 - 1

이번 글에서는 실제 주어진 문제를 해결할 수 있는 과정(procedure) 인 알고리즘(algorithm)을 만들어 보는 연습을 통해 파이썬에 대한 이해도를 높여 보고자 한다.

 

 

 

○ 알고리즘 algorithm 이란 ?

 

알고리즘은 "어떤 주어진 문제를 해결 할 수 있는 절차"라는 뜻이다. 거꾸로 읽는다면, 알고리즘에서 제시된 절차를 따라가다 보면 문제에 대한 답을 구할 수 있다는 뜻이다. 

 

마치 현재 위치에서 어떤 목적지(destination)에 이르는 경로를 찾는 문제와 동일하다. 보통의 문제에서 현재 위치로 부터 목적지에 이르는 경로는 여러가지로 존재한다. 어떤 경로는 (좋은 답이긴 한데) 비용이 많이 들어서, 또는 (좋은 답이긴 한데) 기술적으로 어려워서 실행이 어려운 경로도 존재한다. 이런 경로 (답)을 "실행 불가능(infeasible) 하다"라고 표현하기도 한다. 그럼, 문제는 실행가능한 경로 중에 어느 경로를 선택할 것인가 하는 문제가 된다. 경로에는 좋은 경로도 있고 바람직하지 않은 경로도 있고, 괜찮은 경로지만 나한테는 잘 안맞는 경로도 있다.  이 문제에서 "목적지"를 문제의 "답" 이라고 하면, 그 목적지에 이르는 "경로"는 그 "답"을 이끌어내는 "과정", 즉 알고리즘이라고 볼 수 있다.   

 

하나의 목적지에 이르는 경로가 여러개 있듯이, 하나의 문제를 해결하는 알고리즘은 여러 개가 존재할 수 있다. 하지만, 어떤 경로는 좋은 경로이고 어떤 경로는 좋지 않은 경로이 듯이, 알고리즘에도 좋은 알고리즘과 좋지 않은 알고리즘이 존재한다. 좋은 알고리즘과 좋지 않은 알고리즘을 구별하는 기준은 무엇이 있을까? 

 

우선 속도가 있다. 상대적으로 적은 수의 명령어로 문제를 해결하는 알고리즘은 바람직하다. 알고리즘 실행에 소요되는 시간이 짧을 것이기 때문이다. 특별히 어떤 종류의 소프트웨어에서 속도는 대단히 중요한 요소가 된다. 우리가 보통 실시간 시스템 real time system 이라고 부르는 소프트웨어가 그러하다. 우리 생활과 가깝게 사용되는 실시간 시스템으로는 차량 내비게이션 소프트웨어가 있다. 목적지를 지정했는데 목적지에 도달하기 위한 최단경로 shortest path를 구하는데 1분 이상 분 단위의 시간이 소요된다면 그러한 소프트웨어의 유용성은 매우 낮을 것이기 때문이다.

 

또 하나의 기준으로 들 수 있는 것은 확장성 extendability 이다. 확장성이란 알고리즘의 큰 변화 없이 다양한 사이즈의 문제를 풀 수 있는지의 여부이다. 예를 들어, 여러 숫자의 합을 구하는 알고리즘인데 10개 데이터의 합을 구하는 방식과 20개 데이터를 구하는 방식이 상이하다면 역시 실 생활에서의 활용성은 크게 제한받을 것이다. 하나의 알고리즘으로 여러 사이즈의 문제를 해결할 수 있는 알고리즘이 바람직하며, 수정하더라도 최소한의 수정으로 해결할 수 있는 알고리즘을 개발하는 것이 필요하다.

 

문제의 규모가 커지면 고려해야 할 요소들이 더 필요할 수 있으나 일단은 속도와 확장성을 고려하면서 알고리즘을 만들어 보길 바란다. 똑같은 결과를 내지만 프로그램의 사이즈가 적을수록, 프로그램이 처리할 수 있는 데이터의 사이즈에 대한 제한이 없을수록 좋은 알고리즘이 된다.

 

몇가지 간단한 문제들을 다루어 보면서 알고리즘에 대해 고민해 보는 시간을 가져 보자.

 

○ 알고리즘 연습 1 : 최대값 max 구하기

 

2개의 변수 a와 b에 특정한 값이 저장되어 있다. 예를 들어, a에는 10, b에는 6의 값이 저장되어 있다고 가정해 보자. 이 2개의 값 중에 큰 값을 구하는 프로그램을 작성해 보자.

 

 

 

프로그램 실행 후에 max 값을 "활용" 하기 위해서는 max 값을 저장해 두어야 한다. 수정된 다음의 코드를 보자. 위의 코드와의 차이가 느껴지는가?

 

 

 

위의 코드를 수정하여, 3개의 변수 a, b, c에 저장된 값 중 가장 큰 값을 구하는 프로그램을 만들어 보자. 혼란을 사전에 없애기 위해, a, b, c 세값은 모두 서로 다른 값이라고 가정해 두자. 어떻게 찾을 수 있을까? 알고리즘을 만들어 보자. 여러 방식이 가능하겠지만, 가장 기본적인 알고리즘으로 다음과 같은 절차를 생각해 볼 수 있겠다.

[알고리즘] a 값과 b 값을 비교하여, 만약 a 값이 크다면 a 값과 c 값 중에 큰 값이 최대값이 된다. a 값과 b 값을 비교하여 만약 b 값이 크다면, b 값과 c 값 중에 큰 값이 최대값이 된다.

 

위의 알고리즘을 코드로 바꾸어 보면 다음과 같다.

 

 

 

알고리즘을 만들면 그 알고리즘이 "우리가 기대하는 바와 같이 잘 동작하는지"를 확인할 필요가 있다. 이 과정을 보통 테스트(Test)라고 부른다. 테스트를 하는 경우에 가장 중요한 원칙을 하나 든다면, 한두가지 경우에 잘 동작한다고 해서 모든 경우에 문제(에러) 없이 잘 동작한다고 확신해서는 안된다는 것이다. 가능한 한 다양한 경우(이를 Test Case 라고 부른다)에 대해 결과가 잘 나오는지를 확인해 보아야 한다. 위의 코드를 테스트할 수 있는 케이스로서 무엇을 들어 보면 될까? 사실 위의 코드는 몇 가지 경우를 다루고 있나? 

 

아래와 같이 모두 4가지 경우(case)가 있고, 3가지 결과가 있으며, 이 모든 경우를 확인해 보기 위해서는 최소 6개의 테스트 케이스에 대해 모두 잘 작동하는지 확인해 볼 필요가 있다. (이론상 그렇다는 것이다) 실제로 모든 경우를 다 따지는 것은 어렵다. 하지만, 최소한의 경우에 대해 테스트를 하고 본인이 만든 알고리즘의 신뢰도(정확도)를 확인해 보는 것은 중요하다.  

 

 

 

 

처음 만들어 보는 알고리즘이니 만큼, 함수로 선언하여, 모든 경우에 대해 잘 동작하는 것을 확인해 보았다.

 

[그림] 최대값 찾기 알고리즘

 

 

[그림]  알고리즘 테스트

 

 

○ 알고리즘 연습 2 :  (확장 가능한) 최대값 max 구하기

 

3개의 데이터에 대해 최대값을 찾는 문제에 대해 알고리즘을 만들어 보았다. 이 알고리즘의 확장으로, 4개의 값 중 최대값을 구하는 프로그램을 작성해 보자. 3개 중에 최대값을 구하는 문제 까지는 풀어 봤는데, 그럼 4개인 경우에는 어떻게 해야 할까? 다시 고민이 된다. “음... a 값과 b 값 중에 큰 값을 구하고, c 값과 d 값 중에 큰 값을 구한 다음에, 그 2개 값의 크기를 비교하면 되겠군.”

 

그렇다면, 5개 데이터의 경우에는? 6개 데이터의 경우에는? ... 어떤 생각이 드는가? 분명히 비슷한 문제임에 도 불구하고, 문제의 크기 (다루어지는 데이터의 수)가 변함에 따라 알고리즘을 새로 만들어야 하는 문제가 생긴다.

 

하지만, 조금만 아이디어를 바꾸어 다음과 같은 알고리즘을 생각해 보자.

 

[추천 알고리즘] 현재, 본인 앞에 4개의 값 a, b, c, d가 일렬 종대로 서 있다. 즉, 현재 나는 a 값 만 보인다. 내가 현재까지 알고 있는 값 중에 가장 큰 값은 a 값이다. 그래서, 첫 번째 값인 a를 가장 큰 값 m 으로 본다. 이제 그 다음 값인 b와 현재까지 가장 큰 값 m 을 비교해 본다. 만약 m 값이 크다면 현재까지 최대값은 m 값 그대로 두면 된다. 만약 b 값이 m 값 보다 크다면 b 값을 최대값 m으로 두면 된다. 

이러한 과정을 계속 반복한다. 마지막 값 d 까지 비교가 끝났을 때에 m 에 저장되어 있는 값이 가장 큰 값이 된다. 

 

위의 알고리즘을 코드로 만들어 보고, 하나의 테스트 케이스에 대해 실행한 예를 보이면 아래와 같다. 

 

 

 

#1 까지는 m에 a 값이 저장된다. #2 까지는 a 와 b 중에 큰 값이 m 에 저장되고, #3에 이르면 a, b, c 중에 큰 값이 m 에 저장된다. #4에 이르면 a, b, c, d 중 가장 큰 값이 m에 저장되게 된다.

 

추천하건대, 여러가지 테스트 케이스에 대해 여러분이 직접 파이썬이 되어 코드를 Line by Line 으로 연필로 따라가 보기 바란다. 정말 좋은 공부 방법이다. 느린 듯 하지만, 결국 정상에 오르게 되는 최단경로인 셈이다. 공부하는 방법에 왕도란 없다. 여기서, 왕도란 좋은 방법이 아니다. 쉬운 방법이다. 공부하는 방법에 쉬운 방법은 없다 !! 우리가 잘 알고 있듯이... 우리 학생들 홧팅~하기 바란다.

 

실제로 위의 알고리즘을 5개의 변수, a, b, c, d, e 의 최대값을 찾는 문제로 확장해 보면 아래와 같다. 빨간색 펜으로 표시된 부분이 4개 문제의 경우와 비교해서 추가된 부분이다. 4개 문제에 해당하는 코드는 전혀 달라지지 않았다는 점에 주목해 주기 바란다.

 

 

 

우리가 다루는 데이터를 리스트(List) 데이터 구조에 저장하게 되면 파격적인 변화가 온다.

 

우선 각 변수를 리스트 요소로 바꿔보자.

 

 

 

그렇게 바꾸고 보니 각각의 if 문이 아래와 같은 형태가 된다.

 

 

 

위와 같이 만들어 보면 k=1 이면 #2 코드에 해당하고, k=2 이면 #3, k=3 이면 #4, k=4이면 #5 코드에 해당한다. 실제로 k 값을 입력해서 위의 In[29] 코드와 동일하게 나오는지를 확인해 보기 바란다.

 

그래서, 최대값을 구하는 전체 코드는 다음과 같은 형태가 된다. 여기서 각각의 if 문은 아래의 코드처럼 일반화시킬 수 있겠다. 이전에 [반복을 위한 for, while] 제목의 글에서 for 반복문과 리스트는 천생연분의 조합이라고 했었는데, 그 좋은 예제가 되겠다. 

 

 

 

재미로, 코드는 그대로 남겨두고 리스트 데이터만 바꿔 봤다. (range( )함수에서 리스트의 갯수를 대신해 len( ) 함수를 사용한 것도 유심히 살펴보기 바란다) 데이터가 바뀌어도 알고리즘은 바뀌지 않았다. 데이터가 바뀔 때 마다 알고리즘이 바뀌면 좋은 알고리즘이라고 말하기 어렵겠다. 

 

 

 

이와 같이 데이터가 바뀌어도 알고리즘이 바뀌지 않을려면, 알고리즘의 기본적 구상도 중요하지만 그를 밑받침할 수 있는 알맞은 데이터구조를 찾아내는 것도 매우 중요하다.  그래서, 알고리즘과 데이터구조는 항상 한 몸이다. 실제로, 컴퓨터공학과에서 다루는 주요 과목으로 "데이터 구조와 알고리즘"이라는 과목이 있는 이유가 된다. 

 

우리가 원하던 기능을 하는 알고리즘과 코드를 만들었다. 이제 이 코드의 재사용성 (reuse)을 높이기 위해서 함수로 정의하는 것이다. 다음을 참고하기 바란다.