스파르타 코딩클럽

내일배움캠프 AI 웹개발자양성과정 2회차

알고리즘 강의 2주차 개발일지

1. Array vs LinkedList

1) Array

• 크기가 정해진 데이터
• 각 원소에 즉시 접근 가능 ($O(1)$)
• 삽입, 삭제 어려움 ($O(N)$)
• 새로운 원소 추가시 새로운 공간을 할당해야되서 비효율적

2) LinkedList

• 크기가 정해지지않은 데이터
• 원소에 접근하기 위해서는 순차탐색 필요 ($O(N)$)
• 삽입, 삭제, 추가 용이 ($O(1)$)

2. LinkedList 구현

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

    def __del__(self):
        print(f"node({self.data}) is deleted.")


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):
        if index < 0:
            print("index는 0이상의 값을 입력해주세요.")
            return

        current_node = self.head
        count = 0
        while count < index:
            current_node = current_node.next
            count += 1

        return current_node

    def add_node(self, index, value):
        if index < 0:
            print("index는 0이상의 값을 입력해주세요.")
            return

        new_node = Node(value)

        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        pre_node = self.get_node(index-1)
        new_node.next = pre_node.next
        pre_node.next = new_node

    def delete_node(self, index):
        if index < 0:
            print("index는 0이상의 값을 입력해주세요.")
            return

        if index == 0:
            # del_node = self.head
            self.head = self.head.next
            # del del_node
            return

        pre_node = self.get_node(index-1)
        del_node = pre_node.next
        pre_node.next = del_node.next
        del del_node

        return

linked_list = LinkedList(5)
linked_list.append(10)
linked_list.append(11)
linked_list.append(12)
linked_list.add_node(3, 3)
linked_list.print_all()

print("--------")
linked_list.delete_node(0)
linked_list.print_all()

3. 이진탐색

: 찾고자하는 원소를 정렬된 배열의 중간을 기준으로 범위를 좁혀가며 탐색하는 알고리즘

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

https://www.geeksforgeeks.org/binary-search/

1) 시간복잡도 (vs 순차탐색)

: 이진탐색은 한번 탐색할 때마다 배열의 범위를 절반으로 줄이기 때문에 시간복잡도가 $O(logN)$으로 순차탐색(선형탐색)의 시간복잡도인 $O(N)$ 보다 낮다.

2) 이진탐색 구현

: 반복적인 방법과 재귀적인 방법 두가지 이용

finding_target = 14.5
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):
    start_point = 0
    end_point = len(array) - 1

    while start_point <= end_point:
        avg_point = (start_point + end_point) // 2

        if array[avg_point] == target:
            return True
        if array[avg_point] > target:
            end_point = avg_point - 1
        elif array[avg_point] < target:
            start_point = avg_point + 1

        print(start_point, end_point)
    return False


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


def is_existing_target_number_binary_by_recall(target, array, start_point, end_point):
    print(start_point, end_point)
    if start_point > end_point:
        return False

    avg_point = (start_point + end_point) // 2
    if array[avg_point] == target:
        return True
    if array[avg_point] > target:
        return is_existing_target_number_binary_by_recall(target, array, start_point, avg_point - 1)
    elif array[avg_point] < target:
        return is_existing_target_number_binary_by_recall(target, array, avg_point + 1, end_point)


result = is_existing_target_number_binary_by_recall(finding_target, finding_numbers, 0, len(finding_numbers) - 1)
print(result)

4. 재귀함수 (Recursion)

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

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

https://en.wikipedia.org/wiki/Recursion_(computer_science)

1) 팩토리얼 구현

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


print(factorial(5))

2) 회문검사

: 주어진 문자열이 좌우 대칭인지 검사

input = "abcbcba"


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


print(is_palindrome(input))


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


print(is_palindrome_recursion(input))

Github

https://github.com/kimphysicsman/nbcamp-algorithm-220726