class Node:
def __init__(self, data):
self.data = data
self.next = None
def __del__(self):
print(f"node({self.data}) is deleted.")
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):
if index < 0:
print("index는 0이상의 값을 입력해주세요.")
return
current_node = self.head
count = 0
while count < index:
current_node = current_node.next
count += 1
return current_node
def add_node(self, index, value):
if index < 0:
print("index는 0이상의 값을 입력해주세요.")
return
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
pre_node = self.get_node(index-1)
new_node.next = pre_node.next
pre_node.next = new_node
def delete_node(self, index):
if index < 0:
print("index는 0이상의 값을 입력해주세요.")
return
if index == 0:
# del_node = self.head
self.head = self.head.next
# del del_node
return
pre_node = self.get_node(index-1)
del_node = pre_node.next
pre_node.next = del_node.next
del del_node
return
linked_list = LinkedList(5)
linked_list.append(10)
linked_list.append(11)
linked_list.append(12)
linked_list.add_node(3, 3)
linked_list.print_all()
print("--------")
linked_list.delete_node(0)
linked_list.print_all()
: 찾고자하는 원소를 정렬된 배열의 중간을 기준으로 범위를 좁혀가며 탐색하는 알고리즘
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).
: 이진탐색은 한번 탐색할 때마다 배열의 범위를 절반으로 줄이기 때문에 시간복잡도가 으로 순차탐색(선형탐색)의 시간복잡도인 보다 낮다.
: 반복적인 방법과 재귀적인 방법 두가지 이용
finding_target = 14.5
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):
start_point = 0
end_point = len(array) - 1
while start_point <= end_point:
avg_point = (start_point + end_point) // 2
if array[avg_point] == target:
return True
if array[avg_point] > target:
end_point = avg_point - 1
elif array[avg_point] < target:
start_point = avg_point + 1
print(start_point, end_point)
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
def is_existing_target_number_binary_by_recall(target, array, start_point, end_point):
print(start_point, end_point)
if start_point > end_point:
return False
avg_point = (start_point + end_point) // 2
if array[avg_point] == target:
return True
if array[avg_point] > target:
return is_existing_target_number_binary_by_recall(target, array, start_point, avg_point - 1)
elif array[avg_point] < target:
return is_existing_target_number_binary_by_recall(target, array, avg_point + 1, end_point)
result = is_existing_target_number_binary_by_recall(finding_target, finding_numbers, 0, len(finding_numbers) - 1)
print(result)
: 자기 자신을 호출하는 함수
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1)
print(factorial(5))
: 주어진 문자열이 좌우 대칭인지 검사
input = "abcbcba"
def is_palindrome(string):
for i in range(int(len(string)/2)):
if string[i] != string[-(i+1)]:
return False
return True
print(is_palindrome(input))
def is_palindrome_recursion(string):
if len(string) <= 1:
return True
if string[0] == string[-1]:
return is_palindrome_recursion(string[1:-1])
else:
return False
print(is_palindrome_recursion(input))