[python 24] 알고리즘 연습 - 4 : 두번째로 큰 값 찾기

 

 

 

리스트 중에서 가장 큰 값을 찾는 알고리즘을 만들어 본 후에, 그 문제를 확장하는 의미에서 "리스트에서 두번째로 큰 값을 찾는 알고리즘을 만들고 코드를 제시하라" 라는 과제를 내었다. 대학 1학년 1학기 학생들이 대상이다. 아주 다양한 아이디어가 제시되었다. 그 중에 몇가지 우리 학생들의 아이디어를 공유해 보고자 한다.

 

 

○ 큰 값을 구한 후에 그 값을 제거하고 나머지 값 중에 제일 큰 값을 구한다.

 

첫번째 아이디어는 (1) 먼저 리스트에서 가장 큰 값을 먼저 구한다 (2) 가장 큰 값을 가장 작은 값으로 대체한다. 그러면, 원래는 두번째로 큰 값이었던 값이 가장 큰 값이 된다. (3) 변경된 리스트에서 가장 큰 값을 구한다.

 

먼저 기본적인 아이디어를 스케치해 보고, 실제 그 아이디어가 작동하는지를 확인해 보자.  In[97]에서 리스트 a 의 최대값을 구했다. 그 값을 다른 값으로 바꾸기 위해서는 그 값의 위치(인덱스)를 알아야 하기에 In[98]에서 리스트의 index( ) 함수를 이용해서 가장 큰 값 m 의 인덱스를 구하고, 그 값을 가장 작은 값으로 바꾸었다 ( In[100] ). 꼭 최소값으로 바꿀 필요는 없고 충분히 작은 값 (sufficiently small number)로 바꿔줘도 되겠다. 바뀌어진 리스트에서  max 값을 구하면 그 값은 리스트에서 두번째로 큰 값이 된다.

 

 

 

자, 알고리즘에 대한 스케치는 끝났다. 이제 실제 코드를 만들어 보자. 내장함수를 최대한 사용하지 말고. 여러번 말하지만, 알고리즘 공부를 하려면 내장함수 사용을 최대한 자제하는 것이 좋다. 

 

위에서 확인한 알고리즘을 그대로 코드를 만들어 보면 아래와 같다. 우리가 지난 글에서 보았던, 최대값의 위치를 찾는 코드와 max 값을 구하는 코드가 활용되었다. 

 

 

 

○ 두번째 큰 값은 리스트를 오름차순으로 소팅했을 때 마지막에서 두번째 있는 값이다.

 

리스트를 소팅(sorting) 한 후에 마지막에서 두번째로 있는 값이 두번째로 큰 값이다. 아주 명료하고 깔끔한 아이디어다. 아이디어가 실제 작동하는지를 파이썬의 내장함수 sorted( )를 활용하여 확인해 보자. 

 

sorted( ) 함수의 설명은 다음과 같다. 실제로 아래 코드의 In[118] 처럼 사용하면 된다. 리스트에도 sort( ) 메쏘드가 있는 것을 기억하면 좋겠다. 리스트의 sort( ) 함수는 리스트 자체를 정렬하여 원래 데이터의 순서를 제거해 버린다는 차이점이 있다.

 

 

 

 

 

결국, 소팅한 후에 마지막에서 두번째 값을 구하면 된다. 우리가 몇가지 소팅 알고리즘을 살펴본 적이 있는데 선택정렬(selection sorting) 을 활용해서 코드를 만들어 보면 아래와 같다. 선택정렬은 [python 23] 알고리즘 연습-3 에 소개되었으니 참고하기 바란다.

 

 

 

 

○ 리스트의 각 값에 대해 자기 보다 큰 값의 갯수를 세었을 때 그 갯수가 1인 수가 두번째로 큰 수이다

 

리스트의 각 데이터 요소에 대해 리스트 중에 자기보다 큰 값을 모두 세어본다. 세어본 결과 그 갯수가 1인 수가 두번째로 큰 수이다.

 

리스트에 포함된 어떤 한 수에 대해 그 수 보다 큰 값의 갯수를 세는 알고리즘을 한번 생각해 보자. 다음의 코드를 보자. 어떤 값 a[0] 에 대해 a 리스트에 포함되어 있는 값 중 a[0] 보다 큰 값의 갯수를 저장하는 변수 cnt 를 #1에서 0으로 초기화하였다. 전체 리스트의 값을 모두 방문하면서 자기 보다 큰 경우에 cnt 값을 1씩 증가시키는 코드이다 (#2)

 

 

 

이를 리스트의 모든 요소에 대해 적용하게 되면, for 안에 for 가 있는 이중 루프 (nested loop) 가 된다. 

 

 

 

물론, 모든 알고리즘 마다 약점이 있을 수 있다. 그런 약점들을 찾아내고 보완하는 것이 소프트웨어 개발자들의 가장 큰 덕목이기도 하다. 문제가 무엇인지 알아야 그 문제를 해결할 단초를 찾아낼 것이 아닌가?

 

만약 제일 큰 값이 2개 이상 중복되어 있다면 이 알고리즘은 어떤 결과를 만들어 낼까? 아래의 리스트 데이터는 가장 큰 값인 9가 2개가 포함된 경우이다. 이 경우에 두번째로 큰 값인 8의 cnt 는 2 가 되어 위의 In[78]의 if 문에서 걸러지지 못한다. 이 부분을 보완하려면 어떻게 해야 할까? 

 

 

 

근데, In[133]에서 두번째로 큰 값은 9 인가, 8 인가? 내가 찾고자 하는 값이 내림차순으로 정렬했을 때 두번째에 해당하는 값이라면 9가 맞는 답이고, 우리 데이터 세트에 발생하는 값 중에 (중복을 무시하고) 두번째로 큰 값을 찾고자 했다면 8이 정답이 될 것이다. 

 

사실 이와 같은 문제는 모든 알고리즘에 공통된 문제이기도 하다. 알고리즘을 만들기 전에, 우리가 찾고자 하는 답이 무엇인지 부터 명확히 정의해야 한다. 답이 무엇인지 명확히 정의되어야 그 답을 찾아낼 수 있는 알고리즘도 만들 수 있을 것이다. 찾고자 하는 답이 애매하면 알고리즘도 당연히 애매해 지는 법이다. 

 

 

 

○ 두번째로 큰 값은 max 값보다 작은 값 중에 가장 큰 값이다. 

 

이 아이디어는 리스트에 있는 값들 중에 두번째로 큰 값을 찾으려고 비교를 할텐데, 그 비교에 가장 큰 값은 포함시키지 않는 것이다.

 

아래 코드에서 #2 부분의 조건이 max 값 보다 작으면서 가장 큰 값을 찾기 위한 조건식이다. 1개의 조건식에 2개 이상의 조건식이 포함되어 있다. m2 < x < m 을  m2<x  and  x<m 의 복합조건으로 표시할 수 있다. 되도록 이면 단순조건을 and 또는 or 를 이용하여 조합하는 형태로 조건식을 만들기를 추천한다. #1에서 편의상 max( ) 함수를 사용해 보았다. "내장함수 사용하지 말라면서?" 라고 우기지 말기.

 

 

 

위 코드에서의 #2의 조건식을 조금 다르게 나타내 보았다. 

 

 

 

 

 

○ 마지막 아이디어다. 최대값이 바뀌면, 바뀌기 전 최대값이 두번째로 큰 값이 된다.

 

이 아이디어는 최대값을 구하는 알고리즘을 가장 잘 활용한 경우로 생각된다. 아래는 최대값을 구하는 코드이다. 

 

 

 

위의 코드에서 #1의 조건이 만족되면 #2에서 최대값 m 이 현재의 a[x] 값으로 바뀐다. 그럼, 바뀌기 전의 최대값이 현재까지 두번째로 큰 값이 된다. 최대값이 바뀔 때 마다, 바뀌기 전 최대값을 두번째 큰 값으로 저장해 두면 되겠다. 이를 반영하면 아래와 같은 코드가 된다.

 

 

 

이 방법의 경우에도 한가지 약점이 있다. 만약에, 리스트의 첫번째 값이 가장 큰 값이어서 #1의 조건식이 한번도 True 가 되지 않으면 #2의 코드가 한번도 실행되지 않아 m2 값이 최초에 저장한 값 (보통, 초기값 initial value라고 부른다) 에서 바뀌지 않는다. 실제그런 경우를 살펴보면, 

 

 

 

사실 위의 문제는 두번째로 큰 값이 가장 큰 값 뒤에 나타나는 경우에 항상 문제가 된다. 아래에서 그 예를 살펴보자. In[10]을 보면 

 

 

 

그래서, 다음의 elif 가 필요하다. 즉, 현재 테스트 하는 값 a[x]가 가장 큰 값이 아니라면 (아래 코드에서 #1의 if 조건), 그 값이 두번째로 큰 값인지 확인해 보는 것이다. 아래 코드의 #2의 elif가 여기에 해당한다. else 경우는 고려되지 않음을 명확하게 보이기 위해 pass (null operation) 하였다.  

 

 

 

[보충] pass - 파이썬에서 pass 는 null opertaion 을 뜻하는 말로, 실제 아무 일도 벌어지지 않는다. 실제로는 어떤 명령어든 들어가야 할 자리이지만 아무 것도 실행될 필요가 없을 때 그 자리를 채워주는 용도로 사용된다. 예를 들어 위의 else : 다음에는 else의 경우 (if도 아니고, elif 도 아닌 경우를 말함)에 실행되어야 할 명령어가 나타나야 하지만 우리 경우와 같이 아무 작업도 수행될 필요가 없을 경우에 pass 를 사용한다. 실제로, else : 처럼 콜론 이후에 아무 명령어도 없으면 "expected an indented block" 이라는 에러가 발생한다. 

 

 

 

※ 과제를 통해 느낀 점은 무엇인가?

 

첫째, 알고리즘이 중요하다. 주어진 문제를 어떻게 풀 수 있는지 절차를 찾아내야 한다. 파이썬 코드는 저절로 따라와야 한다. 알고리즘을 파이썬으로 바꾸는 것은 단순한 작업이다. 파이썬 코드를 만드는게 어려워서는 안된다. 파이썬 문법으로 배웠던 예약어가 몇개나 된다고.

 

둘째, 내가 만든 코드가 항상 (always) 잘 작동하는지 다양한 경우 (테스트 케이스) 에 대해 실행해 보는 것이 중요하다. 코드의 오류를 최소화하는 노력이기도 하지만, 이런 연습을 통해 알고리즘의 약점을 쉽게 찾아낼 수 있게 된다.

 

셋째, 하나의 문제를 해결할 수 있는 알고리즘은 1개가 아니다. 정답인 알고리즘이 있는 것이 아니다. 답은 하늘의 별 만큼 많을 수 있다. 그 무수히 많은 답 중에 우리 문제에 가장 알맞은, 가장 적합한, 가장 좋은 알고리즘을 찾아내는 것이 중요하다.

 

그런데 위의 3가지 능력 - 알고리즘을 찾아내는 능력, 알고리즘의 약점을 보완하는 능력, 그리고, 알고리즘의 적합도를 평가하는 능력 - 은 저절로 만들어지지 않는다. 많은 고민과 연습을 통해야 한다. 근데, 한번 터득하면 없앨래야 없앨 수 없는 능력이 된다. 유지하는데 돈(시간, 노력)이 1도 들어가지 않는다. 오, 이런게 진짜 경쟁력이다.