Class

• 클래스는 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념
• 객체 : 세상에 존재하는 유일무이한 사물
• 생성자 함수 : __init__ - 생성시에 호출되는 함수
• self : 객체 자기 자신을 가리킴

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를 사용해서 객체에 데이터를 쌓을 수 있음
• self.name = param_name -> 객체의 name이라는 변수에 저장하겠다!
• talk() 메소드 추가

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()  # 안녕하세요 저는 박명수 입니다

Array 와 Linked List

	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간 삽입 삭제	O(N)	O(1)
데이터 추가	새로운 메모리 공간 할당	맨 뒤의 노드만 동적 추가 가능
정리	데이터 접근이 잦은 경우	삽입,삭제가 잦은 경우

Linked List

노드에 필요한 것

• 칸에 있는 데이터
• 다음 칸의 정보

class Node:
    def __init__(self, data):
        self.data = data		# 받은 파라미터를 data에 저장
        self.next = None		# 다음 이어진 노드가 없어서 None

node = Node(3)					# data 값에 3을 넣고 생성하여 node라 저장		
print(node.data)   ->   3

first_node = Node(5) 	# next가 없이 하나의 노드만 있음 [5]
second_node = Node(12)  # [12] 를 들고 있는 노드를 만듦
first_node.next = second_node # [5]의 next를 [12]로 저장

next연결이 번거로우므로 LinkedList 클래스 생성

• head node만 들고 있음
• 다음 노드를 보기위해 각 노드의 next를 조회해서 찾아야 함

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)		  # head에 시작하는 노드 연결

    def append(self, data):

        if self.head is None:		  # head 가 비었을 경우 바로 대입
            self.head = Node(data)
            return                    # 함수 중단 위해

        cur = self.head				  # 현재 들어있는 값
        while cur.next is not None:	  # 다음이 있을 경우
            cur = cur.next
            print("cur is", cur.data) # 다음이 없을 경우 next에 값 대입
        cur.next = Node(data)

    def print_all(self):			  # LinkedLit 원소 출력
        cur = self.head
        while cur.next is not None:
            print(cur.data)
            cur = cur.next


linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all()     # [3] - [4] - [5]
							# cur is 4
                            # 3
                            # 4
                         

원소 찾기

• node 라는 변수에 head 값을 담고 하나씩 옮겨가며 index 번째를 찾아야 함.

   def get_node(self, index):			# [5] -> [12]
        node = self.head				# node = [5]
        count = 0
        while count < index:			# 0 < 1
            node = node.next			# node = [12]
            count += 1
        return node						# [12]

linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(1).data)	 	-> [12]

원소 추가

• index 번째에 value 원소 추가
• 넣어야할 자리 앞, 뒤를 저장해놓고 그 사이에 새로운 node 추가
• index = 0, head 값을 미리 다음 값으로 저장한 후 head에 새 값 대입

										  node   node.next
 def add_node(self, index, value):		 # [5] -> [12]
        new_node = Node(value)           # new_node = [6]
        node = self.get_node(index - 1)  # node = [5]
        next_node = node.next            # next_node = [12]

        node.next = new_node             # [5] -> [6]
        new_node.next = next_node		 # [6] -> [12]
   
   
# index가 0일 경우
  def add_node(self, index, value):
        new_node = Node(value)			 # 넣을 값 저장
        if index == 0:
            new_node.next = self.head    # head값을 미리 다음 값으로 저장
            self.head = new_node         # head깂에 새 값 넣음

        node = self.get_node(index - 1)
        next_node = node.next

        node.next = new_node
        new_node.next = next_node

linked_list = LinkedList(5)			 
linked_list.append(12)				   0	  1	      2
linked_list.append(8)				# [5] -> [12] -> [8]
linked_list.add_node(1, 6)
linked_list.print_all()				# [5] -> [6] -> [12] -> [8]

원소 삭제

• index 번째 원소 삭제
• index 번째 앞, 뒤를 저장한 후 해당원소 제거한 후 앞, 뒤를 연결
• index = 0, head 값을 그 다음 값으로 변경

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return

        node = self.get_node(index - 1)   # index번째 앞의 값
        node.next = node.next.next	   	  # index 다음다음 값을 다음 값으로 저장

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)			# [5] - [12] - [8]
linked_list.delete_node(2)
linked_list.print_all()			# [5] - [8]

이진 탐색(Binary Search)

• 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
• 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

순차 탐색

• O(N) 만큼의 시간 복잡도가 걸린다.

이진 탐색

총 숫자가 1~N 까지라고 한다면,
1번 탐색하면 반절이 줄어드니 $N/2$ 개가 남습니다.
2번 탐색하면 반절이 줄어드니 $N/4$ = $N/2^2$ 개가 남습니다.
3번 탐색하면 반절이 줄어드니 $N/8$ = $N/2^3$ 개가 남습니다.
....
k번 탐색하면 반절이 줄어드니 $N/2^k$ 개가 남습니다.

이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다.
이걸 수식으로 표현하면, $N/2^k = 1$ 입니다.
즉, $k = \log_2{N}$ 횟수를 시도하면 정답을 찾을 수 있습니다!

결론적으로 이분탐색을 위해서는 시간 복잡도가 O(logN) 만큼 걸린다.
라고 말할 수 있습니다.

# 배열에서 14가 있는지 확인
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

    while current_min <= current_max:
        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)

재귀 함수(Recursion)

• 자기 자신을 호출하는 함수

def count_down(number):
    if number < 0:         # 만약 숫자가 0보다 작다면, (탈출조건)
        return

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

count_down(60)


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


print(factorial(5))

회문(Palindrome)

• 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장

input = "abcba"

def is_palindrome(string):
    n = len(string)
    for i in range(n):
        if string[i] != string[n - i - 1]:
            return False
    return True

print(is_palindrome(input))

# 재귀함수로 해결
input = "abcba"

def is_palindrome(string):
    if len(string) <= 1:    # 한 글자는 회문으로 간주
        return True
    if string[0] != string[-1]:
        return False
    return is_palindrome(string[1:-1])  # 재귀 함수 사용

print(is_palindrome(input))