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

파이썬에서 ''=''는 '+ - * /'와 같은 연산자가 아닙니다.

print(([1,2,3] is [1,2,3])) #등일성
print(([1,2,3] == [1,2,3])) #등가성

 

문자열, 리스트, 튜플, 집합, 딕셔너리 등의 자료형 객체는 모두 이터러블하다는 공통점이 있다???
집합과 딕셔너리도 순환 할 수 있는 건가?? YES

a = {1,3,23,55}
print(type(a))
for i in a:
	print(i)
dic = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}
print(type(dic))
for i in dic.values():
	print(i)

 

# [Do it! 실습 2-8] 1,000 이하의 소수를 나열하기

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

for문에 else를 붙이는 구문도 가능하다. *#끝까지 나누어 떨어지지 않으면 다음을 수행

 

다른 프로그래밍 언어에서는 실제 인수의 값을 매개변수에 복사하는 값에 의한 호출(call by value)을 사용하거나, 실제 인수의 참조를 매개변수에 복사하여 매개변수가 실제 인수와 같아지는 참조에 의한 호출(call by reference)를 이용하지만, 파이썬에서는 2가지 호출의 중간적인 방식으로 참조한다. 파이썬 공식문서에서는 객체 참조에 의한 전달(call by oject reference)이라는 용어를 사용하여 설명하고 있다. 인수(parameter)의 타입이 immutable, mutable 인지에 따라 값이 변하지않거나, 변하거나한다.

 

내장함수 copy의 얕은복사(참조)와 깊은복사(복제)가 있다. 깊은 복사의 경우는 객체가 참조할 메모리를 새로 쓰는 것 같다.

 

파이썬에서 enum의 활용 https://www.daleseo.com/python-enum/

파이썬 enum 타입 사용법

hash구조에서 key값은 하나만 가진다. 다만 key값이 hash함수에 얻어진 hash value는 여러개로 존재할 수 있다. 해시충돌을 해결하기위해, chain법과 open address방법을 배웠는데, chain법이 linked list로써 동적인 삭제와 삽입이 가능해서 편하다고 느껴진다.

 

던더 함수(double underscore)

__len__()

클래스에 __len()__ 함수를 정의하면 클래스형의 인스턴스를 __len__() 함수에 인자로 전달할 수 있습니다.

obj.__len__() == len(obj)

 

__contains__()

인스턴스에 맴버십 판단 연산자인 in을 적용할 수 있습니다.

obj.__contains__() == x in obj

 

파이썬에는 자료구조에 대한 모듈 collections가 있다. 이 클래스를 이용하여 다양한 자료구조의 데이터 삭제,삽입,정렬들을 시도할 수 있다.

 

큐를 배열로 구현하기도하지만, 이때는 buffer내부에서 데이터가 삽입, 삭제 될때마다 배열의 요소들을 움직여줘야하는 단점이 있다. 이 단점을 해결하기위해 링 버퍼 구조의 큐를 구현할 수 있다.
큐에서 주의할 점은 front와 rear의 index만으로는 큐의 구조를 알 수 없다는 것이다. 예를 들면, 링 버퍼가 전부 차있는 경우에도 front == rear이고, 링 버퍼가 전부 비워져있는 경우도 front == rear이다. 따라서 위 경우롤 분리해주기 위한 변수 하나가 더 필요한데, 이때 변수의 갯수를 담는 것을 사용하면 좋다.

큐의 링 버퍼에서 find를 진행할 때, front가 rear보다 값이 작은 경우 뒤엉키게 되는데, 이때 경우를 나누지않고 수학적으로 잘 풀어낼 수 있는 식을 보고 놀랐다.
index = (i + front) % capacity

 

링 버퍼의 활용(가장 최신 값들만 가지고, 오래된 값은 덮혀씌여지는 구조)

# [Do it! 실습 4C-2] 원하는 개수(n)만큼 값을 입력받아 마지막 n개를 저장

n = int(input('정수를 몇 개 저장할까요? : '))
a = [None] * n  # 입력 받은 값을 저장하는 배열

cnt = 0         # 입력 받은 개수
while True:
    a[cnt % n] = int(input((f'{cnt + 1} 번째 정수를 입력하세요.: ')))
    cnt += 1

    retry = input(f'계속 할까요?(Y ... Yes / N ... No) : ')
    if retry in {'N', 'n'}:
        break

i = cnt - n
if i < 0: i = 0

while i < cnt:
    print(f'{i + 1}번째 = {a[i % n]}')
    i += 1

재귀함수(유클리드호제법, 하노이탑, N-Queen(가우스))

------

트리구조, 문자열검색, 정렬에 대해서는 지겨워서 그만뒀다. 나중에 다시 시도하자.