[자료구조 with Python] 4. 선형 자료 구조 - 배열(2), 기본 메서드/함수 동작

 

 

 

 

 

Python에서 사용되는 모든 자료형은 Class로 정의가 되어 있으며, 각 자료형은 각각의 Method를 가지고 있다. 예를 들어 Python에서 배열의 한 종류인 List는 배열은 내부에 정의된 값의 순서를 반대로 지정하는 reverse() 메서드, 배열의 가운데 또는 마지막에 값을 추가하는 insert(), append() 메서드, 혹은 리스트의 모든 내용을 삭제하는 clear() 메서드 등...

 

Python이 아닌 C와 같이 오래 전에 컴퓨터를 제어하는 언어들은, 위와 같이 배열의 값을 추가하거나, 빼거나, 순서를 변경하는 모든 작업을 일일이 코딩해주어야 했다. 즉, 프로그래머들이 특정 기능을 수행하는 함수를 만들어 코드를 어떻게 작성하느냐에 따라 프로그래밍의 효율과 처리 시간에 차이가 날 수 밖에 없었다.

 

다행히 자료구조와 알고리즘으로 인해, 배열에 자주 사용하는 기능들은 거의 정형화되어 있고, Python의 배열형 자료의 메서드들은 이렇게 정형화된 패턴으로 코딩되어 있다. 이번 포스팅에서는, Python의 배열에서 사용하는 기본적인 메서드와 정의되어 있지 않지만 배열에서 자주 사용하는 기능을 구현하는 코드 패턴을 확인해보려고 한다.

 

 

1. insert(), append()

 

insert와 append 메서드는 list 자료형에서, 새 값을 list에 추가할 때 사용한다. 단, append 메서드는 배열의 가장 마지막 index에 값을 추가하는데 반해, insert 메서드는 함수 내에 index 인자를 추가하여, 지정한 위치에 새 값을 추가한다는 차이점이 있다.

 

 

이제, 별도의 클래스로 list 자료형을 새로 정의하고, insert와 append 메소드 내에 동작 코드를 작성하여, 가장 효율적인 코드가 무엇인지 확인해보려한다.

 

 

(1) append 메서드

 

먼저 append 메서드다. append 메서드는 인자값이 단순히 리스트의 가장 마지막 부분에 추가된다. 따라서, 기존의 리스트에 새 값을 리스트 형태로 만들어 추가하기만 하면 된다.

 

 

append 메서드의 코드만 보면, 새로 추가하는 값은 리스트화 되어 기존의 리스트에 추가만 되는 매우 간단한, 설명할 것이 없는 구조다. Big O 역시 O(1)로 효율도 매우 높다. 위 코드의 결과물은 아래와 같다.

 

 

 

(2) insert() 메서드

 

insert 메서드는 append보다 동작 방식이 조금 더 복잡하다. 우선, 함수 인자로 list의 index 값을 추가로 받으며, 이 index 값이 기존 list 크기를 초과하는 경우에만 list의 가장 마지막에 값이 추가된다. 추가로, 이 index 인자값이 음수일 경우도 고려를 해야하는데, list index와 달리 -1값이 가장 마지막 list index을 참조하는 것이 아니라, 그 이전에 위치한 index를 참조한다. 

 

 

insert 메서드 코딩 시 중점적으로 생각해야 할 것 중 첫 번째가 바로 list의 위치를 지정하는 index 인자다. 이 index 인자를 고려하여 insert 기능이 작동하는 과정을 의사코드로 나타내면 아래와 같이 나타낼 수 있다.

 

-----------------------------------------------------------------------

index 인자값이 list 길이 이상인 경우 : 

     list += [새 값]

     return True

list = list[:index] + [새 값] + list[index:]

-----------------------------------------------------------------------

 

위에서 생성한 클래스에 insert 메서드를 코딩하면 아래와 같이 나타난다.

 

 

해당 코드의 결과 역시 interactive 모드에서 작동한 것과 동일한 결과를 나타낸다.

 

 

index 인자로 인해 append보다 조금 더 복잡한 코드 양상을 띄지만, 각 코드의 실행 횟수가 value의 값에 상관없이

1이므로, insert 메소드 코드 역시, append 코드와 마찬가지로, big O가 O(1)로 효율이 매우 높은 코드다. 

 

 

2. clear(), remove()

 

(1) clear() 메서드

 

clear 메서드는 list 내의 모든 원소를 삭제하고, list 크기도 0으로 초기화하는 기능을 가지고 있다. 따라서, 이 clear 메서드는 단순히 원래의 list를 []로 정의하면 끝난다.

 

  

마지막에 test.clear()와 test.print_list() 코드를 추가하여 얻은 결과는 다음과 같다.

 

 

 

(2) remove() 메서드

 

remove 메서드는 list 내에 존재하는 값(value)을 인자로 받으며, 이 값을 list의 앞부분부터 검색하여 일치하면 삭제하는 기능을 가진다. 만약 list에 없는 값이 인자에 지정될 경우, 아래와 같이 에러 메세지가 출력된다.

 

 

remove 메서드의 기능을 동작시키는 절차는 아래와 같이 볼 수 있다. 우선 전달받은 함수 인자값이 list 내에 존재하는지 검색을 진행해야 한다(검색과 관련된 내용은 다음 포스팅부터 3부작으로 진행하려 한다). 검색값이 존재할 경우, 해당 값을 제외한 나머지 값들로만 list를 재정의하면 되며, 검색값이 없다면 에러를 발생시키면 된다. 아직 에러를 발생시키는 방법은 포스팅한 적이 없기 때문에 우선은 "검색값 없음"으로 출력하여 종료하는 것으로 코드를 짜보려 한다.

 

 

 

이전의 메서드들과 달리, remove 메서드의 효율은 조금 더 떨어지는데, value 인자의 값이 list 내에 존재하는지 확인하는 for 문 내의 코드가 최대 len(self.table) 만큼 실행되기 때문이다. 따라서 remove() 메서드의 BigO 값은 O(n)이 되는데, 앞서 보았던 메서드들의 BigO 표기값이 전부 O(1)이었던 것과 비교하면 효율성은 조금 떨어지는 것을 알 수 있다. 하지만 이 효율을 더 개선할 수는 없는데, 메서드 인자로 들어간 value의 값을 list 내에서 찾는 과정을 삭제하고서 메서드 코드를 작성하기는 어렵기 때문이다.

 

 

3. reverse()

 

마지막으로 reverse 메서드는 list 내의 모든 원소의 순서를 뒤집는 기능을 가진 메서드다. 일반적으로 두 변수의 값을 뒤바꾸는 작업에는 별도의 임시 변수(tmp와 같은)가 반드시 필요한데, Python은 다른 프로그래밍 언어와 달리 변수가 값을 저장하는 형태가 아니라 메모리 내의 값을 참조하도록 만든 형태라 훨씬 간단한 코드로 reverse 메서드를 구현할 수 있다.

 

 

위의 원리를 이용하여 reverse 메서드 코드를 작성하면 아래와 같이 나타낼 수 있다.

 

위의 remove 메서드와 마찬가지로, reverse 메서드도 for 문에 의해 list의 모든 원소를 훑으며 실행해야 하는 코드가 하나 존재한다. remove와 달리, for 문 내의 코드는 len(list) / 2 번만 실행되지만, BigO 표기에서 계수를 제외하고 표시하면 O(n)으로 remove 메서드와 효율은 동일함을 알 수 있다.

 

 

 

 

4. 배열값의 최대/최소/평균값 구하기

 

Python에서는 Iterable한 자료형(반복 가능한 자료형으로 for 문이나 range 등으로 내부 값을 반복적으로 확인할 수 있는 자료형 - list, dictionary, tuple 등) 내에 존재하는 원소 값 중 최대값과 최소값을 구할 수 있는 함수를 제공한다. 바로 max()와 min() 함수인데, 이들은 list나 tuple 클래스의 하위 메서드가 아니라 별도의 함수로 존재한다. 

 

 

list나 tuple 내의 최소/최대값을 찾기 위한 절차는 다음과 같다. 우선, list/tuple의 앞부분부터 값을 비교하여 작거나 큰 값을 임시 변수에 저장한다. 그리고, 저장한 임시 변수를 list/tuple의 다음 index에 위치한 원소값과 비교하여 다시 크기를 비교하고, 둘 중 큰 값이나 작은 값을 다시 임시 변수에 저장한다. 이 과정을 list/tuple의 마지막 index 원소값까지 비교하면 된다. 

 

max와 min 함수는 원래 list 클래스 외부에 작성해야 하나, 기존 함수와의 충돌을 고려하여 class 내부에 작성을 진행해보려 한다(어차피 처리 과정을 확인하는 것이니 상관없다).

 

 

 max, min 함수 역시 for 문에 의해 O(n)의 BigO 값을 가진다. 

 

 

---

 

이번 포스팅에서는 Python의 List 자료형에서 사용하는 메서드, 그리고 iterable 자료형의 최대/최소값을 출력하는 함수가 어떤 절차로 기능하는지, 그리고 그 절차를 직접 코딩함으로써 해당 코드들의 복잡도와 효율성에 대해 간략하게 살펴보았다. 다음 포스팅에서는, 배열형 자료에서 값을 검색하는 방법에 대해 알아보고, 최적의 검색을 진행할 수 있는 코드를 작성해보려 한다.

 

 

 

Fin.