[python 20] 알고리즘 연습 - 2

 

 

 

[알고리즘 - 1]에 이어서, 몇 가지 문제에 대한 알고리즘에 대해 살펴보기로 하자. 아주 크고 복잡한 문제들을 해결하는 방법인 "알고리즘"도 따지고 보면, 아래에서 소개하는 간단한 알고리즘(들)을 조합하는 것에 지나지 않는다. 작은 문제들을 풀어 보는 것에 절대 소홀하지 않기를 바란다. 

 

이번 글에서 살펴볼 알고리즘들은 다음과 같다.

 

   - 리스트에 저장되어 있는 데이터들의 합(sum) 구하기

   - 멱승(power) 구하기

   - 사용자로 부터 데이터를 입력받아 리스트에 저장하기

   - 리스트에서 특정한 값의 개수 구하기

 

이 글에 이어질 [알고리즘 - 3] 에서는 소팅(sorting, 정렬) 알고리즘에 대해 살펴 볼 계획이다.

 

 

○ 리스트 데이터의 합(sum) 구하기

 

최대값을 구하는 것 만큼 중요한 알고리즘 중의 하나는 리스트에 저장되어 있는 데이터 요소들의 합을 구하는 알고리즘이다. 아래와 같이 구할 수는 없는 노릇이다. 확장성이 없기 때문이다. 만약에 사이즈가 100개인 리스트가 있을 때 전체 데이터의 합을 아래와 같은 방식으로 구할 수 있을까?

 

 

 

데이터의 합을 구하는 절차를 다음과 같이 생각해 보자.

 

여기에 여러 숫자 데이터가 리스트를 구성하고 있다.  예를 들어, a=[3, 5, 2, 8, 3, 4] 라고 해 보자. 각 데이터를 컵에 담겨져 있는 물의 양(cc) 라고 생각해 보자. 예를 들어, a[0] 가 3 이므로 첫번째 컵에는 3cc의 물이 담겨져 있다고 생각하자. 지금 6개의 컵에 서로 다른 부피의 물이 담겨져 있는데, 이 물의 양을 모두 더한 합을 구하고자 한다. 어떻게 하면 될까? 여러 방법이 가능하겠지만, 가장 쉬운 방법 중의 하나는 눈금이 있는 빈 비이커를 하나 준비하고, 각 컵의 물을 차례대로 비이커에 쏟아 붓는다. 모두 쏟아 부은 후에, 비이커의 눈금을 읽으면 되겠다. 

 

이러한 절차를 그대로 적용해서 알고리즘을 만들어 보자

 

 

 

In[16] 에서 더할 데이터를 준비했다. In[17]에서 비어 있는 비이커를 준비했다. In[18]에서 s = s+a[0] 를 실행하는데 이 명령어는 s 에다 저장하시오 (s = ) 무슨 값을 ? = 기호의 오른편에 있는 값 s + a[0] 를.  현재까지는 s 에 저장될 값이 결정되어 있지 않다. 현재의 s 값과 a[0]를 더해 봐야 s 에 저장될 값을 알아낼 수 가 있다. 현재의 s 값은 0 이고 a[0]는 3 이므로 s 에 저장될 값은 3이 된다. 즉,  s = s+a[0] 명령어는 결국 s = 3으로 실행된다.  ln[18]에서 print(s) 했더니 3 값이 출려된 것을 확인해 주기 바란다.

 

리마인드 차원에서 다시 강조해 보자. Assignment 의 기본 문법은 "변수 = 값" 이다. 아무리 복잡한 명령어라도 결국 실행될 때에는 변수=값이 됨을 이해하기 바란다. 결국 프로그램이란 수없이 많은 (더할나위없이 간단한) assignment 명령어들이 순서있게 진행되는 절차일 뿐이다. 

 

다시 원래대로 돌아가서, 이제 두번째 컵의 물을 더할 차례이다. 현재 비이커에는 첫번째 컵의 물 만큼이 담겨 있다. 여기에 두번째 컵의 물을 더해서 담으려면 s = s+a[1] 이 된다. 비이커 s 에 담아라, 무엇을 ? 현재의 물의 양(s)에 두번째 컵의 물(a[1])을 더한 값을. 실제로 더한 후 8 값이 나온 것을 확인하자. 8은 어떤 값인가? 첫번째 데이터 3과 두번째 데이터 5를 더한 값이다. 

 

이런 과정을 계속 반복하여 모든 리스트의 요소 값을 더하게 되면 최종적으로 전체 데이터의 합을 구하게 된다. 이 과정을 모두 나타내 보면 아래와 같다.

 

 

 

위의 코드를 보자. 무엇인가 반복되는 것이 보이는가? 그렇다 뭔가 조금씩 변하긴 하지만, 동일한 행위(연산)들이 계속 반복된다. 조금씩 변하는 부분을 변수로 나타내 보면, 위의 연산은 결국 아래와 같이 표현할 수 있게 된다.

 

 

0부터 5 까지 1씩 변하는 x 값에 대하여   ->  for x in range(0, 6, 1):
변수 s 에 s+s[x] 값을 저장하시오          ->      s = s+a[x]

 

실제 코딩 후에 결과를 확인해 보자.  정말 단순하지만, 정말 중요한 알고리즘이다.

 

 

 

근데, 여기서 드는 궁금증 하나. 파이썬의 내장 함수 중에 sum( ) 함수가 있는데 그 함수를 바로 사용하면 안되나 하는 의문이다. 아래의 코드를 보자. 정말 단순한데 우리가 원하던 결과를 구해주고 있다.

 

 

 

하지만, 일반적인 문제에서는 위와 같은 기본적인 함수들을 활용하기 어렵다. 예를 들어, 리스트 내의 데이터의 합을 구하긴 구하는데, 리스트에 포함된 데이터 중 양수의 합 만을 구하고자 하는 경우이다. 위의 sum( ) 함수를 이용하기 어렵겠다. 그럼, 파이썬 본사(?)에다 연락해서 이와 같은 기능을 해 주는 새로운 함수를 하나 만들어 달라고 해야 하나? 웃자고 하는 소리다. 답은 너무 빤하다. 우리가 필요한 건 우리가 만들어야 한다. 그래서, 알고리즘 공부와 연습이 너무 너무 중요한 것이다. 

 

실제로, 양, 음이 섞여 있는 리스트에서 양수 만의 합을 구하는 알고리즘은 위에서 만들어 봤던 알고리즘을 조금만 수정하면 된다. 그냥 모두 더하는 것이 아니라, 양수인 경우에만 더하면 된다. 아래와 같이 하면 되겠다.

 

 

 

위의 코드를 함수로 정의해 보자. 

 

 

 

 

○ 멱승 (power) 구하기 

 

2의 3승 처럼 어떤수를 여러번 곱한 멱승을 구하는 코드를 만들어 보자. 위에서 본 합을 구하는 알고리즘과 정확히 일치한다. 대신, 초기값에 0을 두고 계속 곱해봤자 0 밖에 더 되겠나? 합을 구할 때에는 덧셈의 항등원 0 을 초기값으로 사용한 대신에, 멱승을 구할 때에는 곱셈의 항등원인 1을 사용해야겠다.

 

 

 

코드를 만들었으면, 특히 반복문의 경우에는 반드시, 여러분들이 먼저 여러분들의 머리(CPU, 중앙처리장치)와 종이/연필(메모리)를 이용해서 연산과정을 따라 가보기 바란다. 컴퓨터는 우리가 만든 코드 그대로 실행해 줄 뿐이며, 코드의 옳고 그름은 순전히 만드는 사람에게 달려 있다. 코드가 옳은지 항상 확인하고 검증하기 바란다. 우리가 만든 코드가 올바르게 실행되는 지를 검증하는 과정을 보통 디버깅 (debugging) 이라고 하는데 이에 대한 내용을 따로 한번 다루도록 하겠다.

p 값은 1
for 루프에 들어와서, ( x 값은 0, 1, 2 까지 변한다는 것을 확인하고 )
처음으로 x 값이 0일 때 반복, p=1*2 여서 p에 2 값이 저장되고,
그 다음으로 x 값이 1일 때 반복, p=2*2 여서 4 값이 저장되고,
마지막으로 x 값이 2 일때 반복, p=4*2 여서 8 값이 저장된다. 

코드가 확인이 됐으면 함수로 만들어 보는 연습을 꼭 해 보기 바란다. 

 

 

 

참고로, 파이썬의 내장함수 중에 멱승을 구하는 pow 함수가 있다. 한번, 사용해 보고 잊어 버리기 바란다. 

 

 

 

○ 사용자로 부터 데이터를 입력받아 리스트에 저장하기

 

input( ) 명령어를 사용하여 사용자로부터 숫자를 입력 받다가 만약 음수가 입력되면 입력을 중단하는 프로그램을 만들어 보자. 그 때 까지 입력된 데이터는 리스트에 저장하는 것으로 하자. 이 예제의 경우와 같이, 반복의 횟수가 고정되어 있지 않고 가변적인 경우에는 for 문 보다는 while 을 사용하는 것이 유리하다.

 

 

#1 에서 비어 있는 리스트를 하나 준비한다.  While 루프를 통해 입력된 데이터를 이 리스트에 저장(append) 하게 될 것이다. #2와 #3에서 데이터를 입력받는다. #4에서, 그 값이 음수이면 전체 루프를 break (빠져 나오게) 된다. 그렇지 않으면, #5 명령어가 실행되어 입력된 데이터가 리스트에 추가되게 된다. 음수가 입력되어 while 루프를 빠져 나오게 되면, #6에서 그 결과를 화면에 출력하게 된다. 

 

루프의 뼈대는 while True : 로 선언하여 무한 루프로 만들어 주고, 내부에서 break 할 수 있는 조건을 만들어 결국에는 루프를 종료할 수 있도록 하는 구조를 가지고 있다. 반복횟수가 고정되어 있지 않은 경우에 가장 일반적으로 사용할 수 있는 뼈대로서 활용도가 높다. 

 

 

○ 리스트에서 특정한 값의 개수 (frequency) 구하기

 

간혹 데이터의 개수를 세어야 하는 경우가 있다. 예를 들어, 데이터가 중복 저장되어 있는 리스트 a=[1, 2, 3, 4, 1, 2, 3, 1, 2, 1] 에서 1의 개수를 세는 형태의 문제이다. 

 

만약 우리가 리스트에서 1 값의 개수를 센다고 한다면, 우리가 결국 구해야 하는 어떤 값을 cnt 라고 해 보자. 리스트 데이터를 하나씩 하나씩 1과 비교해 보면서 만약 1이면 cnt 값을 1씩 증가시키면 된다. 리스트의 마지막 요소까지 방문을 완료했을 때 cnt 에 저장되어 있는 값이 1의 개수가 된다.  

 

위의 알고리즘대로 만들어 본 코드는 아래와 같다. 

 

위의 코드를 일반화 시켜서 데이터의 리스트와 찾아야 할 값을 인자로 넘겨받아 그 개수를 카운트하는 함수로 한번 만들어 보자