[알고리즘] 스파르타 코딩 : 알고리즘 - 2주차

Array와 Linked List

Array

ㄴ크기가 정해져있어서 한 번 정해지면 바꿀 수 없음

ㄴ즉시 접근 가능 = 상수 시간 내에 접근 가능, O(1)

ㄴ원소를 삽입/삭제하려면 모든 원소를 다 옯겨야 함,  O(N)

ㄴ원소 새로 추가 시 새 공간 할당해야함

 

Linked List

ㄴ크기가 정해지지 않은 데이터 공간

ㄴ연결 고리 따라 원소 접근 가능, O(N)

ㄴ원소 삽입/삭제 시 앞 뒤의 포인터만 변경하면 됨, O(1)

 

	Array	Linked List
특정 원소 조회	O(1)	O(N)
원소 삽입/삭제	O(N)	O(1)
원소 추가	새 메모리 공간 할당	맨 뒤 노드만 동적으로 추가
정리	데이터에 접근하는 경우가 많을 때 사용	삽입/식제하는 경우 많을 때 사용

 

https://www.faceprep.in/data-structures/linked-list-vs-array/

Difference between Linked List and Arrays

 

 

Linked List 구현

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, data):
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        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
            return

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


linked_list = LinkedList(5)
linked_list.append(6)
linked_list.append(7)
linked_list.append(8)
linked_list.add_node(2, 3)
linked_list.add_node(0, 0)
linked_list.print_all()
#print(linked_list.get_node(1).data) # -> 5를 들고 있는 노드를 반환해야 합니다!

---

 

이진 탐색과 순차 탐색

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

# 숫차 탐색
# O(logN)
# 연산량이 반으로 나눠진다 = O(logN)
def is_existing_target_number_binary(target, array):
    cur_min = 0
    cur_max = len(array) - 1
    cur_guess = (cur_max + cur_min) // 2

    while cur_min <= cur_max:
        if array[cur_guess] == target:
            return True
        elif array[cur_guess] < target:
            cur_min = cur_guess + 1
        else:
            cur_max = cur_guess - 1
        cur_guess = (cur_max + cur_min) // 2
    return False

# 순차 탐색
# O(N)
def is_existing_target_number_sequential(target, array):
    find_count = 0
    for number in array:
        find_count += 1
        if target == number:
            print(find_count) # 14!
            return True

    return False


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

---

 

 재귀 함수 : 자기 자신을 부르는 함수

ㄴ탈출 조건 꼬옥!!

 

팩토리얼

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
    if string[0] != string[-1]:
        return False

    return is_palindrome(string[1:-1])


print(is_palindrome(input))

---

숙제

Q1, 링크드 리스트 끝에서 k번째 값 출력하기

    def get_kth_node_from_last(self, k):
        cur_node = self.head
        length = 1
        while cur_node.next is not None:
            length += 1
            cur_node = cur_node.next

        cur_node = self.head
        for i in range(length - k):
            cur_node = cur_node.next

        return cur_node

    def get_kth_node_from_last_2(self, k):
        slow = self.head
        fast = self.head

        for i in range(k):
            fast = fast.next

        while fast is not None:
            slow = slow.next
            fast = fast.next

        return slow

 

Q2, 배달의 민족 배달 가능 여부

배달의 민족 서버 개발자로 입사했다.

상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때,

유저가 ["오뎅", "콜라", "만두"] 를 주문했다.

그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    menus_set = set(menus)
    for order in orders:
        if order not in menus_set:
            return False
        return True


result = is_available_to_order(shop_menus, shop_orders)
print(result)

 

Q3, 더하거나 빼거나

음이 아닌 정수들로 이루어진 배열이 있다.

이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다.

 

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때

숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

numbers = [2, 3, 1]
target_number = 0
result_count = 0  # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(array):  # 탈출조건!
        if current_sum == target:
            global result_count
            result_count += 1  # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
        return
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum - array[current_index])


get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count)  # 2가 반환됩니다!