2주차_어레이, 링크드리스트, 클래스

Array 와 LinkedList

 

1. Array 이야기

여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요? 오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라고 합니다.	→ 배열은 크기가 정해진 데이터의 공간입니다. 한 번 정해지면 바꿀 수 없어요!
떨리는 마음으로 체크인을 받고, 각 호수에 있는 멤버들의 방에 방문해 웰컴 드링크를 전달했습니다.	→ 배열은 각 호텔방(원소)에 즉시 접근할 수 있습니다 rooms[0] 처럼요! 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부릅니다. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미합니다. 즉, O(1) 내에 접근할 수 있다고 말하곤 합니다.
앗 그런데, 제일 끝방에 있는 서현이 수영과 티파니 사이의 방에서 자고 싶다고 합니다. 다른 멤버들의 순서는 유지한채요! 그래서 다음과 같이 이동해야 했습니다. # 처음 상태 rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"] # 1번 이동 -> 써니와 서현 변경 rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "서현", "써니" ] # 2번 이동 -> 태연과 서현 변경 rooms = ["윤아", "수영", "티파니", "효연", "유리", "서현", "태연", "써니" ] # 3번 이동 -> 유리와 서현 변경 rooms = ["윤아", "수영", "티파니", "효연", "서현", "유리", "태연", "써니" ] # 4번 이동 -> 효연과 서현 변경 rooms = ["윤아", "수영", "티파니", "서현", "효연", "유리", "태연", "써니" ] # 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착! rooms = ["윤아", "수영", "서현", "티파니", "효연", "유리", "태연", "써니" ] 너무 힘들게 방을 옮겨서 피곤해진 서현이는 바로 곯아떨어졌다고 합니다.	→ 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 합니다. 최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가집니다.
갑자기 호텔 프론트에 전화가 왔습니다. 매니저가 곧 도착할 예정이니, 방 하나를 더 준비해달라고 연락이 왔습니다! 이런, 어떡하죠? 그래서 옆 공터에 방이 9개인 호텔을 지었습니다. 물론 새로운 호텔을 짓느라 돈과 시간을 다 써 사업이 망해버리고 말았습니다 ㅠㅠ	→ 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조입니다.

 

 

2. LinkedList(List) 이야기

 

여러분이 이번엔 화물 열차를 만들었습니다. 총 5칸을 실은 화물 열차입니다. 각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있습니다!	→ 리스트는 크기가 정해지지 않은 데이터의 공간입니다. 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있습니다!
우편 칸에 잠시 일이 생겼습니다! 시멘트 칸을 지나, 자갈칸을 지나, 밀가루 칸을 지나 겨우 우편칸에 도착했습니다.	→ 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 합니다. 최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가집니다. 여기서, 앞으로 연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 부르겠습니다.
앗 그런데, 시멘트 칸과 자갈 칸 사이에 흑연이라는 칸을 넣기로 했습니다. 그래서, 화물칸의 연결고리를 이어 붙였습니다. 시멘트 칸의 연결고리를 흑연 칸에 연결하고, 흑연 칸의 연결고리를 자갈 칸으로 연결했습니다. 가던 도중 밀가루가 상해서 밀가루 칸을 버리기로 했습니다. 그래서 흑연 칸의 연결고리를 떼서 우편 칸으로 연결하기로 했습니다! 밀가루 칸을 버려버렸습니다.	→ 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됩니다. 따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있습니다.

 

표로 정리하자면

 

 

참고로 Python의 list는 array로 구현되어있지만

내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어있다.

파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조다!

https://stackoverflow.com/questions/5932328/internals-of-python-list-access-and-resizing-runtimes/5932364#5932364

Internals of Python list, access and resizing runtimes

---

클래스

 

클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념이다.

객체는 세상에 존재하는 유일무이한 사물이다.

(ex) 클래스가 사람이면 객체는 유재석, 박명수 등등이 될 수 있다

      클래스가 동물이면 객체는 강아지, 고양이 등등이 될 수 있다)

 

class Person:
    pass # 안에 아무런 내용이 없다


person_1 = Person()
print(person_1)  # <__main__.Person object at 0x1090c76d0>
person_2 = Person()
print(person_2)  # <__main__.Person object at 0x1034354f0>

 

클래스에 생성자가 있는데 객체를 생성할 때 데이터를 넣어주거나 내부적으로 원하는 행동을 실행하게 할 수 있다.

생성자는 생성시에 호출되는 함수인데

파이썬에서 생성자 함수의 이름은 __init__으로 고정되어 있다!

class Person:
    def __init__(self):
        print("hihihi", self)


person_1 = Person()  
# hihihi <__main__.Person object at 0x1067e6d60> 

person_2 = Person()  
# hihihi <__main__.Person object at 0x106851550>

 

 

self를 이용해서 객체에 데이터를 넣을 수가 있는데

class Person:
    def __init__(self, param_name):
        print("i am created!", self)
        self.name = param_name


person_1 = Person("유재석")
print(person_1)
print(person_1.name)

person_2 = Person("박명수")
print(person_2)
print(person_2.name)


"""
i am created! <__main__.Person object at 0x000001F340348BE0>
<__main__.Person object at 0x000001F340348BE0>
유재석
i am created! <__main__.Person object at 0x000001F3404EAEB0>
<__main__.Person object at 0x000001F3404EAEB0>
박명수
"""

Person()안에 들어간 "유재석"은 self.name에 저장되어있기 때문에

person_1.name을 해야 찍힌다

 

클래스 내부함수 method를 추가해보자

class Person:
    def __init__(self, param_name):
        print("i am created!", self)
        self.name = param_name
    def talk(self):
        print("안녕하세요 저는", self.name, "입니다")


person_1 = Person("유재석")
print(person_1)
print(person_1.name)
person_1.talk()

person_2 = Person("박명수")
print(person_2)
print(person_2.name)
person_2.talk()


"""
i am created! <__main__.Person object at 0x00000259BF4F8BE0>
<__main__.Person object at 0x00000259BF4F8BE0>
유재석
안녕하세요 저는 유재석 입니다
i am created! <__main__.Person object at 0x00000259BFAFAE80>
<__main__.Person object at 0x00000259BFAFAE80>
박명수
안녕하세요 저는 박명수 입니다
"""