내일배움캠프 AI, 14일차 TIL - 2022.09.19

스파르타 코딩클럽 내일배움캠프 AI 웹개발자양성과정 3회차

2022.09.19. 14일차 - TIL

 

 

1. 알고리즘, 자료구조 강의

• Array : 크기가 정해진 연속된 데이터 공간, 데이터 접근이 빠르며(O(1)) 데이터 추가 시 모든 공간이 다 찼다면 새로운 공간을 할당하고, 중간에 요소 삽입/삭제가 어렵다(O(n)) -> 모든 요소를 이동시켜야 한다
• Linked List: 크기가 정해지지 않은 데이터 공간, 삽입과 삭제가 빈번한 문제에 사용하기 좋으며 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가 가능하다. 특정 데이터 조회에 O(n)의 시간이 필요하다.
• 파이썬의 list는 내부적으로 동적 배열을 사용해 배열, 링크드 리스트 모두로 사용 가능
• linked list 구현

# 노드 클래스 정의
class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None
        
# 링크드 리스트 클래스 정의
class LinkedList:
	# 받은 값으로 노드를 생성하고, head에 저장
	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)  # 받은 값으로 노드를 생성하고, 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)  # 새로운 노드 생성
        # index - 1 이 0이 될 경우의 예외 처리
        if index == 0:
        	new_node.next = self.head
                self.head = new_node
                return
            
        node = self.get_node(index - 1)  # 삽입을 원하는 위치의 노드 가져오기
        next_node = node.next  # 해당 노드의 next값을 따로 저장
        node.next = new_node  # 이전 노드가 가지고 있던 다음 노드를 가져와
        new_node.next = next_node  # 새로운 노드의 next에 추가
        
    # 링크드 리스트 원소 삭제 메소드
    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
        
     
        
    # 링크드 리스트 전체 출력 메소드
    def print_all(self):
    	cur = self.head
        while cur is not None:
        	print(cur.data)
                cur = cur.next

• 순차탐색 : 처음부터 하나씩 수를 비교해 값을 찾는다. -> O(n)
• 이진탐색 : 정렬된 수에서 중간값과 비교해 값이 크면 우측에서, 값이 작으면 좌측에서 다시 탐색 반복 -> O(logn)

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)

• 재귀함수 : 자기 자신을 호출하는 함수, 반드시 빠져나가는 지점을 명확히 정해줘야 한다.
• 팩토리얼

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


print(factorial(60))

• 회문 검사(앞으로 읽으나 뒤로 읽으나)

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

• 2주차 과제

# 문제 1: 링크드 리스트의 끝에서 k번째 값을 반환하시오.

# 노드 클래스 선언
class Node:
    def __init__(self, arg_data):
        self.data = arg_data  # 노드 값 저장
        self.next = None  # 다음 노드를 가리킬 지표


# 링크드 클래스 선언
class LinkedList:
    # 먼저 노드 클래스 생성 후 head에 저장
    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_kth_node_from_last(self, k):
        # 방법1) 리스트의 길이를 구해 위치 구하기
        length = 1
        cur = self.head

        # linked의 길이를 알기 위한 반복문
        while cur.next is not None:
            cur = cur.next
            length += 1
        end_length = length - k  # 구하고자 하는 인덱스의 (앞에서의) 위치
        cur = self.head
        for _ in range(end_length):
            cur = cur.next
        return cur
        
        '''방법2) k만큼 떨어진 포인터 두개 설정(slow와 fast)
        slow = self.head
        fast = self.head

        # k만큼 떨어진 곳에 fast 위치
        for i in range(k):
            fast = fast.next

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

        return slow
        '''

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

print(linked_list.get_kth_node_from_last(2).data)  # 7이 나와야 합니다!

# 문제 2: 현재 주문 가능한 상태인지 확인
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]

'''방법1) 정렬 후 이진탐색
def is_available_to_order(menus, orders):
    menus.sort()  # menus 정렬!
    for order in orders:
        # 주문이 메뉴에 없으면 False 리턴
        if not is_existing_target_number_binary(order, menus):
            return False
    return True

# 이진 탐색 함수
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
'''

# 방법 2) 집합으로 바꿔 in 으로 확인
def is_available_to_order(menus, orders):
    menu_set = set(menus)
    for order in orders:
        if order not in menu_set:
            return False
    return True


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

# 문제 3: 음이 아닌 정수 배열이 있을 때 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 할 때 방법의 수를 반환
# n 길이의 배열에서 더하거나 뺀 경우의 수는 n-1 길이의 배열에서 마지막 원소를 더하거나 뺀 경우의 수를 추가
numbers = [1, 1, 1, 1, 1]
target_number = 3
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):  # 탈출 조건 -> 현재 인덱스가 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])
    
    return 5


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)

 

• 버블 정렬 : 첫 번째와 두 번째, 두 번째와 세 번째, 세 번째와 네 번째, .. , (마지막-1)와 마지막 자료를 비교하며 교환해 자료를 정렬하는 방법
  -> 오름차순의 경우 1단계로 끝까지 도달하면 가장 우측에 가장 큰 수가 위치, 내림차순의 경우 1단계로 끝까지 도달하면 가장 우측에 가장 작은 수가 위치
  -> O(n^2) 시간

# 1단계 : [4, 2, 6, 1, 9] -> [0]과 [1] 비교, [1]과 [2] 비교, [2]와 [3] 비교, [3]과 [4] 비교(이때 큰 값을 오른쪽에 위치시킴)
# 2단계 : [2, 4, 1, 6, 9] -> [0]과 [1] 비교, [1]과 [2] 비교, [2]와 [3] 비교(이때 큰 값을 오른쪽에 위치시킴)
# 3단계 : [2, 1, 4, 6, 9] -> [0]과 [1] 비교, [1]과 [2] 비교(이때 큰 값을 오른쪽에 위치시킴)
# 4단계 : [1, 2, 4, 6, 9] -> [0]과 [1] 비교(이때 큰 값을 오른쪽에 위치시킴)

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
	n = len(array)
    for i in range(n-1):
    	for j in range(n-i-1):
        	if array[j] > array[j+1]:
            	array[j], array[j+1] = array[j+1], array[j]
    	
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

• 선택 정렬 : 가장 큰 값 또는 가장 작은 값을 선택해 가장 앞에 위치시키는 방법 -> O(n^2) 시간

# 1 단계 : [1, 6, 2, 9, 4] -> [0]과 [1] 비교, [1]과 [2] 비교, [2]와 [3] 비교 후 가장 작은 수 1과 [0] 위치에 있는 수 swap
# 2 단계 : [1, 2, 6, 9, 4] -> [1]과 [2] 비교, [2]와 [3] 비교 후 가장 작은 수 2와 [1] 위치에 있는 수 swap
# 3 단계 : [1, 2, 4, 9, 6] -> [2]와 [3] 비교 후 가장 작은 수 4와 [2] 위치에 있는 수 swap
# 4 단계 : [1, 2, 4, 6, 9] -> [3]와 [4] 비교 후 가장 작은 수 6와 [3] 위치에 있는 수 swap

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n-1):
    	min_index = i
        for j in range(n - i):
        	if array[i+j] < array[min_index]:
            	   min_index = i+j
        array[i], array[min_index] = array[min_index], array[i]
        
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

• 삽입 정렬 : 특정 원소를 정렬된 원소들 사이에 삽입하는 방법 -> O(n^2) 시간, but 최선은 n

# 원래 : [4, 6, 2, 9, 1]
# 1단계 : [4, 6, 2, 9, 1] -> [0]은 정렬된 것으로 보고, [1]을 [0]과 비교([0]보다 [1]의 값이 크기 때문에 그대로 둔다.)
# 2단계 : [2, 4, 6, 9, 1] -> [1]까지 정렬된 것으로 보고, [2]을 [1]과 비교해 값이 작으면 서로의 위치 변경, [1]을 [0]과 비교해 값이 작으면 서로 위치 변경
# 3단계 : [2, 4, 6, 9, 1] -> [2]까지 정렬된 것으로 보고, [3]을 [2]와 비교([2]보다 [3]의 값이 크기 때문에 그대로 둔다.)
# 4단계 : [1, 2, 4, 6, 9] -> [3]까지 정렬된 것으로 보고, [4]를 [3]과 비교해 값이 작으면 서로의 위치 변경, [3]를 [2]과 비교해 값이 작으면 서로의 위치 변경, [2]를 [1]과 비교해 값이 작으면 서로의 위치 변경, [1]를 [0]과 비교해 값이 작으면 서로의 위치 변경

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
    	for j in range(i):
        	if array[i-j-1] > array[i-j]:
            	array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
            else:
            	break
    return array


insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))