22년 11월 23일 TIL

좋은 프로그램 = 프로그램을 수행하기 위해 꼭 필요한 자료구조 + 알고리즘

알고리즘 공부를 하면서 기본 코딩 능력을 튼튼히 하는 것에 무조건 집중해주세요!

기본 코딩 능력을 탄탄하게 만들기 → 문제에 대해 생각하는 능력을 키우기 전략으로 알고리즘 고수되기!

 

pseudo code = 문제를 해결하기 위한 절차를 말로 서술한 것.

---

어레이와 링크드 리스트

어레이(배열) : 캡슐 호텔

여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요? 오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라고 합니다.

rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

그런데, 제일 끝방에 있는 서현이 수영과 티파니 사이의 방에서 자고 싶다고 합니다. 다른 멤버들의 순서는 유지한채요! 그래서 다음과 같이 이동해야 했습니다.

참고로 코딩에서 변수를 옮길 때 한번에 하나씩 옮길 수 있어서 두명씩 방을 옮기게 됩니다

# 처음 상태
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

# 1번 이동 -> 써니와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "서현", "써니" ]

# 2번 이동 -> 태연과 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "유리", "서현", "태연", "써니" ]

# 3번 이동 -> 유리와 서현 변경
rooms = ["윤아", "수영", "티파니", "효연", "서현", "유리", "태연", "써니" ]

# 4번 이동 -> 효연과 서현 변경
rooms = ["윤아", "수영", "티파니", "서현", "효연", "유리", "태연", "써니" ]

# 5번 이동 -> 티파니와 서현 변경! 후! 드디어 도착!
rooms = ["윤아", "수영", "서현", "티파니", "효연", "유리", "태연", "써니" ]

• 배열은 크기가 정해진 데이터의 공간입니다. 한 번 정해지면 바꿀 수 없어요!
• 배열은 각 호텔방(원소)에 즉시 접근할 수 있습니다 rooms[0] 처럼요 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부릅니다.
• 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미합니다. 즉, O(1) 내에 접근할 수 있다고 말하곤 합니다.
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 합니다. 최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가집니다.
• 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조입니다.

링크드 리스트 : 화물열차

여러분이 이번엔 화물 열차를 만들었습니다. 총 5칸을 실은 화물 열차입니다. 각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있습니다!

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

우편 칸에 잠시 일이 생겼습니다! 시멘트 칸을 지나, 자갈칸을 지나, 밀가루 칸을 지나 겨우 우편칸에 도착했습니다.

# 처음 상태              내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 1번 이동                           내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 2번 이동                                      내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 3번 이동                                                 내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

# 4번 이동                                                             내 위치
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

앗 그런데, 자갈 칸과 밀가루 칸 사이에 흑연이라는 칸을 넣기로 했습니다. 그래서, 화물칸의 연결고리를 이어 붙였습니다. 간단하게 자갈 칸의 연결고리를 흑연 칸에 연결하고, 흑연 칸의 연결고리를밀가루 칸으로 연결했습니다.

# 처음 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
                              ["흑연"] 을 중간에 넣어야 합니다

# 1. 자갈 칸의 연결고리를 흑연 칸으로 연결하고,
["자갈"] -> ["흑연"]   ["밀가루"] -> ["우편"]

# 2. 흑연 칸으로 연결고리를 밀가루 칸으로 연결합니다. 
["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]

가던 도중 밀가루가 상해서 밀가루 칸을 버리기로 했습니다. 그래서 흑연 칸의 연결고리를 떼서 우편 칸으로 연결하기로 했습니다! 밀가루 칸을 버려버렸습니다.

# 현재 상태
["기관실"] -> ["시멘트"] -> ["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
                                              ["밀가루"] 칸을 버려야 합니다

# 흑연 칸의 연결고리를 떼서, 우편 칸으로 연결하면 됩니다!
["흑연"]     ->      ["우편"]  
        ["밀가루"]

• 링크드리스트는 원소의 삽입/삭제에 강점이 있는 자료구조입니다!
• → 리스트는 크기가 정해지지 않은 데이터의 공간입니다. 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있습니다!
• 리스트는 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 합니다. 최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가집니다.
• 여기서, 앞으로 연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 부르겠습니다.
• 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됩니다. 따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있습니다.

어레이와 링크드리스트의 차이

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.

 

클래스

• 클래스 : 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념
• 객체는 세상에 존재하는 유일무이한 사물입니다.
• 클래스가 사람이라면, 객체는 유재석이 될수도 있고, 박명수가 될 수도 있습니다.
• 클래스가 동물이라면, 객체는 강아지가 될수도 있고, 고양이가 될 수도 있습니다.
• 클래스를 이용하면 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있습니다!
• 클래스에는 생성자(Constructor)라는 게 있는데 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있습니다
• 파이썬에서 생성자 함수의 이름은 __init__ 으로 고정되어 있습니다 생성자는 생성시에 호출되는 함수입니다
• self 는 객체 자기 자신을 가리킵니다! 따라서,  파라미터를 따로 넣어주실 필요가 없이 그냥 호출하시면 알아서 self에 자기자신을 넣어줍니다!
• 클래스 내부의 함수는 메소드(method) 라고 부릅니다.

class Person:
    def __init__(self, param_name):
        print("hihihi", self)
        self.name = param_name  #나의 이름은 param_name

    def talk(self): #메소드
        print("안녕하세요 저는", self.name, "입니다")


person_1 = Person("유재석")  # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name)  # 유재석
person_1.talk()  # 안녕하세요 저는 유재석 입니다

person_2 = Person("박명수")  # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name)  # 박명수
person_2.talk()  # 안녕하세요 저는 박명수 입니다