[TIL] 항해99 83일차

Array와 linked_list

- array

- linked_list

• 자갈칸과 밀가루칸 사이에 흑연칸을 추가하고 싶을때

• 밀가루칸을 버리고 싶을때
  

1. 리스트는 크기가 정해지지 않은 데이터의 공간이다.
   연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있다.
2. 리스트는 특정원소에 접근하려면 연결 고리를 따라 탐색해야 한다.
   최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
   (연결고리 -> 포인터, 화물 칸 -> 노드)
3. 리스트는 원소를 중간에 삽입.삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다.
   따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.
   

이진탐색

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_max + current_min) // 2
    return False


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

재귀함수와 팩토리얼

3! 은 3 2 1 = 6,
4! 는 4 3 2 1 = 4 3! = 24

Factorial(n) = n Factorial(n - 1)
Factorial(n - 1) = (n - 1) Factorial(n - 2)
....
Factorial(1) = 1

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


print(factorial(60))

회문검사

똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미한다.

input = "tomato"


def is_palindrome(string):
    n = len(string)
    for i in range(n):
        if string[i] != string[n-1-i]:
            return False

    return True


print(is_palindrome(input))

• 문자열 자르기
  
  

input = "소주만병만주소"


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