11 TIL

 

기다리던 주말이 왔는데 행복하지 않네요.. 알고리즘을 학원이 제시하는 범위까지

진도를 못나가서 요번 주말은 반납입니다.. 허허 그래도 계속 보니 뭔가 알거 같기도 하네요

자꾸 까먹는 range, len과 이론 정리, 배운 예제 1개씩 소개하며 마치겠습니다. 

 

range, len

range() 함수 : for문과 함께 자주 사용되는 함수로 입력받은 숫자에 해당하는 범위의 값을

                  반복 가능한 객체로 만들어 돌려줌

len() 함수    : 리스트 안의 요소 개수를 돌려줌

for in range : 순회할 횟수가 정해져 있을 때 사용함

 

시간 복잡도
입력값과 문제를 해결하는데 걸리는 시간과 상관관계
입력값이 2배로 늘어났을때 문젤르 해결하는데 걸리는 시간은 몇배로 늘어나는지 보는것
예) 각줄이 실행된느걸 1번의 연산이 된다고 생각하고 계산

공간 복잡도란
시간 복잡도란 유사하지만 연산에서 공간으로 변경됨
보통은 경우 공간의 의해서 결정되지 않고 시간 복잡도를 더 신경씀

예) 저장하는 데이터의 양이 1개의 공간을 사용한다 생각하고 계산

 

점근 표기법 
알고리즘의 성능을 수학적으로 표기하는 방법
최악을 경우를 대비해야하기 때문에 모든 알고리즘을 빅오 표기법으로 분석 
최악 = 빅오 O(@), 최고 = 빅오메가 Ω(@)

 

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):           # 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)          # 새로운 node
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1) # index 번째 node, index 다음에 올 노드를 추가하려면 -1
        next_node = node.next           # 밀리는 노드가 사라질 수 있기에 미리 저장, Node(index).next
        node.next = new_node            # Node(index) -> new_node
        new_node.next = next_node       # new_node[밀가루] -> next_node

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next  # 0번째 head를 삭제하니거니 head.next로 정의하고 아래 식이 안돌아가게 retrun
            return

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

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()
linked_list.delete_node(0)
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_binary(target, array):
    current_min = 0                                     # 초기화
    current_max = len(array) - 1                        # array 마지막 수 
    current_guess = (current_min + current_max) // 2    # 최속값과 최대값 2로 나누고 몫 값만 취함

    while current_min <= current_max:                   
        if array[current_guess] == target:              # target 값과 같은면 True 반환
            return True
        elif array[current_guess] < target:             # target 보다 적을 때 
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1             # 그 외 
        current_guess = (current_max + current_min) // 2# while문 마저 돌려 정확한 값을 찾기 위해 guess 값 반환
    return False


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