11.10 알고리즘 강의: 링크드 리스트 구현(2) 및 재귀 함수

링크드 리스트 구현

링크드 리스트 원소 찾기 및 삽입/삭제

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
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node
        
    def add_node(self, index, value):
        new_node = Node(value) #[6]
        
        if index == 0: #index가 0일 경우의 예외처리
            new_node.next = self.head
            self.head = new_node
            return
        
        node = self.get_node(index - 1) #index번째에 넣기 위해서는 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
            return
        node = self.get_node(index - 1)
        node.next = node.next.next #기존의 연결에서 제거대상 노드를 빼고 연결하기

linked_list = LinkedList(5) #[5]
linked_list.append(12) #[5]-[12]
linked_list.add_node(1, 6) #[5]-[6]-[12] 인덱스 1, index-1 = 0 [5]
linked_list.print_all()

 

이진 탐색 알고리즘

순차 탐색과 비교:

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_sequential(target, array):
    for number in array:
        if target == number:
            return True

    return False

#앞선 최빈값 찾기 알고리즘을 연상하자
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

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

** 이진 탐색 알고리즘은 일정한 규칙으로 정렬되어 있는 경우에만 사용 가능하다!

 

재귀 함수 : *코테빈출*

반드시 탈출조건(Terminal Condition)이 있어야 한다 -> OOM으로 인한 Recursion Error 발생을 막기위해

함수가 스스로를 호출하는 함수

왜? 간결하고 효율성있는 코드를 만들수 있다

1) 카운트 다운

def count_down(number):
    print(number)          # number를 출력하고
    if number < 0:
        return #음수 카운트다운은 제귀함수 에러발생
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)

2) 팩토리얼 N! : 정수 1부터 N까지 곱하기

input = "abcba"


def is_palindrome(string):
    return True


print(is_palindrome(input))

파이썬 : 콘솔 조작가능

3) 회문 검사

input = "abcba"


def is_palindrome(string):
    if len(string) <= 1: #1과 같거나 작을때까지 회문검사가 이루어졌다면, 이것은 회문이다
        return True
    if string[0] != string[-1]: #같지 않다면, 이것은 회문이 아니다
        return False
    return is_palindrome(string[1:-1]) #검사가 끝난 문자열에 대한 슬라이싱


print(is_palindrome(input))