<자료구조> 자료구조와 배열

 

1. 자료구조와 배열

* 배열이란

 - 하나의 값이 아닌 묶음 단위의 값을 저장하는 자료구조

 - 원소 : 배열에 저장된 객체 한 단위

 - 파이썬에서는 주로 리스트와 튜플로 배열을 표현함.

 

* 객체

 - 파이썬은 데이터, 함수, 클래스, 모듈 등 전부 객체로 취급하기때문에 변수는 값을 갖는 것이 아니다.

 - 모든 객체는 메모리를 차지하며 식별번호가 따로 존재한다.

 - 따라서 변수는 객체를 참조하는 별명이라고 보는 것이 좋다.

  예를 들어 10의 고유번호를 19991010 이라고 하자. 이 때 x = 10 이라고 선언하고 x의 식별번호를 확인하면 19991010이 나타난다.

  ※ 값을 비교할 때 연산자로 == 을 사용하지만 두 객체의 값과 식별번호를 함께 비교할 경우에는 is 를 사용한다.

 

* 리스트와 튜플

 - 리스트는 원소 변경이 가능한 뮤터블 객체이다.

 - 튜플은 원소 변경이 불가능한 이뮤터블 자료형이다.

 - 인덱스 접근

x = [10, 20, 30, 40, 50]
print(x[1])
print(x[-1])

# 20
# 50

     : 인덱스에서 1은 리스트의 앞에서 두번째 값을 의미하며, -1은 뒤에서 첫번째를 의미한다.

 

 - 슬라이스 접근

x = [10, 20, 30, 40, 50]
print(x[:2])
print(x[0:6:2])
print(x[-3:])
print(x[::-1])

# [10, 20]
# [10, 30, 50]
# [30, 40, 50]
# [50, 40, 30, 20, 10]

     : 슬라이스는 리스트에서 필요한 부분만을 나타내게 할 수 있다. [-3:] 은 뒤에서 3개까지 보여주게 되지만, [::-1]은 뒤에서부터 역으로 차례로 보여준다.

 

* 자료구조

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

 - 자료구조의 이해를 통해 컴퓨터의 데이터를 더 효율적으로 관리할 수 있다.

 

2. 배열과 알고리즘

* 최댓값 구하기

 - 최댓값은 다음과 같이 구할 수 있다.

n = int(input('숫자는 총 몇개입니까?'))
x = list()
for i in range(n) :
    x.append(int(input(f'{i+1}번째 값 : ')))
print('입력 받은 배열 :',x)
max = x[0]
for i in range(1, n) :
    if x[i] > max :
        max = x[i]
print('최댓값 :',max)

# 숫자는 총 몇개입니까?5
# 1번째 값 : 1
# 2번째 값 : 5
# 3번째 값 : 3
# 4번째 값 : 7
# 5번째 값 : 2
# 입력 받은 배열 : [1, 5, 3, 7, 2]
# 최댓값 : 7

 : 처음에 x를 리스트로 선언하여 주고 첫 for문에서 append를 통해 리스트에 차례로 입력받은 숫자를 int형으로 추가하여 준다.

   리스트의 첫 번째 원소를 max로 지정하고 두 번째 for문에서 각 원소와 비교하며 max값을 최대값으로 저장시킨다.

 

 다음든 위에서 두 번째 for문을 함수로 지정한 코드이다. 다양한 자료형에서 사용하기 위해 위와는 조금 차이가 있다.

from typing import Any, Sequence

def maximum(x: Sequence) -> Any:
    max = x[0]
    for i in range(1, n):
        if x[i] > max:
            max = x[i]
    return max

n = int(input('숫자는 총 몇개입니까?'))
x = list()
for i in range(n) :
    x.append(int(input(f'{i+1}번째 값 : ')))
print('입력 받은 배열 :',x)
print('최댓값 :',maximum(x))

 : 위의 코드도 결과는 똑같이 나온다.

 : 제약없는 임의의 자료형을 사용하기위해 Any를 임포트하였다.

 : 매개변수x의 자료형을 리스트든 튜플이든 시퀀스 자료형이라면 뭐든지 받기 위해서 Sequence도 선언하였다.

 : 함수를 보면 x는 시퀀스형이며 결과는 Any형태로 반환하겠다고 선언했음을 알 수 있다.

 

* 기수변환 프로그램

 이번에는 10진수를 다른 진수로 변환하는 프로그램을 작성해보자. 위에서와 달리 리스트가 아닌 단순한 문자열을 통해 만들 수 있다.

 

def conv(x:int, r:int) -> str:
    y = ''
    dchar = '0123456789ABCDEF'
    while x > 0 :
        y += dchar[x % r]
        x //= r
    return y[::-1]


while True:
    n = int(input('변환하기를 원하는 정수를 입력해주세요. :'))
    if n > 0 :
        break
while True:
    c = int(input('몇 진수로 변환하시겠습니까? (최대 16진수) :'))
    if 2 <= c <= 16 :
        break
print('입력 값 :', n)
print(f'변환 값 : {conv(n, c)}({c})')

# 변환하기를 원하는 정수를 입력해주세요. :7
# 몇 진수로 변환하시겠습니까? (최대 16진수) :2
# 입력 값 : 7
# 변환 값 : 111(2)

 

 : 기수변환 프로그램을 만들기 위해 먼저 함수를 선언하였다. y는 x정수가 변환된 결과값 문자열이다. 16진수까지 표현하기 위해서 0부터 F까지 dchar에 선언하였다. 그 후 나누는 과정은 아래 그림으로 자세히 보자.

 

 - input으로 받은 정수를 원하는 진수로 반복해서 나누게 된다.

 - 나머지가 그 진수의 문자열 한 원소가 되고 몫은 다시 나눠줘야한다.

 - 따라서 나머지를 dchar 문자열의 인덱스로 받고 몫은 다시 x로 선언하여 반복한다.

 - 몫이 0이 되면 지금까지의 문자열 y를 역으로 모두 반환시킨다.

 

* 함수와 이뮤터블 인수

def sum(n):
    s = 0
    while n !=0 :
        s += n
        n -= 1
    return s
x = int(input('정수를 입력하세요. : '))
print(f'1부터 {x}까지의 합 : {sum(x)}')

# 정수를 입력하세요. : 10
# 1부터 10까지의 합 : 55

 - 파이썬에서 매개변수에는 실제 인수가 대입되며 같은 값을 참조한다.

 - int는 이뮤터블 타입의 대표적인 예이다. 따라서 위의 코드에서 x가 함수에 대입되었지만 print함수에 x를 넣었음에도 x는 초깃값인 10을 유지하고 있음을 알 수 있다.

 - 따라서 함수 종료시 x는 10, n은 0임을 알 수 있다. 이는 매개변수와 단순히 같은 값을 참조만 했음을 알 수 있다.

 

* 함수와 뮤터블 인수

def change(lst, idx, val):
    lst[idx] = val

x = [1, 2, 3, 4, 5, 6, 7]
print('현재 x의 값은 :', x)
index = int(input('몇 번째 값을 변경하시겠습니까? : ')) + 1 # 1부터 시작하기 위해 +1
value = int(input('새로운 값은 무엇입니까? : '))
change(x, index, value)
print('현재 x의 값은 :', x)

# 현재 x의 값은 : [1, 2, 3, 4, 5, 6, 7]
# 몇 번째 값을 변경하시겠습니까? : 3
# 새로운 값은 무엇입니까? : 10
# 현재 x의 값은 : [1, 2, 3, 4, 10, 6, 7]

 - 리스트는 대표적인 뮤터블 자료형이다.

 - 따라서 함수 안에서 업데이트 된 값은 그대로 반영되어 변경됨을 알 수 있다.

 

* 얕은복사와 깊은복사

 - 얕은 복사(shallow copy) : 객체를 복사할 때 참조값만 복사하는 방식

 - 깊은 복사(deep copy) : 참조값 뿐만 아니라 참고하고 있는 객체 자체를 복사하는 방식

 - 예를 들어 x라는 1, 2, 3을 가진 리스트가 있다고 치자. y=x.copy() 를 사용하고 x를 1, 3, 5 로 변경하면 얕은 복사이므로 y도 x를 따라 변경된다.

    그러나 copy모듈을 임포트하여 y=copy.deepcopy(x) 를 하고 x를 변경하면 y는 x가 아니라 기존의 1, 2, 3 이라는 리스트 자체를 복사하였으므로 영향이 없다. 

 

 

 

 

 

---

 

참고

 

 이 글은 ‘이지스퍼블리싱’의 ‘자료구조와 함께 배우는 알고리즘 입문’을 공부 후 정리하며 쓴 글입니다.

 작성된 모든 내용과 코드는 교재 및 관련 사이트를 참고하여 직접 재구성하였습니다.

 

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

http://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

이지스퍼블리싱 스터디룸 카페

Do it! 스터디룸 : 네이버 카페

 

교재 공식 깃허브

easysIT/doit_dsalgo_with_python