algorithm_review_2편(ft. python)

2. array / linked_list + class + binary_search + recursive_function

• 배열의 특징

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

• Linked_list

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

• Class

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

   • 그렇다면 객체란?
     -> 객체는 세상에 존재하는 유일무이한 사물이다.
     ex) '인간' 클래스의 '박하영'이라는 객체.

2. 클래스를 이용하면 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있다.

ex)

class Person:
    pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미이다.


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

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

• 파이썬에서 생성자 함수의 이름은 init 으로 고정되어 있다. 따라서, 생성자 이름의 함수는 무조건 init 이다.

ex)

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> 이 출력된다.

• 생성자는 생성시에 호출되는 함수이다. 따라서, 위에 예제처럼 Person 을 생성하기만 해도 hihihi 와 self 가 동시에 출력이 된다.

• 여기서 self란? self 는 객체 자기 자신을 가리킨다. 따라서, 파라미터를 따로 넣어주실 필요없이 그냥 호출하면 알아서 self에 자기자신을 넣어준다.

ex)

class Person:
    def __init__(self, param_name):
				print("hihihi", self)
        self.name = param_name


person_1 = Person("유재석")  # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name)  # 유재석

person_2 = Person("박명수")  # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name)  # 박명수

• self 를 사용해서 객체에 데이터를 쌓을 수가 있는데, self.name 에 param_name 을 저장해두겠다는 건 -> 그 객체의 name 이라는 변수에 저장된다는 의미이다.

• 클래스 내부의 함수는 메소드(method) 라고 부른다. talk 라는 메소드를 만들어 보면,
  각 객체의 변수를 사용해서 메소드를 구현할 수 있다.

talk method ex)

class Person:
    def __init__(self, param_name):
        print("hihihi", self)
        self.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()  # 안녕하세요 저는 박명수 입니다

• 이처럼 클래스를 이용하면, 연관성 있는 데이터들을 클래스 내에서 관리할 수 있으며, 다양한 객체들을 쉽게 생성할 수 있게 된다!

• binary_search

• 만약 7번의 기회속에서 숫자의 범위 1~100 까지중 정답을 맞춰야 된다면, 어떻게 맞추는게 효율적일까?

-> 1부터 하나씩 천천히 맞춰본다..? (순차탐색) or 절반값으로 선택해 한번의 기회에 후보군중 절반씩 줄여나간다..? (이진탐색)

알고리즘 관점으로 가장 효율적인 방법은 이진탐색이다.

binary_search ex)

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    find_count = 0
    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)  # 3!
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2

    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

• 이진탐색의 시간복잡도는..?
  -> 상수는 무시해도 되기 때문에, 이분탐색을 위해서는 시간 복잡도가 O(logN) 만큼 걸린다고 말할 수 있다.

(쉽게 말해서, 연산량이 반으로 나눠진다.. 싶으면 O(logn) 이겠구나 생각하면 된다)

• recursive_function

• 재귀란?
  -> 재귀(Recursion)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

• 주의할 점*
  -> 재귀함수는 반드시 빠져나가는 지점을 명확하게 정해줘야 한다. 그렇지 않으면 무한 루프에 빠져서 에러가 나기 때문이다.

ex)

def count_down(number):
    if number < 0:         # 만약 숫자가 0보다 작다면, 빠져나가자.
        return

    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다.


count_down(60)

• 위 예제와 같이 탈출 조건을 만들어줌으로써 재귀 함수의 반복을 멈출 수 있다.

• Factorial

• 재귀함수와 관련되어 나오는 대표적인 문제인 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.

ex)

3! 은 3 x 2 x 1 = 6,
4! 은 4 x 3 x 2 x 1 = 4 x 3! = 24

즉,
Factorial(n) = n Factorial(n - 1)
Factorial(n - 1) = (n - 1) Factorial(n - 2)
....
Factorial(1) = 1 구조이다.

• factorial ex code)

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(60))