EverGiver

02-2 배열이란? 본문

Python/알고리즘

02-2 배열이란?

친절한개발초보자 2022. 1. 5. 13:34
728x90
배열 원소의 최댓값 구하기
// a의 원소가 3개일 때
maximum = a[0]
if a[1] > maximum: maximum = a[1]
if a[2] > maximum: maximum = a[2]

// a의 원소가 4개일 때
maximum = a[0]
if a[1] > maximum: maximum = a[1]
if a[2] > maximum: maximum = a[2]
if a[3] > maximum: maximum = a[3]

- 배열 a의 원소 중에서 최댓값을 구하는 max_of( ) 함수 정의

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

- 배열 원소를 하나씩 차례로 주목하여 살펴보는 방식을 알고리즘 용어로 스캔(scan)이라고 한다.
  (스캔은 주사 또는 트래버스(traverse)라고도 한다.)

 

배열 원소의 최댓값을 구하는 함수 구현하기
from typing import Any, Sequence

def max_of(a: Sequence) -> Any:
    """시퀀스형 a 요소의 최댓값을 반환"""
    maximum = a[0]
    for i in range(1, len(a)):
         if a[i] > maximum: 
            maximum = a[i]
    return maximum

if __name__ == '__main__':
    print('배열의 최댓값을 구합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num    # 원소 수가 num인 리스트를 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]를 입력하세요.: '))

    print(f'최댓값은 {max_of(x)}입니다.')
from typing import Any, Sequence
  • Any는 제약이 없는 임의의 자료형을 의미
  • Sequence는 시퀀스형을 의미
    - 무언가의 조합으로 이루어진 자료형으로 생각하자.
    - 리스트 형, 바이트 배열 형, 문자열 형, 튜플 형, 바이트열 형이 있다.

 

주석과 자료형 힌트
def max_of(a: Sequence) -> Any:
  • 건네받는 매개변수 a의 자료형은 Sequence입니다.
  • 변환하는 것은 임의의 자료형인 Any입니다.
  • max_of( )함수의 특성
    - 함수 안에서 배열 a의 원솟값을 변경하지 않는다.
    - 호출하는 쪽이 넘겨주는 실제 인수의 자료형은 뮤터블인 리스트, 이뮤터블인 튜플/문자열 등 시퀸스 자료형이라면 무엇이든 상관없다.
    - 인수의 원소를 비교 연산자 >로 값을 비교할 수 있다면 다른 형(int형, float형)이 섞여 있어도 된다.
    - 최댓값의 원소가 int형 원소이며 int형 값을 반환하고, float형 원소이면 float형 값을 반환한다.
  • max_of( ) 함수 안에서 매개변수에 대한 함수 어노테이션(annotation)은 시퀸스형이 아닌 뮤터블 시퀸스라고 명시한다.

    cf) 뮤터블(mutable) vs 이뮤터블(immutable)
        - 뮤터블(mutable)
          ▷ 변경이 가능한 객체
          ▷ 생성 후 자유롭게 값을 변경, 추가, 삭제 등이 가능
          ▷ 참조에 의한 호출 (call by reference)
          ▷ 변수의 값을 변경하면 객체 자체를 업데이트한다. 
          ▷ 리스트, 세트, 딕셔너리 등
        - 이뮤터블(immutable)
          ▷ 변경이 불가능한 객체
          ▷ 생성 후 값 변경, 추가 삭제 등이 불가능
          ▷ 값에 의한 호출 (call by value)
          ▷ 변수의 값을 변경하면 다른 객체를 생성하고 그 객체에 대한 참조로 업데이트된다.
          ▷ 숫자, string, 튜플 등

    cf) 함수 어노테이션(annotation)
        - 파이썬에서는 자료형 선언 없이 변수나 함수를 자유롭게 사용할 수 있지만. 명시적으로 해석하기 어려운 경우가 있다.
        - 그래서 등장한 기능이 어노테이션(annotation, 주석 달기)입니다.
        - 가장 큰 특징은 강제성이 없다. 즉, 말 그대로 주석 달기일 뿐이며 코드 자체에는 어떠한 영향도 미치지 않는다.
        - 함수 어노테이션은 함수의 매개변수와 반환 값을 나타내는 역할을 한다.

 

재사용할 수 있는 모듈 작성하기
  • 하나의 스크립트 프로그램을 모듈(module)이라고 한다.
  • 확장자(.py)를 포함하지 않는 파일의 이름 자체를 모듈 이름으로 사용한다.
    if __name__ == '__main__':​
    - 스크립트 프로그램이 직접 실행될 때 변수 __name__은 '__main__'이다.
    - 스크립트 프로그램이 임포트 될 때 변수 __name__은 원래의 모듈 이름이다.
  • 모듈도 당연히 객체이다.
  • 모듈은 프로그램이 처음 임포트되는 시점에 그 모듈 객체가 생성되면서 초기화되는 구조이다.

cf) 모듈 객체에는 __name__ 이외에도 __loader__, __package__, __spec__, __path__, __file__ 등이 있다.

 

모듈 테스트하기
  • 입력받을 때 원소 수를 결정하기
    from max import max_of

print('배열의 최댓값을 구합니다.')
print('주의: "End"를 입력하면 종료합니다.')

number = 0
x = []                  # 빈 리스트

while True:
    s = input(f'x[{number}]를 입력하세요.: ')
    if s == 'End':
        break
    x.append(int(s))    # 배열의 끝에 추가
    number += 1

print(f'{number}개를 입력했습니다.')
print(f'최댓값은 {max_of(x)}입니다.')​
    - 모듈 max로 정의된 max_of( ) 함수를 사용할 수 있도록 임포트 했다.
  • 배열의 원솟값을 난수로 결정
    import random
from max import max_of

print('난수의 최댓값을 구합니다.')
num = int(input('난수의 개수를 입력하세요.: '))
lo = int(input('난수의 최솟값을 입력하세요.: '))
hi = int(input('난수의 최댓값을 입력하세요.: '))
x = [None] * num        # 원소 수 num인 리스트를 생성

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

print(f'{(x)}')
print(f'이 가운데 최댓값은 {max_of(x)}입니다.')​
  • 튜플, 문자열, 문자열 리스트의 최댓값 구하기
    from max import max_of

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)}입니다.')​

    cf) 리스트와 튜플
        - 따로따로 생성한 리스트, 튜플의 동일성 판단하기
          ▷ 따로따로 생성한 리스트에서 모든 원소의 값이 같아도 실체는 각각 다르다.
    list1 = [1, 2, 3, 4, 5]
list2 = [1, 2, 3, 4, 5]
list1 is list2 	# False​
    → 리더럴(고정된 값)이 아니기 때문이다.

        - 리스트, 튜플의 대입
    list1 = [1, 2, 3, 4, 5] 
list2 = list1 
list1 is list2	#True 

list[2] = 9 
list1 	# [1, 2, 9, 4, 5] 
list2 	# [1, 2, 9, 4, 5]​
    → 리스트를 2개 선언하여 서로 대입해도 원소 자체는 복사되지 않는다.
        (대입에서 복사되는 것은 값이 아니라 참조하는 곳이다.)

        - 리스트 스캔
          ▷ 원소 수를 len() 함수로 미리 알아내서 0에서 원소 수 - 1까지 반복
          ▷ 인덱스와 원소를 짝지어 enumerate( ) 함수로 반복
              → enumerate( ) 함수는 인덱스와 원소를 짝지어 튜플로 꺼내는 내장 함수이다.
              → enumerate(x, 1) : 인덱스를 1부터 카운트
          ▷ 인덱스 값을 사용하지 않고 in을 사용해서 원소를 처음부터 순서대로 꺼낸다.

        - 튜플의 스캔
          ▷ 리스트로 작성한 x = [ ]를 x = ( )로 수정하는 것만으로 스캔할 수 있다.

        - 이터러블 (iterable)
          ▷ 문자열, 리스트, 튜플, 집합, 딕셔너리 등의 자료형 객체는 모두 이터러블(반복 가능)하다는 공통점이 있다.
          ▷ 이터러블 객체는 원소를 하나씩 꺼내는 구조이며, 이터러블 객체를 내장 함수인 iter( )의 인수로 전달하면 그 객체에 대한 이터레이터(반복자)를 반환합니다.
              (이터레이터는 데이터의 나열을 표현하는 객체이다.)
          ▷ 이터레이터의 __next__ 함수를 호출하거나 내장 함수인 next( ) 함수에 이터레이터를 전달하면 원소를 순차적으로 꺼낼 수 있다. (더 이상 없는 경우 StopIteration으로 예외 발생을 시킨다.)

 

배열 원소를 역순으로 정렬하기
from typing import Any, MutableSequence

def reverse_array(a: MutableSequence) -> None:
    """뮤터블 시퀀스형 a의 원소를 역순으로 정렬"""
    n = len(a)
    for i in range(n // 2):
         a[i], a[n - i - 1] = a[n - i - 1], a[i]

if __name__ == '__main__':
    print('배열 원소를 역순으로 정렬합니다.')
    nx = int(input('원소 수를 입력하세요.: '))
    x = [None] * nx   # 원소 수가 nx인 리스트를 생성

    for i in range(nx):
        x[i] = int(input(f'x[{i}] : '))

    reverse_array(x)  # x를 역순으로 정렬

    print('배열 원소를 역순으로 정렬했습니다.')
    for i in range(nx):
        print(f'x[{i}] = {x[i]}')
  • 리스트를 역순으로 정렬
    - list형의 reverse( ) 함수를 사용할 수 있다.
    x.reverse( )	# 리스트 x의 원ㅅ로를 역순으로 정렬
  • 역순으로 정렬한 리스트 생성
    - reversed( ) 함수를 호출하는 reversed(x)는 x의 원소를 역순으로 정렬하는 이터러블 객체를 생성한다.
    y = list(reversed(x))	# 리스트 x의 원소를 역순으로 정렬하여 y에 대입​
기수 변환하기 (n진수 구하기)

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

  • 기수 살펴보기
    1. 10진수
        ▷ 1 자릿수 : 0~9까지의 수를 나타낸다.
        ▷ 2 자릿수 : 10~99까지의 수를 나타낸다.
        ▷ 3 자릿수 : 100~999까지의 수를 나타낸다.
    2. 8진수
        ▷ 1 자릿수 : 0~7까지의 수를 나타낸다.
        ▷ 2 자릿수 : 10~77까지의 수를 나타낸다.
        ▷ 3 자릿수 : 100~777까지의 수를 나타낸다.
    3. 16진수
        ▷ 0 1 2 3 4 5 6 7 8 9 A B C D E F
    def card_conv(x: int, r: int) -> str:
    """정수 x를 r 진수로 변환한 뒤 그 수를 나타내는 문자열을 반환"""

    d = ''  # 변환 뒤 문자열
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    while x > 0:
        d += dchar [x % r]  # 해당하는 문자를 꺼내 결합
        x //= r

    return d[::-1]          # 역순으로 반환

if __name__ == '__main__':
    print('10진수를 n진수로 변환합니다.')

    while True:
        while True :  # 음이 아닌 정수를 입력받음
            no = int(input('변환할 값으로 음이 아닌 정수를 입력하세요.: '))
            if no > 0:
                break

        while True :  # 2~36진수의 정수값을 입력받음
            cd = int(input('어떤 진수로 변환할까요?: '))
            if 2 <=  cd <=  36:
                break

        print(f'{cd}진수로는 {card_conv(no, cd)}입니다.')

        retry = input( "한 번 더 변환할까요?(Y ... 예/N ... 아니오): ")
        if retry in {'N', 'n'}:
           break​

    def card_conv(x: int, r: int) -> str:
    """정수 x를 r 진수로 변환한 뒤 그 수를 나타내는 문자열을 반환"""

    d =  ''  # 변환 뒤 문자열
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    n = len(str(x))  # 변환하기 전의 자릿수

    print(f'{r:2} | {x:{n}d}')
    while x > 0:
        print('   +' + (n + 2) * '-')
        if x // r:
            print(f'{r:2} | {x // r:{n}d} … {x % r}')
        else:
            print(f'     {x // r:{n}d} … {x % r}')
        d += dchar [x % r]  # 해당하는 문자를 꺼내 결합
        x //= r

    return d[::-1]  # 역순으로 반환​

cf) 함수 사이에 인수 주고받기

def sum_1ton(n):
    """1부터 n까지 정수의 합"""
    s = 0
    while n > 0:
        s += n
        n -= 1
    return s

x = int(input('x의 값을 입력하세요.: '))
print(f'1부터 {x}까지 합은 {sum_1ton(x)}입니다.')
  • 매개변수 n으로 실제 인수 x의 값이 복사(copy) 되었습니다.
    → 절대 이렇게 생각하면 안 된다!!!!
  • 파이썬에서는 매개변수에 실제 인수가 대입된다.
  • (함수 실행 시작 시점) 원래 대입에서 복사되는 것은 값이 아니라 참조하는 곳이므로 n과 x가 참조하는 곳은 같다.
  • 매개변수 n값을 sum_1ton( ) 함수 안에서 변경했는데도 실제 인수 x의 값이 변경되지 않는 것은 int가 이뮤터블 타입이기 때문이다.
  • 변수 n은 값이 업데이트되는 시점에 다른 객체를 참조하게 된다. 
    (함수를 종료할 때 n이 참조하는 곳은 정소 0이 된다.)
  • 파이썬에서 인수 전달은 실제 인수인 객체에 대한 참조를 값으로 전달하여 매개변수에 대입되는 방식이다.
  • 파이썬에서는 값에 의한 호출(call by value)과 참조에 의한 호출(call by reference)의 중간적인 방식으로 값을 전달한다.
    (파이썬 공식 문서에서는 객체 참조에 의한 전달(call by object reference)이라는 용어를 사용하여 설명한다.)
  • 함수 사이의 인수 전달을 정리
    - 함수의 실행 시작 시점에서 매개변수는 실제 인수와 같은 객체를 참조한다.
    - 함수에서 매개변수의 값을 변경하면 인수의 형(type)에 따라 구분된다.
      1. 인수가 이뮤터블인 경우
          : 함수 안에서 매개변수의 값을 변경하면 다른 객체를 생성하고 그 객체에 대한 참조로 업데이트된다. 따라서 매개변수의 값을 변경해도 호출하는 쪽의 실제 인수에는 영향을 주지 않는다.
      2. 인수가 뮤터블인 경우
          : 함수 안에서 매개변수의 값을 변경하면 객체 자체를 업데이트한다. 따라서 매개변수의 값을 변경하면 호출하는 쪽의 실제 인수는 값이 변경된다.

소수 나열하기

어떤 정수 이하의 소수(prime number)를 모두 나열하는 알고리즘
- 소수
  : 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수이다.
- 조건
  ▷ 2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않는다.

- 합성수(composite number)
  : 나누어 떨어지는 정수가 하나 이상 존재하는 경우

counter = 0  # 나눗셈 횟수

for n in range(2, 1001):
    for i in range(2, n):
        counter += 1
        if n % i == 0 :     # 나누어 떨어지면 소수가 아님
            break           # 반복은 더 이상 불필요하여 중단
    else:                   # 끝까지 나누어 떨어지지 않으면 다음을 수행
        print(n)
print(f'나눗셈을 실행한 횟수: {counter}')

- 정리
  ▷ n이 소수일 때
      : for 문은 마지막까지 실행된다. → else 문을 실행하여 n값을 출력
  ▷ n이 합성수일 때
      : for 문은 중단된다.
- 나눗셈 횟수를 줄이는 프로그램 
  ▷ 2부터 n - 1까지 어떤 소수로도 나누어 떨어지지 않는다.

  • 알고리즘 개선하기 1
    - 소수를 구하는 과정에서 지금까지 구한 소수를 배열 prime의 원소로 저장한다.
      (n이 소수인지 판단할 때 배열 prime에 저장한 소수로 나눗셈을 하면 된다.)
    counter = 0           # 나눗셈 횟수
ptr = 0               # 이미 찾은 소수의 개수
prime = [None] * 500  # 소수를 저장하는 배열

prime[ptr] = 2        # 2는 소수이므로 초깃값으로 지정
ptr += 1

for n in range(3, 1001, 2):  # 홀수만을 대상으로 설정
    for i in range(1, ptr):  # 이미 찾은 소수로 나눔
        counter += 1
        if n % prime[i] == 0:  # 나누어 떨어지면 소수가 아님
            break              # 반복 중단
    else:                      # 끝까지 나누어 떨어지지 않았다면
        prime[ptr] = n         # 소수로 배열에 등록
        ptr += 1

for i in range(ptr):  # ptr의 소수를 출력
    print(prime[i])
print(f'나눗셈을 실행한 횟수: {counter}')​

    cf) 1. 같은 결과(해답)를 얻을 수 있는 알고리즘은 여러 개일 수 있다.
        2. 빠른 알고리즘은 많은 메모리를 요구한다.
  • 알고리즘 개선하기 2
    - n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않으면 소수라고 할 수 있다.
    counter = 0           # 곱셈과 나눗셈을 합한 횟수
ptr = 0               # 이미 찾은 소수의 개수
prime = [None] * 500  # 소수를 저장하는 배열

prime[ptr] = 2  # 2는 소수
ptr += 1

prime[ptr] = 3  # 3은 소수
ptr += 1

/*
prime = [2, 3]   
*/

for n in range(5, 1001, 2):    # 홀수만을 대상으로 설정
    i = 1
    while prime[i] * prime[i] <=  n:
        counter += 2
        if n % prime[i] == 0:  # 나누어 떨어지므로 소수가 아님
            break              # 반복 중단
        i += 1
    else:                      # 끝까지 나누어 떨어지지 않았다면
        prime[ptr] = n         # 소수로 배열에 등록
        ptr += 1
        counter += 1

for i in range(ptr):  # ptr개의 소수를 출력
    print(prime[i])
print(f'곱셈과 나눗셈을 실행한 횟수: {counter}')​

cf) 리스트의 원소 복사
     - 파이썬에서 변수는 객체와 연결된 이름에 불과하다.
       (리스트, 튜플의 원소 자료형을 미리 정할 필요가 없다.)

# 자료형을 정하지 않은 리스트 원소 확인하기

x = [15, 64, 7, 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를 y로 얕은 복사
x[0][1] = 9
x	# [[1, 9, 3], [4, 5, 6]]
y	# [[1, 9, 3], [4, 5, 6]]

     - 얕은 복사 (shallow copy)
       ▷ 객체가 갖는 멤버의 값을 새로운 객체로 복사할 때 객체가 참조 자료형의 멤버를 포함할 경우
       ▷ 리스트 안의 모든 원소가 참조하는 곳까지 복사된다.
           (참조값만 복사하는 방식)
       ▷ 리스트 x가 참조하는 곳이 다르면 y도 달라진다.
     - 깊은 복사 (deep copy)
       ▷ 참조값뿐만 아니라 참조하는 객체 자체를 복사한다.
           (객체가 갖는 모든 멤버(값과 참조 형식 모두)를 복사하므로 전체 복사라고도 한다.)
       ▷ 구성 원소 수준으로 복사하는 방법
       ▷ copy 모듈 안의 deepcopy( ) 함수로 수행된다.

import copy		# deepcopy를 사용하기 위한 copy 모듈을 임포트
x = [[1, 2, 3], [4, 5, 6]]
y = copy.deepcopy(x)	#x를 y로 깊은 복사
x[0][1] = 9
x	# [[1, 9, 3], [4, 5, 6]]
y	# [[1, 2, 3], [4, 5, 6]]

     - 리스트의 원소뿐만 아니라 구성 원소(원소의 원소)도 복사된다.

728x90
저작자표시

'Python > 알고리즘' 카테고리의 다른 글

02-1 자료구조와 배열  (0) 2022.01.03
01-2 반복하는 알고리즘  (0) 2021.10.01
01-1 알고리즘이란?  (0) 2021.10.01
'Python/알고리즘' Related Articles more
Comments