[구버전] [Python] 01. 자료 구조와 배열

이 포스트는 [Do it! 자료 구조와 함께 배우는 알고리즘 입문 - 파이썬 편]을 보며 제가 알아야할 내용들을 정리한 포스트입니다. 개인 공부용이므로 자세한 설명이나 정보 설명을 위한 포스트는 아님을 미리 말씀드립니다.

 

📌 자료구조와 배열

📚 리스트의 기초

• 리스트의 원소를 변경할 수 있는 뮤터블(mutable) list 형 객체
• 파이썬 내장 함수인 list( )를 사용하여 다양한 자료형의 원소를 가진 객체 생성 가능
• None을 통해 원솟값을 정하지 않은채로 개수 사용 가능

 

📚 튜플의 기초

• 튜플은 원소에 순서를 매겨 결합한 것으로 원소를 변경할 수 없는 이뮤터블(imutable) 자료형
• tuple( ) 을 사용하면 문자열이나 리스트 등 여러가지 자료형 객체를 원소로 하는 튜플 생성 가능

 

📚 뮤터블과 이뮤터블의 대입

• 뮤터블 : 값을 변경할 수 있는 특성, ex) 리스트, 딕셔너리 집합
• 이뮤터블 : 값을 변경할 수 없는 특성, ex) 수, 문자열 튜플
• int형 정수형 객체 12의 값 자체를 변경하는 것은 불가능하므로 다른 정수형 객체를 가져와야함
• 어떤 자료형의 객체이든 상관없이 변수에 대입할 수 있음

변수에 어떤 값을 대입하면 값이 아니라 식별 번호가 바뀐다.

 

여러 변수에 여러 값을 한꺼번에 대입할 수도 있음

• 두 대입식이 동시에 이루어지므로 x는 업데이트 전의 값인 6으로 실행
• 누적 변수 : 변수에 특정 값을 더한 결과값을 다시 대입하여 업데이트한 변수
• ex) n++, n+= 1

 

📚 등가성과 동일성

• 등가성(equality) : ==. 좌변과 우변의 값이 같은지 비교
• 동일성(identity) : is, 값은 물론 객체의 식별 번호까지 같은지 비교

 

📌 배열이란?

• 배열의 원소를 하나씩 차례로 주목하여 살펴보는 방식을 스캔(트래버스, 주사)라고 합니다.

 

📚 배열의 최댓값 구하는 함수 구현하기

# max.py

from typing import Any, Sequence

def max_of(a: Sequence) -> Any:
    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

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

    print(f'최댓값은 {max_of(x)}입니다.')

• Any
  • 제약이 없는 임의의 자료형
• Sequnce
  • 시퀀스형 : 리스트(list)형, 바이트 배열(bytearry)형, 문자열(str)형, 튜플(tuple)형, 바이트열(bytes)형
• 함수 어노테이션
  • 어노테이션(annotaion, 주석달기)
  • 강제성은 없으나 명시적으로 자료형을 표시
  • 함수 어노테이션은 함수의 매개변수와 반환값을 나타내는 역할
  • max_of( ) 함수 내에서 매개변수에 대한 함수 어노테이션은 시퀀스형이 아닌 뮤터블 시퀀스라고 명시
• 모듈
  • 하나의 스크립트 프로그램
  • 확장자(.py)를 포함하지 않는 파일의 이름 자체를 모듈 이름으로 사용
  • name 은 모듈 이름을 나타내는 변수
  • 모듈은 프로그램이 처음 임포트되는 시점에 그 모듈 객체가 생성되면서 초기화되는 구조
  • if 문은 max.py를 직접 시작한 경우에만 참이되어 실행됨
• from max import max_of
  • 모듈 max로 정의된 파일을 불러옴
  • main.py에서 실행된 것이 아니라면 if 문 이후로는 실행이 되지 않음
• 리스트 스캔
  • enumeate( ) 함수 : 이용하면 인덱스와 원소를 짝지어 튜플로 꺼내는 내장 함수
  • 리스트가 이터러블 객체(순차 반복 객체)이기 때문에 인덱스 값을 지정하지 않아고 배열에서 직접 꺼내도 됨
• 이터러블
  • 문자열, 리스트, 튜플, 집합, 딕셔너리 등의 자료형 객체는 모두 이터러블(반복 가능)하다는 공통점
  • 이터러블 객체는 원소를 하나씩 꺼내는 구조
  • 이터러블 객체를 내장 함수인 iter( )의 인수로 전달하면 그 객체에 대한 이터레이터(iterator)를 반환
  • 이터레이터의 next 함수를 호출하거나 내장 함수인 next( ) 함수에 이터레이터를 전달하면 원소를 꺼낼 수 있음
• 리스트를 역순으로 정렬 : reverse()

 

📚 진수변환

def card_conv(x:int, r:int) -> str:
    d = ''
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    while x > 0:
        d += dchar[x % r]
        x //= r

    return  d[::-1]

if __name__ == '__main__':
    print('10진수로 변환')

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

        while True:
            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

 

📚 소수 판단하기

1. 나누는 수가 있는 경우 break

   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}') #78022

   • n이 소수일 때 : for 문은 마지막까지 실행
   • n이 합성수일 때 : for 문이 중단
   1. 소수를 판단할 때 배열 prime에 저장한 소수로만 나눗셈을 진행
   2부터 n - 1까지 어떤 정수로도 나누어 떨어지지 않습니다.
   • 빠른 알고리즘은 많은 메모리를 요구합니다.
   1. 제곱근 이용하기
   n의 제곱근 이하의 어떤 소수로도 떨어지지 않으면 소수입니다.
   • 100은 250, 425, 520, 1010, 205, 254, 502입니다. 1010 이후의 연산은 중복이므로 불필요한 연산에 해당합니다.
   • while 문에서는 제곱연산과 나머지 연산 두 가지를 하므로 counter += 2
2. counter = 0 ptr = 0 prime = [None] * 500 prime[ptr] = 2 ptr += 1 prime[ptr] = 3 ptr += 1 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): print(prime[i]) print(f'나눗셈을 실행한 횟수: {counter}') #3774
3. counter = 0 ptr = 0 prime = [None] * 500 prime[ptr] = 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): print(prime[i]) print(f'나눗셈을 실행한 횟수: {counter}') #14622
4. 2부터 n - 1까지 어떤 정수로도 나누어 떨어지지 않습니다.