파이썬 자료구조 2-2장. 배열이란?

1. 배열 원소의 최댓값을 구하는 함수 구현하기


# max.py
from typing import Any, Sequence

def max_of(a: Sequence) -> Any:
    maximum = a[0]
    for i in range(1,len(a)):
        if maximum < a[i]:
            maximum = a[i]
    return maximum

if __name__ == '__main__':
    num = int(input("원소 수 : "))
    list_A = [None] * num
    for i in range(num):
        list_A[i] = int(input(f"x[{i}] 요소 값을 입력 :"))
    print(max_of(list_A))

max_of 함수를 보면 for문에서 배열 원소를 하나씩 차례로 살펴보고 있다. 이렇게 하나씩 차례로 주목하여 살펴보는 방식을 알고리즘 용어로 스캔 이라고 한다.
cf) 함수 어노테이션
파이썬은 자료형 선언 없이 변수나 함수를 자유롭게 사용할 수 있지만, 명시적으로 해석하기 어려운 경우가 있다. 그래서 등장한 기능이 어노테이션(주석달기)이다. 말 그대로 주석 달기일 뿐이며 코드 자체에는 어떠한 영향도 미치지 않는다. 함수 어노테이션은 함수의 매개변수와 반환값을 나타내는 역할을 한다.
Any는 제약이 없는 임의의 자료형을 의미하며, Sequence는 시퀀스형을 의미한다. 시퀀스형에는 리스트형, 바이트 배열형, 문자열형, 튜플형, 바이트열형이 있다. 따라서 두 자료형을 사용하여 max_of 함수는 다음과 같이 정의된다.

  • 건네받은 매개변수 a의 자료형은 Sequence 자료형이라고 주석
  • 반환하는 것은 임의의 자료형인 Any 자로형이라고 주석

cf) 모듈 재사용

  • 스크립트 프로그램이 직접 실행될 때 변수 __name__은 ‘__main__’ 이다.
  • 스크립트 프로그램이 임포트될 때 변수 __name__는 원래의 모듈 이름이다.

모든 것을 객체로 다루는 파이썬에서 모듈도 당연히 객체이다. 모듈은 프로그램이 처음 임포트되는 시점에서 그 모듈 객체가 생성되면서 초기화되는 구조이다. 따라서 위에 구현한 max_of 함수가 다른 스크립트 프로그램에서 임포트되었다면 if문이 거짓이되어 실행되지 않는다.

배열의 원솟값을 난수로 결정하기

import random
from max import max_of ## 위에서 작성한 max.py 모듈에서 max_of 함수 가져오기

num = int(input("난수 갯수: "))
up = int(input("난수 최댓값"))
lo = int(input("난수 최솟값"))

list_a =[None] * num

for i in range(num):
    list_a[i] = random.randint(lo,up)

print(f"최댓값 = {max_of(list_a)}")

튜플, 문자열, 문자열 리스트의 최댓값 구하기

import random
from max import max_of

# max_of 매개인자를 Sequence 자료형을 받고 반환형이 Any이기 때문
t = (4,7,5.6,2,3.14,1)
s = 'string'
a = ['dts','aac','flac']

print(f"{t}의 최댓값 = {max_of(t)}")
print(f"{s}의 최댓값 = {max_of(s)}")
print(f"{a}의 최댓값 = {max_of(a)}")

위와 같이 max를 구하는 함수를 직접 구현했는데 사실 리스트, 튜플, 문자열 등의 최댓값, 최솟값은 표준 라이브러리인 max(), min() 함수로도 구할 수 있다.

2. 따로따로 생성한 리스트, 튜플의 동일성 판단하기


따로따로 생성한 리스트에서 모든 원소의 값이 같아도 실체는 각각 다르다.

list1 = [1,2,3,4]
list2 = [1,2,3,4]
print(list1 is list2) # False

동일성이 같은지 연산자 is로 판단하는데 결과는 Flase이다. 튜플도 마찬가지이다. 같은 리스트를 생성한 것처럼 보이지는 이는 리터럴(고정된값)이 아니기 때문이다.

list1=[1,2,3,4]
list2=list1
print(list1 is list2) # True
list1[2]=9
print(list1) # [1,2,9,4]
print(list2) # [1,2,9,4]

앞서 말했듯이 파이썬에서 대입에서 복사되는 것은 값이 아니라 참조하는 곳이다. 따라서, list2는 리스트를 복사한 것이 아니고 list1(참조하는 곳의 리스트)을 참조한다. 즉, list2와 list1은 같은 실체(리스트)를 참조하는 것이다. 따라서 한쪽에서 원소값을 수정하면 list1,list2 모두 바뀌는 것이다.

3. 리스트, 튜플 스캔


enumerate() 함수는 인덱스와 원소를 짝지어 튜플로 꺼내는 내장 함수이다. 리스트로 예시를 보이겠으나 튜플로 하길 원한다면 그저 x = [] 를 x = () 로 바꾸면 된다.

x = ['John','James','Peter','Potter']

for index, value in enumerate(x):
    print(f"x[{index}] = {value}")

print()
for index, value in enumerate(x,1): # 인덱스값을 1부터 시작
    print(f"x[{index}] = {value}")

cf) 이터러블
문자열, 리스트, 튜플, 집합, 딕셔너리 등의 자료형 객체는 모두 이터러블(반복가능)하다는 공통점이 있다. 이터러블 객체는 원소를 하나씩 거내는 구조이며, 이터러블 객체를 내장 함수인 iter()의 인수로 전달하면 그 객체에 대한 이터레이터(반복자)를 반환한다. 이터레이터는 데이터의 나열을 표현하는 객체이다. next() 함수에 이터레이터를 전달하면 원소를 순차적으로 꺼낼 수 있다. for의 경우는 next()를 이용해 알아서 꺼내준다.

4. 배열 원소를 역순으로 정렬하기


# 직접 구현하기
from typing import Any, MutableSequence

def reverse_Arr(a:MutableSequence) -> None :
    for i in range(len(a)//2):
        a[i], a[len(a)-1-i] = a[len(a)-1-i],a[i]

if __name__ == '__main__':
    n = int(input("원소의 수: "))
    list_a = [None] * n
    for i in range(n):
        list_a[i] = int(input("원소값 : "))
    
    print(list_a)
    reverse_Arr(list_a)
    print(list_a)

# 내장 함수 사용하기
n = int(input("원소의 수: "))
list_a = [None] * n
for i in range(n):
    list_a[i] = int(input("원소값 : "))

print(list_a)
y= list(reversed(list_a))
print (y)

reversed() 함수는 이터레이터(반복자)를 반환하므로 list() 함수에 인자로 넣어서 새롭게 리스트를 생성하거나 for문을 사용해야 한다.

5. 기수 변환하기(n진수 구하기)


10진수를 n진수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에 몫을 반복해서 나눠야 한다. 몫이 0이 될 때까지 반복하고 나머지를 역순으로 늘어놓으면 기수로 변환한 수가 된다.

# 10 진수 정숫값을 입력받아 2~ 36진수로 변환하여 출력하기
# module.py
def card_conv(x:int, y:int) ->str:
    d =''
    dchar ='0123456789ABCDEFFGHIJKLMNOPQRSTUVWXYZ'
    while x>0:
        d += dchar[x%y]
        x //=y
    return d[::-1]

# main.py
from test import card_conv

if __name__ =='__main__':
    while True:
        a = int(input("10진수 : "))
        if a>0 :
            break
    while True:
        b = int(input("진수 변환 : "))
        if 2<= b <= 36:
            break
    print(card_conv(a,b))


6. 함수 사이에 인수 주고받기


C언어를 기준으로 보면, 함수(n) 이라고 했을 때 매개변수 n으로 실제 인수의 값이 복사된다. 하지만 파이썬에서는 매개변수에 실제 인수가 대입된다. 즉, 실제 인수가 참조하는 곳을 매개변수 n 또한 그곳을 참조하게 되는 것이다.

def sum_ex(n):
    s = 0
    while n>0:
        s+=n
        n-=1
    return s

x = int(input("x 값 입력:"))
printf(f"1부터 {x}까지의 정수 합 : {sum_ex(x)}")

위에서 설명한 내용으로는 함수 인자는 실제 인수가 대입된다고 했다. 그런데 매개변수 n값을 함수 안에서 변경했는데도 실제 인수 x의 값이 변경되지 않는 것은 int가 이뮤터블 타입이기 때문이다. 변수 n은 값이 업데이트되는 시점에 다른 객체를 참조하게 된다. 변수 n은 함수가 종료할 때 int형 객체 0을 참조하게 되는 것이다.
함수의 실행 시작 시점에서 매개변수는 실제 인수와 같은 객체를 참조한다. 함수에서 매개변수의 값을 변경하면 인수의 형(type)에 따라 아래와 같이 구분한다.

  • 인수가 이뮤터블일 때 : 함수 안에서 매개변수의 값을 변경하면 다른 객체를 생성하고 그 객체에 대한 참조로 업데이트된다. 따라서 매개변수의 값을 변경해도 호출하는 쪽의 실제 인수에는 영향을 주지 않는다.
  • 인수가 뮤터블일 때 : 함수 안에서 매개변수의 값을 변경하면 객체 자체를 업데이트 한다. 따라서 매개변수의 값을 변경하면 호출하는 쪽의 실제 인수의 값도 변경된다.

7. 소수 나열하기


1000 이하의 소수 나열하기
방법1 (효율적이지 못한 코딩)

counter = 0 # 나눗셈 횟수 카운트
for i in range(2,1000+1):
    for j in range(2,i):
        counter+=1
        if i%j==0:
            break
    else :
        print(i, end=" ")
print()
print(f"counter : {counter}") # 78022


방법2 : 방법1을 알고리즘을 개선했지만 아직 부족한 코딩
n이 2와 3으로 나누어 떨어지지 않는다면 2 * 2인 4와 2 * 3인 6으로 나누어 떨어지지 않는다. => 소수는 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다.

counter = 0 # 나눗셈 횟수 카운트
# 짝수는 소수가 아니므로 전체 개수의 반으로 모든 소수를 배열에 넣을 수 있음
arr = [None]* 500 # 소수 리스트
i=0 # 찾은 소수 갯수
arr[i] = 2
i+=1
for n in range(3,1000+1,2): # 2를 제외한 짝수는 소수가 아님
    for k in range(1,i):
        counter+=1
        if n%arr[k]==0:
            break
    else :
        arr[i]=n
        i+=1
for j in range(i):
    print(arr[j],end=" ")
print ()
print(f"counter : {counter}") # 14622

4 이상의 짝수는 2로 나누어 떨어지므로 소수가 아니기 때문에 첫 for문에서 공차를 2로 주어 짝수를 제외시킨다. k는 0부터가 아니라 1부터 1씩 증가해야한다. 왜냐하면 판단 대상인 n이 홀수이므로 arr[0]에 저장된 2는 나눌 필요가 없기 때문이다. 방법 1과 다른 점을 통해서 다음과 같은 사실을 알 수 있다.

  • 같은 결과를 얻을 수 있는 알고리즘은 여러 개 일 수 있다.
  • 빠른 알고리즘은 많은 메모리를 요구한다.


방법3 : 최종적으로 개선한 알고리즘
예를 들어 넓이가 100인 직사각형의 가로, 세로 변의 길이를 생각해보자. 5 * 20과 20 * 5는 가로, 세로 변의 길이는 다르지만 같은 직사각형이다. 소수를 구할 때도 마찬가지이다. 만약 100이 5로 나누어 떨어지지 않는다면 20으로도 나누어 떨어지지 않는다. 그렇다면 소수n은 n제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

counter = 0 # 나눗셈,곱셈 횟수 카운트
# 짝수는 소수가 아니므로 전체 개수의 반으로 모든 소수를 배열에 넣을 수 있음
arr = [None]* 500 # 소수 리스트
i=0 # 찾은 소수 갯수
arr[i] = 2
i+=1
for n in range(3,1000,2):
    for k in range(1,i):
        counter +=1 # 곱셈 카운트
        # 예시로 a,b,c 모두 소수이고 c < a < b라고하자
        # 해당 숫자를 소수로 나눴을 때 소수가 아닌 경우 반드시 (a) * (b)에 해당할 것이다.
        # (a) * (c)의 경우 이전 과정에서(c) * (a) 이렇게 먼저 구해지고 해당 n의 과정은 break됬을 것이다.
        # 따라서 소수 구하는 과정이 arr[k] * (arr[k]보다 큰 소수)로 진행될 것이므로
        # arr[k] * arr[k] > n 이면 n은 arr[k]보다 큰 소수로 나눌 수 없는 것이기 때문에 소수이다.
        # 좀 쉽게 말하자면 1*2는 앞에서 구했으므로 2*1은 배제하고 2보다 큰 수를 곱해서 구하겠다는 뜻
        if arr[k] * arr[k] > n:
            arr[i] = n
            i+=1
            break
        counter +=1 # 나눗셈 카운트
        if n% arr[k] == 0:
            break
    else :
        arr[i] = n
        i+=1
        
for j in range(i):
    print(arr[j],end=" ")
print ()
print(f"counter : {counter}") # 3774


8. 리스트의 원소와 복사


변수는 객체와 연결된 이름에 불과하다. 따라서 리스트, 듀플의 원소 자료형을 미리 정할 필요가 없다.

x = [1,2,3.14,[32,55],'abc']
for i in range(len(x)):
print(f"x[{i}] = {x[i]}")


얕은 복사

리스트를 복사할 때 사용하는 copy() 함수는 주의해서 사용해야 한다. 리스트를 복사한 후 원솟값을 변경하면 복사된 원솟값까지 변경될 수 있기 때문이다. 객체가 갖는 멤버의 값을 새로운 객체로 복사할 때 객체가 참조 자료형의 멤버를 포함할 경우를 얕은 복사라고 하며, 참조값만 복사하는 방식이다.

x = [[1,2,3],[4,5,6]]
y = x.copy()
x[0][1] = 9
print(x) # [[1,9,3][4,5,6]]
print(y) # [[1,9,3][4,5,6]]

참조값만 복사되었다는 말은 y의 y[0],y[1]에 x[0],x[1]이 참조하는 값, 즉 리스트 안의 원소가 참조하는 곳 까지만 복사되었다는 뜻이다. 하지만 x[0]은 리스트 객체를 참조하고 x[0][0~2]는 int형 객체를 참조한다. 따라서 얕은 복사는 리스트 객체만 참조하고 있기 때문에 리스트 객체가 참조하고 있는 int형 객체를 다른 객체로 변경하게 되면 x,y는 같이 참조하는 곳이 달라지게 되는 것이다.

x = [1,2,3]
y = x.copy()
x[1] = 9
print(x) # [1,9,3]
print(y) # [1,2,3]

위의 내용을 이해했다면 이해하기 쉬울 것이다. 리스트 안의 원소가 참조하는 곳까지 복사되었으므로 위의 경우에서는 서로 영향을 주지 않는다.
참고로 x,y의 id값을 검사해보면 서로 다르다. 따라서 x.copy()는 x와 같은 곳을 참조하는 다른 객체를 만든 것이고 y는 그 객체를 참조하는 것으로 보면 된다.

깊은 복사

깊은 복사는 참조값 뿐만 아니라 참조하는 객체 자체를 복사한다. 즉, 객체가 갖는 모든 멤버를 복사하므로 전체 복사라고도 한다.

import copy
x = [[1,2,3],[4,5,6]]
y = copy.deepcopy(x)
x[0][1] = 9
print(x) # [[1,9,3][4,5,6]]
print(y) # [[1,2,3][4,5,6]]

위에서 설명한 얕은 복사의 예시에서는 x[0],x[1]이 참조하는 값만 복사되었다. 하지만 깊은 복사에서는 x[0],x[1]이 참조하는 값과 참조하는 객체 자체(x[0][0~2], x[1][0~2])까지 복사한다. 즉, x[0][0~2]가 참조하는 값까지 복사된다는 뜻이다. 따라서 참조하는 곳을 업데이트해도 서로 영향을 주지 않는다.
deepcopy(x)는 x와 같은 곳을 참조하는 다른 객체를 만든 것이고 y는 그 객체를 참조하는 꼴이다.


본 포스팅은 ‘자료구조와 함께 배우는 알고리즘 입문’을 읽고 공부한 내용을 바탕으로 작성하였습니다.


© 2021. By Backtony