[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 02. 기본 자료구조와 배열

02. 기본 자료구조와 배열

02-1. 자료구조와 배열

배열 개념 알아보기

#[Do it! 실습 2-1] 학생 5명의 점수를 입력받아 합계와 평균을 출력하기

print('학생 그룹 점수의 합계와 평균을 구합니다.')

score1 = int(input('1번 학생의 점수를 입력하세요.: '))
score2 = int(input('2번 학생의 점수를 입력하세요.: '))
score3 = int(input('3번 학생의 점수를 입력하세요.: '))
score4 = int(input('4번 학생의 점수를 입력하세요.: '))
score5 = int(input('5번 학생의 점수를 입력하세요.: '))

total = 0
total += score1
total += score2
total += score3
total += score4
total += score5

print(f'합계는 {total}점입니다.')
print(f'평균은 {total / 5}점입니다.')

# 실행 결과
학생 그룹 점수의 합계와 평균을 구합니다.
1번 학생의 점수를 입력하세요.: 4
2번 학생의 점수를 입력하세요.: 5
3번 학생의 점수를 입력하세요.: 6
4번 학생의 점수를 입력하세요.: 7
5번 학생의 점수를 입력하세요.: 8
합계는 30점입니다
합계는 6.0점입니다

 

배열 array

배열에는 객체가 저장됨

서로 다른 자료형을 같이 저장 가능

 

원소 element

배열에 저장된 객체 하나하나

 

인덱스 index

각 원소에 부여되는 순서

 

리스트와 튜플 알아보기

배열은 리스트 list와 튜플 tuple로 구현 가능

= 데이터 컨테이너 data container

원소 변경 가능 여부에 따른 차이 존재

 

리스트의 기초

원소를 변경할 수 있는 뮤터블 mutable list형 객체

연산자 [] 안에 원소를 쉼표(,)로 구분해서 표기하여 생성

원소 없이 []만 사용하면 빈 리스트 생성

list04 = list() # [] 빈 리스트
list05 = list('ABC') # ['A', 'B', 'C']
list06 = list([1, 2, 3]) # [1, 2, 3]
list07 = list((1, 2, 3)) # [1, 2, 3]
list08 = list({1, 2, 3}) # [1, 2, 3]
list09 = list(range(7)) # [0, 1, 2, 3, 4, 5, 6]
list10 = list(range(3, 8)) # [3, 4, 5, 6, 7]
list11 = list(range(3, 13, 2)) # [3, 5, 7, 9, 11]
list12 = [None] * 5 # [None, None, None, None, None]

 

튜플의 기초

원소를 변경할 수 없는 이뮤터블 immutable 자료형

원소를 쉼표(,)로 구분하여 나열한 뒤 결합 연산자 ()로 둘러싸는 방식으로 생성

리스트와 마찬가지로 맨 마지막 원소 뒤에 쉼표를 써도 되며, ()만 사용하면 빈 튜플 생성

결합 연산자 ()를 생략 가능

원소가 1개인 경우엔 원소 뒤에 쉼표를 반드시 입력해야 함

tuple01 = () # ()
tuple02 = 1, # (1,) : 원소가 1개라 쉼표 필수! 쉼표가 없으면 튜플이 아니라 단순 변수로 취급됨
tuple03 = (1,) # (1, )
tuple04 = 1, 2, 3 # (1, 2, 3)
tuple05 = 1, 2, 3, # (1, 2, 3)
tuple06 = (1, 2, 3) # (1, 2, 3)
tuple07 = (1, 2, 3, ) # (1, 2, 3)
tuple08 = 'A', 'B', 'C', # ('A', 'B', 'C')

# 튜플이 아닌 하나의 값을 가진 int형 변수
v01 = 1 # 1
v02 = (1) # 1

tuple09 = tuple() # () 빈 튜플
tuple10 = tuple('ABC') # ('A', 'B', 'C') 문자열의 각 문자로부터 원소를 생성
tuple11 = tuple([1, 2, 3]) # (1, 2, 3) 리스트로부터 원소를 생성
tuple12 = tuple({1, 2, 3}) # (1, 2, 3) 집합으로부터 원소를 생성
tuple13 = tuple(range(7)) # (0, 1, 2, 3, 4, 5, 6)
tuple14 = tuple(range(3, 8)) # (3, 4, 5, 6, 7)
tuple15 = tuple(range(3, 13, 2)) # (3, 5, 7, 9, 11)

print(tuple09, tuple10, tuple11, tuple12, tuple13, tuple14, tuple15)

 

리스트와 튜플 풀어내기

좌변에는 여러 개의 변수를 놓고 우변에는 리스트나 튜플을 놓으면 우변의 원소를 좌변의 변수에 한번에 대입 가능

언팩 unpack : 리스트나 튜플의 원솟값들을 풀어 여러 변수에 대입하는 것

 

인덱스로 원소에 접근하기

리스트나 튜플의 원소에 접근할 때는 인덱스 index 사용

 

인덱스식 사용하기

인덱스식

- 인덱스 연산자 [] 안에 정숫값 인덱스를 지정

- 리스트의 특정 원소를 정할 수 있음

 

슬라이스식으로 원소에 접근하기

슬라이스 slice

리스트 또는 튜플의 원소 일부를 연속해서 또는 일정한 간격으로 꺼내 새로운 리스트 또는 튜플을 만드는 것

 

슬라이스식으로 원소 꺼내기

다음처럼 슬라이스식을 나타낼 수 있음

s[i:j] ...s[i]부터 s[j-1]까지 나열합니다
s[i:j:k] ...s[i]부터 s[j-1]까지 k씩 건너뛰며 나열합니다

# 예시
s = [11, 22, 33, 44, 55, 66, 77]
print(s[0:6]) # 리스트 s의 0번째 원소부터 5번째 원소를 출력
# [11, 22, 33, 44, 55, 66]
print(s[0:7]) # 리스트 s의 0번째 원소부터 6번째 원소를 출력
# [11, 22, 33, 44, 55, 66, 77]
print(s[0:7:2]) # 리스트 s의 0번째 원소부터 6번째 원소 중 2씩 건너뛰며 원소를 출력
# [11, 33, 55, 77]
print(s[-4:-2]) # 리스트 s의 뒤에서 4번째 원소부터 뒤에서 2번째 원소를 출력
# [44, 55]
print(s[3:1]) # 리스트 s의 j값(1)이 i값(3)보다 작지만 오류가 나지 않음
# []

 

i, j, k의 값 중 1개의 값 이상을 생략하는 패턴 목록

패턴	설명	실행 예	실행 결과
s[:]	리스트 a의 원소를 모두 출력합니다	s[:]	[11, 22, 33, 44, 55, 66, 77]
s[:n]	리스트 s의 원소 중 맨 앞부터 n개까지 출력합니다	s[:3]	[11, 22, 33]
s[i:]	리스트 s의 원소 중 s[i]부터 맨 끝까지 출력합니다	s[3:]	[44, 55, 66, 77]
s[-n;]	리스트 s의 원소 중 -n부터 맨 끝까지 출력합니다	s[-3:]	[55, 66, 77]
s[::k]	리스트 s의 원소 중 맨 앞부터 k개씩 건너뛰며 출력합니다	s[::2]	[11, 33, 55, 77]
s[::-1]	리스트 s의 원소 중 맨 끝부터 전부 출력합니다	s[::-1]	[77, 66, 55, 44, 33, 22, 11]

 

 

뮤터블과 이뮤터블의 대입

뮤터블 mutable

값을 변경할 수 있는 특성

파이썬의 뮤터블 자료형 : 리스트, 딕셔너리, 집합 등

 

이뮤터블 immutable

값을 변경할 수 없는 특성

파이썬의 이뮤터블 자료형 : 수, 문자열, 튜플 등

 

자료구조의 개념 알아보기

자료구조 data structure

논리적인 관계로 이루어진 데이터 구성

데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계

 

02-2. 배열이란?

배열 원소의 최댓값 구하기

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

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


arr = [2, 6, 4, 67, 33, 22, 677]
print(max_of(arr))

# 실행 결과
677

 

스캔 scan

배열 원소를 하나씩 주목하여 살펴보는 방식(알고리즘 용어)

= 주사, 트래버스 traverse

 

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

배열 원소의 최댓값을 구하는 함수를 프로그램으로 구현

 # [Do it! 실습 2-2] 시퀀스 원소의 최댓값 출력하기

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

# 실행 결과
배열의 최댓값을 구합니다.
원소 수를 입력하세요 : 6
x[0]를 입력하세요.: 1
x[1]를 입력하세요.: 5
x[2]를 입력하세요.: 22  
x[3]를 입력하세요.: 77
x[4]를 입력하세요.: 3
x[5]를 입력하세요.: 4
최댓값은 77입니다.

 

어노테이션 type annotation

파이썬 코드에서 변수, 함수 인자, 그리고 반환 값의 기대되는 데이터 타입을 명시적으로 선언하는 방법

함수 어노테이션

강제성 없는 주석 달기로, 코드 자체에는 아무런 영향도 미치지 않음

python 3부터 추가됨

ex. def max_of(a: Sequence) -> Any:

 

재사용할 수 있는 모듈 작성하기

모듈 module

하나의 스크립트 프로그램

확장자(.py)를 포함하지 않는 파일의 이름 자체를 모듈 이름을 사용

 # [Do it! 실습 2-3] 배열 원소의 최댓값을 구해서 출력하기(원솟값을 입력받음)

from max import max_of // 모듈 max를 import 했음

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

# 실행 결과
배열의 최댓값을 구합니다.
주의: "End"를 입력하면 종료합니다.
x[0]를 입력하세요.: 6
x[1]를 입력하세요.: 44
x[2]를 입력하세요.: 5
x[3]를 입력하세요.: 3
x[4]를 입력하세요.: 22
x[5]를 입력하세요.: 6
x[6]를 입력하세요.: 77
x[7]를 입력하세요.: End
7개를 입력했습니다.
최댓값은 77입니다.

 

이터러블 iterable 객체

반복 가능한 객체

원소를 하나씩 꺼내는 구조

ex. 파이썬에서는 문자열, 리스트, 튜플, 집합, 딕셔너리 등

이터러블 객체를 내장 함수인 iter()의 인수로 전달 시, 그 객체에 대한 이터레이터 반환

이터레이터 iterator(반복자)
데이터의 나열을 포현하는 객체

이터레이터의 __next__함수 호출/내장 함수인 next() 함수에 이터레이터 전달 시, 원소를 순차적으로 꺼낼 수 있음

꺼낼 원소가 없을 경우 StopIteration으로 예외 발생 시키기 가능

 

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

맨 앞 원소와 맨 끝 원소를 교환, 그 다음 원소와 맨 끝에서 그 이전 원소를 교환하는 등 각각 하나씩 교환하는 작업을 반복함

-> 교환 횟수 = 원소 수 // 2번, 원소 수가 홀수인 경우 가운데 원소는 교환할 필요 없음

 

의사 코드 pseudo code

컴퓨터에서 바로 실행은 안되지만 알고리즘을 간단하고 분명하게 나타내는 코드

for i in range(n // 2)
	a[i]와 a[n - i - 1]의 값을 교환

 

배열 원소를 역순으로 정렬하는 프로그램

# [Do it! 실습 2-6] 뮤터블 시퀀스 원소를 역순으로 정렬

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]}')
        
# 실행 결과
배열 원소를 역순으로 정렬합니다.
원소 수를 입력하세요.: 7 
x[0] : 2
x[1] : 4
x[2] : 3
x[3] : 5
x[4] : 1
x[5] : 56
x[6] : 4
배열 원소를 역순으로 정렬했습니다.
x[0] = 4
x[1] = 56
x[2] = 1
x[3] = 5
x[4] = 3
x[5] = 4
x[6] = 2

 

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

기수

수를 나타내는 기초

ex. 10진법 : 0 ~ 9까지의 정수

 

기수로 변환하는 프로그램

# Do it! 실습 2-7 [A] 10진수 정수값을 입력받아 2~36진수로 변환하여 출력하기

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]          # 역순으로 반환

# Do it! 실습 2-7 [B]

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
           
# 실행 결과
10진수를 n진수로 변환합니다.
변환할 값으로 음이 아닌 정수를 입력하세요.: 234
어떤 진수로 변환할까요?: 16
16진수로는 EA입니다.
한 번 더 변환할까요?(Y ... 예/N ... 아니오): Y
변환할 값으로 음이 아닌 정수를 입력하세요.: 4
어떤 진수로 변환할까요?: 2
2진수로는 100입니다.
한 번 더 변환할까요?(Y ... 예/N ... 아니오): N

 

변환 과정을 나타낸 프로그램

# 10진수 정수값을 입력받아 2~36진수로 변환하여 출력하기(실습 2-7 수정)

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]  # 역순으로 반환

# 이하 Do it! 실습 2-7 [B]와 동일

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


# 실행 결과
10진수를 n진수로 변환합니다.
변환할 값으로 음이 아닌 정수를 입력하세요.: 77
어떤 진수로 변환할까요?: 16
16 | 77
   +----
16 |  4 … 13
   +----
      0 … 4
16진수로는 4D입니다.
한 번 더 변환할까요?(Y … 예/N … 아니오) : Y
변환할 값으로 음이 아닌 정수를 입력하세요.: 423
어떤 진수로 변환할까요?: 2
 2 | 423
   +-----
 2 | 211 … 1
   +-----
 2 | 105 … 1
   +-----
 2 |  52 … 1
   +-----
 2 |  26 … 0
   +-----
 2 |  13 … 0
   +-----
 2 |   6 … 1
   +-----
 2 |   3 … 0
   +-----
 2 |   1 … 1
   +-----
       0 … 1
2진수로는 110100111입니다.
한 번 더 변환할까요?(Y … 예/N … 아니오) : N