[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 2주차

• 배열(Array) : 크기가 정해진 데이터의 공간
  - 한 번 정해지면 바꿀 수 없음
  - 각 원소에 즉지 접근 가능
  - 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함 (최악의 경우 O(N)의 시간 복잡도가짐)
  - 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조임.

 

• 클래스 : 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념이다.
  - 객체 : 세상에 존재하는 유일무이한 사물
  클래스를 사용하면 같은 속성, 기능을 가진 객체들을 묶어서 정의 가능!  

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.name)
person_1.talk()
print(person_1)  # <__main__.Person object at 0x1090c76d0>
person_2 = Person('박명수')
print(person_2.name)
person_2.talk()
print(person_2)  # <__main__.Person object at 0x1034354f0>

# 연관성 있는 데이터들을 클래스 내에서 관리하면서 다양한 객체를 쉽게 생성하기 위해서는 클래스라는 개념을 잘 이용해야한다.

 

• 링크드리스트(linked list) : 크기가 정해지지 않은 데이터의 공간
  - 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있음
  - 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 함 (최대 O(N)의 시간 복잡도 가짐)
  - 원소를 중간에 삽입/삭제 하기위해서는 앞 뒤의 포인터만 변경하면 됨. (O(1)의 시간 복잡도)

       각 인덱스 값의 노드는 1) 칸에 있는 데이터(머리) 와 2) 다음 칸이 무엇인지(꼬리) 두가지 정보가 필요하다.

       그래서 Node 클래스에서 1) data 와 2) next 를 인자로 받아서 저장한다.

 

- LinkedList 클래스의 print_all() 함수 : 모든 원소 출력

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        if self.head is None:  # head 의 값이 Node 일때
            self.head = Node(data)  # self.head 에 새로운 데이터 추가
            return  # 함수 종료

        cur = self.head

        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    def print_all(self):
        cur = self.head
        while cur 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()

 

- 링크드 리스트 원소 찾기 get_node()

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        cnt = 0
        while cnt < index:
            node = node.next
            cnt += 1
        return node

linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!

- 링크드 리스트 원소 추가 add_node()

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        cnt = 0
        while cnt < index:
            node = node.next
            cnt += 1
        return node

    # index    next_node
    # ['자갈] ['밀가루'] -> ['우편']
    #          new_node
    #        -> ['흑연'] ->
    # index.next = new_node
    # new_node.next = next_node

    def add_node(self, index, value):
        if index == 0:
            new_node = Node(value)  # [6] -> [5]
            new_node.next = self.head # head -> [6]
            return

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


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

# [5] -> [6] -> [12] -> [8]

linked_list.add_node(1, 6)
linked_list.print_all()

- 링크드 리스트 원소 삭제 delete_node()

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        cnt = 0
        while cnt < index:
            node = node.next
            cnt += 1
        return node

    # index    next_node
    # ['자갈] ['밀가루'] -> ['우편']
    #          new_node
    #        -> ['흑연'] ->
    # index.next = new_node
    # new_node.next = next_node

    def add_node(self, index, value):
        new_node = Node(value)  # [6]
        if index == 0:
            new_node.next = self.head  # [6] -> [5]
            self.head = new_node # head -> [6] -> [5] -> ...
            return

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

    # ['자갈] ['밀가루'] -> ['우편']

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return  # 아래 코드가 실행되지 않도록
        node = self.get_node(index - 1)
        node.next = node.next.next


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.delete_node(0)
linked_list.print_all()

- 두 링크드 리스트의 합 계산 _get_linked_list_sum()

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)


def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = _get_linked_list_sum(linked_list_1)
    sum_2 = _get_linked_list_sum(linked_list_2)

    return sum_1 + sum_2


def _get_linked_list_sum(linked_list):
    linked_list_sum = 0  # linked_list 합계
    head = linked_list.head
    while head is not None:
        linked_list_sum = linked_list_sum * 10 + head.data
        head = head.next

    return linked_list_sum


linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

• 이진 탐색 : 반으로 나눠서 진행한다.

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):
    currnet_min = 0
    current_max = len(array) - 1
    current_guess = (currnet_min + current_max) // 2
    while currnet_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            currnet_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_max + currnet_min) // 2

    return False


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

• 순차 탐색 : 처음부터 순차적으로 진행한다.

• 재귀함수 : 자기 자신을 호출하는 함수

              - 재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것

 

- 카운트 다운

def count_down(number):
    if number < 0:         # 탈출 조건
        return
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)

- 팩토리얼

# Factorial(N) = N * Factorial(N-1_
# ...
# Factorial(1) = 1

#             factorial(1)
# 5 * 4 * 3 * 2 * 1
def factorial(n):  # 1
    if n == 1:     # True
        return 1
    return n * factorial(n - 1)


print(factorial(5))

- 회문 검사 (회문 : ["기러기 토마토 스위스 인도인 별똥별 우영우! 거꾸로 해도 우영우! ... 역삼역?" - 우영우-] )

    - 반복문

input = "tamato"


#        01234
# 1. index 0 이랑 n-1 같으면 true
# 2. index 1 이랑 n-2 같으면 true

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

    return True


print(is_palindrome(input))

    - 재귀함수

input = "소주만병만주소"


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

# 문제가 축소되는 특징이 보여야함
# 특정 구조가 반복되는 것 같은 양상을 보았으면
# 재귀함수 시도 생각
# 재귀함수를 쓸경우 반드시 탈출 조건 작성

============================================================================================

출처 : [스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 2주차

============================================================================================

솔직한 심정

(그만해...)