자료구조 2-1강 | Array and List | 숙명여대 학점교류

학점교류로 수강하는 숙명여대 자료구조 계절학기 수업

day 2. 2021.12.23. 목

---

Array and List

variable

Array

List

Polynomial

Bowling

Sparse Matrix

 

* 파이썬으로 바꾸면서, 포인터/배열이 빠짐... :/

---

Array and List

variable

python variable is a reference to a literal value

파이썬의 변수는 literal value의 주소를 참조하는 변수이다. (포인터 같음)

파이썬 변수의 값을 literal value라고 한다. 

a, b = b, a #swap

 

 

Data Type : mutable / immutable 

 

immutable Data type

 

int, float, string

 

literal 값 변경이 불가능하다. 

변수에서 값을 변경하는 경우 다른 값을 갖는 새로운 리터럴을 참조한다. 

매개변수를 전달하는 경우, 값을 변경하는 것이 불가능하다. 

list, 매개변수 전달에서 값 변환 안되는 것 이해 가능함

 

a = 2
b = a
print("a", a, id(a)) #a가 참조하는 literal의 주소
print("b", b, id(b))
b = b+1
print("a", a, id(a))
print("b", b, id(b))

 

alias : 같은 값(리터럴)을 공유하는 변수? 

literal은 바꿀 수 없음

 

mutable Data type

 

list, dictionary : 군집 자료형

 

list, dictionary의 원소 값을 변경, 추가 가능함

list : 각 원소값에 대한 참조들의 모음

매개 변수 전달시 인수 값이 변경될 수 있다. 

 

list 원소에 대한 참조는 바꿀 수 있다. 

 

A = [2, 3, 4]
A[1] = 5
B = A
print("A", A, id(A))
print("B", B, id(B)) # B가 A의 alias가 됨
B.append(7)
print("A", A, id(A))
print("B", B, id(B))

 

list가 변경되었음

 

parameter passing

 

불변 자료형을 함수에 전달하면, 그냥 바꾸지 못한다. 

 

call by value

call by reference

 

파이썬은

Call by object reference

 

call by value랑 call by object reference

call by value를 사용하는 C언어에서도  return (int)a;를 이용하면  변수 값을 바꾸어줄 수 있지 않나요? 

call by value랑 call by object reference가 정확히 어떻게 다른지 궁금합니다..

 

>> call by object reference는 value랑 비교되는 개념이 아니다. 

값을 복사해주고 리턴해서 받으니까 비슷한 개념으로 느껴지지만, 

call by value는 값을 복사해서 저장 공간에 저장해주지만, 

참조 변수이므로 값이 복사되는 게 아니라, 값의 리터럴을 참조 변수가 바꾸어준다. 

 

 

>> call by reference랑 비교하면, 주소값을 쉐어해서 직접 바꾼다. 

그냥 허용하지는 않는다. 

참조변수임에도 그렇게 동작하지 않음

 

 

def f(a):
    a = 3 # a는 3을 가리킴
    print(a)
    return a

b = 2 # b는 2를 가리킴
f(b) # 받는 변수가 지정되지 않음
print(b) # b는 바뀌지 않음
b = f(b) # b가 reference하는 곳이 3으로 바뀜
print(b)

 

 

 

Array

static array

- def)

a collection of elements whose data type is the same

elements are stored in consecutive memory locations

after declaration, array size is fixed

an element is accessed by index, [i]

 

list 원소의 길이를 계속해서 바꿔줄 수 있다. 

static array는 연속적으로 메모리에 존재한다. 

list는 꼭 그렇지는 않다. 

 

(array를 쓸 필요 없다)

 

 

List

data types of elements need not to be the same

list size is not fixed, and...

 

how to create a list

num = [i for i in range(100)]
num = list(range(100))
num = []
for i in range(100):
    num = num + [i]

 

shallow and deep copy

static array는 같은 type이어야 하지만, 

list는 그럴 필요가 없다 - list는 struct와도 같은 특성을 가지고 있다. 

 

B는 alias로, A와 같은 것을 공유한다. 

A = [[2,3,4],5]
B = A
B[0][1] = 'f'
print(A, id(A))
print(B, id(B))

 

shallow copy

참조 변수가 공유하는 literal은 공유하되

list 원소만 복사해준다. 

alias가 아니라 새로운 원소가 생긴 것임

같은 대상을 공유한다. 

주소가 바뀜

 

import copy
A = [[2,3,4],5]
B = copy.copy(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]))
print(B, id(B), id(B[0]), id(B[0][1]))

 

Deep Copy

얕은 복사는 리스트 원소만 복사한다. 깊은 복사는 리스트 원소가 참조하는 대상까지 복사한다. 완전히 동일한 두 개의 list, 대상까지 생긴다. clone격

import copy
A = [[2,3,4],5]
B = copy.deepcopy(A)
B[0][1] = 'f'
B[1] = 7
print(A, id(A), id(A[0]), id(A[0][1]))
print(B, id(B), id(B[0]), id(B[0][1]))

주소가 전부 다르게 나온다. (리스트 속의 리스트까지 바뀌게 된다?)

 

-> 머리로만 이해하지 말고, 직접 해봐라. 

 

Bowling Game

10 Frames and 1 bonus throwStrike : 10 points + next two throw scoresSpare : 10 points + next one throw score

 

10 frame

10 프레임에서 첫번째에서 스트라이크를 치면, 두 번의 보너스를 준다. 

: strike : 2 bonus throws - (10, - ,7, 3): spare : 1 bonus throws - (8, 2, 10, -): none : 0 bonus throws - (6,3, -, -)

 

score1 = [(8,0), (4,3), (4,6), (2,6), (10,0), (9,0), (10,0), (8,2), (10,0),(10,10)]
score2 = [(10,0), (10,0), (10,0),(10,0), (10,0), (10,0),(10,0), (10,0), (10,0),(10,0),(10,10)]

def bowling(score):
    total = i = 0
    frame = []
    for first, second in score:
        f_total = first+second
        if i != 9:
            next_first, next_second = score[i+1]
        if first == 10:
            result = 'STRIKE'
            f_total += next_first + next_second
            if i < 8 and next_first == 10:
                next_next_first, next_next_second = score[i+2]
                f_total += next_next_first
        elif (first+second)==10:
            result = 'SPARE'
            f_total += next_first
        else: result = 'NONE'
        total += f_total
        frame.append((f_total, result))
        i += 1
        if i == 10: break
    print(frame)
    print("Total = ", total)
    print()

bowling(score1)
bowling(score2)

 

 

 

---