21.12.07 TIL

알고리즘 문제 풀기 with Python

Array vs Linked List

Linked List 구현하기

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

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

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return self.head
        node = self.head
        while node.next is not None:
            node = node.next
        node.next = Node(data)
        return node.next

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

    def get_node(self, index):
        node = self.head
        for _ in range(index):
            node = node.next
        return node

    def add_node(self, index, data):
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        else:
            node = self.get_node(index-1)
            next_node = node.next
            node.next = new_node
            new_node.next = next_node

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
        else:
            node = self.get_node(index-1)
            node.next = node.next.next

my_list = LinkedList(4)
my_list.append(6)
my_list.append(8)
my_list.append(10)
my_list.append(12)

my_list.print_all()
print(my_list.get_node(2).data)

my_list.add_node(3, 9)
my_list.add_node(0, 1)
print('========')
my_list.print_all()

print('========')
my_list.delete_node(3)
my_list.delete_node(0)
my_list.delete_node(4)
my_list.print_all()

이진 탐색

순차 탐색은 처음부터 끝까지 한번 순회하면서 검색하는 것.

이진 탐색은 탐색 범위를 반으로 나누어가면서 검색하는 것. (업다운)

순차 탐색의 시간복잡도가 O(N) 이고 이진 탐색의 시간복잡도는 O(logN)

재귀 함수

재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것.

재귀 함수는 구현부에서 자기 자신을 호출하는 함수이다.

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

count_down(60)

재귀 함수는 반드시 무한정 돌게하면 안된다. (무한루프, RecursionError) 재귀에서의 탈출 조건이 필요하다.

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

count_down(60)

팩토리얼

N! = N * (N-1)! = N * (N-1) * (N-2)! ...

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

print(factorial(5))

회문 검사

input = "abcba"


def is_palindrome(string):
    if len(string) <= 1:
        return True
    elif string[0] == string[-1]:
        return is_palindrome(string[1:-1])
    else:
        return False


print(is_palindrome(input))