링크드 리스트에서 원하는 원소 찾기
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):
node = self.head
count = 0
while count < index:
node = next.node
count += 1
return node
linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!: index번째 원소를 찾는다는 뜻은 index번 만큼 next.node 이동한다는 의미
링크드 리스트 원소 추가하기
[기관실] -> [자갈] -> [밀가루]
[흑연]
: 기관실과 자갈 사이에 흑연을 넣고 싶다면
기관실의 포인터를 끊고, 자갈의 데이터를 임시로 저장해야한다.
자갈을 next_node라는 변수에 저장, 추가하는 흑연을 new_node에 저장
index.next = new_node
new_node.next = next_node링크드 리스트 연습문제
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 get_linked_list_sum(linked_list_1, linked_list_2): # 각 링크드리스트의 모든 숫자를 문자열로 나열한 후 int로 바꿔서 각 값을 더한다.
sum_1 = 0
head_1 = linked_list_1.head
while head_1 is not None:
sum_1 = sum_1 * 10 + head_1.data
head_1 = head_1.next
sum_2 = 0
head_2 = linked_list_2.head
while head_2 is not None:
sum_2 = sum_2 * 10 + head_2.data
head_2 = head_2.next
return (sum_1+sum_2)
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2)): 1032
하지만, sum_1과 sum_2는 중복되는 함수이다
잘 짜여진 코드는 중복되지 않아야 하므로 함수로 쪼갠다.
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 get_linked_list_sum(linked_list_1, linked_list_2): # 각 링크드리스트의 모든 숫자를 문자열로 나열한 후 int로 바꿔서 각 값을 더한다.
sum_1 = _get_linked_list_sum(linked_list_1)
sum_2 = _get_linked_list_sum(linked_list_2)
return (sum_1 + sum_2)
def _get_linked_list_sum(linked_list):
sum = 0
head = linked_list.head
while head is not None:
sum = sum * 10 + head.data
head = head.next
return sum
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2))
: 보다 짧은 코드로 같은 기능을 구현 할 수 있다.
만약 코드에 노랑색 물결 밑줄이 있을 경우
위에 코드에서는 'sum'이라는 변수에 노랑색 물결 밑줄이 그어져있는데,
'sum' 이라는 함수가 파이썬에서 이미 구현되어있어 충돌의 위험 때문에 다른 변수의 이름을 사용하길 권장한다는 뜻.
아래와 같이 'sum'을 특정지어서 'linked_list_sum'으로 변경.
def _get_linked_list_sum(linked_list):
linked_list_sum = 0
head = linked_list.head
while head is not None:
linked_list_sum = linked_list_sum * 10 + head.data
head = head.next
return linked_list_sum이진 탐색 & 순차 탐색
이진 탐색(binary)
: 값을 찾기 위해 반으로 나눠서 탐색. ex) up&down 게임
중간의 값을 찾으려면 /2를 해야 하지만, 소수점이 나올 수 있으므로
>>> print((4 + 5) / 2)
4.5
>>> print((4 + 5) // 2)
4'/' 대신 '//'을 사용하여 소수점을 버리게 한다.
target이 배열 안에 들어가 있다면 True를, 없다면 False를 반환하라.
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):
# 구현해보세요!
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result): 문제 방향성 잡기
1. 배열에서 최솟값과 최댓값을 더하고 2로 나누어 소수점을 버린다.
2. 그 값이 타겟과 같은지 확인하고, 아니라면 범위를 줄인다.
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):
curr_min = 0
curr_max = len(array) - 1
curr_guess = (curr_min + curr_max) // 2
while curr_min <= curr_max:
if array[curr_guess] == target:
return True
elif array[curr_guess] < target:
curr_min = curr_guess + 1
else:
curr_max = curr_guess - 1
curr_guess = (curr_min + curr_max) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)이진 탐색의 시간복잡도 계산하기
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_sequential(target, array):
find_count = 0
for number in array:
find_count += 1
if target == number:
print(find_count) # 14!
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result) # True: 14, True
: O(N) 만큼의 시간 복잡도를 가진다.
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):
curr_min = 0
curr_max = len(array) - 1
curr_guess = (curr_min + curr_max) // 2
find_count = 0
while curr_min <= curr_max:
find_count += 1
if array[curr_guess] == target:
print(find_count)
return True
elif array[curr_guess] < target:
curr_min = curr_guess + 1
else:
curr_max = curr_guess - 1
curr_guess = (curr_min + curr_max) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result): 3, True
: O(logN) 만큼의 시간 복잡도를 가진다.
이진 탐색 연습문제 - 무작위 수 찾기
finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]
def is_exist_target_number_binary(target, numbers):
# 이 부분을 채워보세요!
return 1
result = is_exist_target_number_binary(finding_target, finding_numbers)
print(result): 위 숫자의 배열은 이진 탐색이 불가능하다.
일정한 규칙으로 배열되어 있는 데이터만 이진 탐색이 가능하다.
정렬하는 방법은 다음주에 알랴줌....
재귀 함수
재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. [위키백과]
재귀 함수 : 자기 자신을 호출하는 함수, 간결하고 효율성 있는 코드를 작성 가능하다.
재귀 함수 연습 문제 1 - 보신각 카운트다운
def count_down(number):
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60): count_down 함수 안에 count_down이 또 있다. -> 재귀 함수 -> 계속해서 호출(반복)
우리는 0 까지의 값만 원하지만, 위 값에서 제한이 없으므로 -값 밑으로 게속 내려감
어느 시점에서 재귀 함수가 끝나는지 정의해 줘야 한다.(탈출조건)
def count_down(number):
if number < 0:
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60): 60 59 58 ... 2 1 0
재귀 함수 연습 문제 2 - 팩토리얼
5!의 결과값을 출력하라.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5))
: 120
재귀 함수 연습 문제 3 - 회문 검사
회문 : 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장
ex) 토마토, 오디오, 소주만병만주소
-> 문자열을 보고 회문인지 확인하는 방법
다음 문자열이 회문인지 True or False로 표현해라
input = "abcba"참고 기능
"가나다라마바사"[1:5]
-> '나다라마' // 앞에서 첫번째 ~ 앞에서 다섯번째 단어를 자르고 출력
"가나다라마바사"[1:-1]
-> '나다라마바' // 앞, 뒤에서 첫번 째 단어를 자르고 출력
input = "abcba"
def is_palindrome(string):
if len(string) <= 1: # 만약, 문자열의 길이가 1보다 작거나 같다면
return True # True를 반환해준다. "c"만 남더라도 회문이기 때문, indexError가 나기 때문에 꼭 넣어줘야 한다.
if string[0] != string[-1]:
return False
return is_palindrome(string[1:-1])
print(is_palindrome(input))
: True
-. 재귀 함수를 활용하기 위해선 문제가 축소되는 특징이 보여야 한다.
-. 특정 구조가 반복되는 모습이 보이면 활용 가능
-. 재귀 함수를 사용 할 때는 반드시 탈출 조건을 작성해야 한다.
