항해99 TIL 1주차 -1

강민범·2023년 10월 16일

점근 표기법

점근 표기법이란 함수의 증가율을 다른 함수와 비교해서 표현하는 방법으로 빅오(Big-O) 표기법과 빅 오메가(Big-Ω) 표기법이 두 종류가 있습니다.

빅오(Big-O) 표기법은 최악의 성능이 나올때 어느정도의 연산량이 걸리는지이고
빅 오메가(Big-Ω) 표기법은 최고의 성능이 나올때 어느정도 연산량이 걸리는지 표시하는것입니다.
요즘 대부분은 빅오(Big-O) 표기법을 대부분 사용하는데요 그 이유로는 최고의 성능을 기대하기 어렵기 때문에 최악의 경우를 대비해야하기 때문입니다.

시간복잡도

시간복잡도란 입력값을 통해 문제를 해결하는 시간을 말합니다.
시간복잡도의 좋은 예로는 입력값이 늘어나도 문제를 해결하는 시간은 그에 비해 덜 늘어나는 코드입니다.

어레이 리스트 vs 연결리스트

어레이리스트의 특징으로는 파이썬의 리스트이고 접근하기 쉽지만 배열의 크기가 유동적이지 않기 때문에 삽입하기가 어렵습니다.

연결리스트의 특징으로는 직접 구현해야하며 접근하기가 어렵지만 삽입하기 쉽다는 장점이 있습니다.

class ListNode:
     def __init__(self, val, next):
         self.val = val
         self.next = next

class LinkedList:
     def __init__(self):
         self.head = None

     def append(self, val): //추가 기능
         if not self.head: //만약 앞의 노드가 없다면
             self.head = ListNode(val,None) //새로운 노드를 하나 생성
         node = self.head 

         while node.next: 
             node = node.next // 리스트의 맨 끝

         node.next = ListNode(val,None) //맨 끝에 도착하면 다음 리스트 생성

팰린드롬

팰린드롬이란?
앞뒤를 뒤집어도 똑같은 단어 또는 문장

def isPalindrome(head):
    arr = []

    if not head:
        return True

    node = head
    while node:
        arr.append(node.val)
        node = node.next

    while len(arr) > 1:
        if arr.pop(0) != arr.pop(): //리스트의 맨 앞과 맨 뒤의 값을 꺼내서 같지 않다면 false를 반환 만약 중간의 두 값까지 값이 같다면 팰린드롬 충족
            return False

    return True