배열(Array)
같은 타입의 변수들로 이루어진 유한 집합
링크드 리스트(Linked List)
- Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.
- Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가진다.
- Head : 링크드리스트에서 가장 시작점인 데이터를 의미한다.
- Tail : 링크드리스트에서 가장 마지막 데이터를 의미
- Next=None(또는 Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다.
- 링크드 리스트의 장단점
1) 장점
- 배열은 미리 데이터 공간을 할당해야 하지만 링크드리스트는 미리 할당할 필요가 없다.(유동적으로 데이터 추가,삭제 가능)
- 링크드리스트 수정시 시간복잡도 O(1)을 갖는다.
: 항상 일정한 속도
2) 단점
- 위 구조에서 보듯이 다음 데이터를 연결하기 위해선 별도의 주소 공간을 가져야 한다.
: 저장공간 효율이 높지 않음
- 배열은 인덱스를 통해 데이터에 접근하므로 시간복잡도 O(1)을 갖지만 링크드리스트의 경우 O(n)을 갖는다. 즉, 연결 된 정보를
찾기 위해 주소를 확인하고 다음 데이터를 탐색하는 시간이 있기 때문에 접근 속도가 느리다.
- 중간데이터를 삭제시, 앞뒤 데이터를 연결하고 재구성하는 코드가 추가로 필요하다.
링크드리스트 파이썬 구현
- Node 선언
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다 [3]- Node 연결하기
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head 에 시작하는 Node 를 연결합니다.
linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력됩니다!
# 현재 LinkedList 는 (5) 만 존재합니다!- Node 삭제
# Node에 데이터 할당 및 next에 None
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 할당
cur = self.head
# cur.next 뒤에 None이 없을때 cur에 cur.next를 할당하고 cur.next에 Node(value) 할당
# cur.next에 있던 데이터를 cur에 옮기고 그 cur의 next에 새로운 Node를 할당하는 것
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
# cur이 None이 아닐때 cur.data를 출력하고 cur을 cur.next에 할당
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
# node 에 head를 할당하고 인덱스보다 count가 작으면 node 다음번으로 넘어가고 count +1
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, data):
new_node = Node(data) # [6]
if index == 0:
new_node.next = self.head # [6]
self.head = new_node # head -> [6] -> [5]
return
node = self.get_node(index - 1) # [5]
next_node = node.next # [12]
node.next = new_node # [5] -> [6]
new_node.next = next_node # [6] -> [12]
def delete_node(self, index):
# index가 0이면 self.head에 다음 노드를 할당하고 리턴
if index == 0:
self.head = self.head.next
return
# node에 get_node(index - 1)을 할당 (기존 node는 지워짐)
# node.next에 node.next.next를 할당
node = self.get_node(index - 1)
node.next = node.next.next
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
print(linked_list.get_node(0).data)
linked_list.add_node(1, 6)
linked_list.delete_node(0)
linked_list.print_all()
링크드 리스트 문제
- 두 링크드 리스트 합 계산
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):
sum_1 = _get_linked_list_sum(linked_list_1)
sum_2 = _get_linked_list_sum(linked_list_2)
print(sum_1)
print(sum_2)
return sum_1 + sum_2
def _get_linked_list_sum(linked_list):
sum = 0
head = linked_list.head
# head가 None이 아닐때까지 sum에 sum *10 + head.data를 하고 head에 다음 Node를 할당
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))
이진 탐색
이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
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):
min = 0
# array의 길이 - 1
max = len(array) - 1
# finding numbers를 반으로 나누기 위해 (min + max) 나누기 2를 하고 소수점 이하의 수를 모두 버린다
# 시도값 == guess
guess = (min + max) // 2
# min이 max 이하일때
while min <= max:
# array[guess]가 target과 일치한다면 True
if array[guess] == target:
return True
# array[guess]가 target보다 작다면
elif array[guess] < target:
# min에 guess + 1을하고
min = guess + 1
else:
# array[guess]가 target보다 크다면 max에 guess -1을 할당한다
max = guess - 1
# 그 후 guess 에 (max+min)의 2를 나누고 소수점 이하를 버린다
guess = (max + min) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
재귀 함수
함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다(구현은 만들다와 같은 뜻입니다). 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다.
- Q. 60에서 0까지 숫자를 출력하시오.
def count_down(number):
if number < 0:
return
# number를 출력하고
print(number)
# count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(number - 1)
count_down(60)- 팩토리얼
팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다
def factorial(n):
# 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다
# n 이 1이라면 1을 리턴하고
if n == 1:
return 1
# 5 * 4 * 3 * 2 * 1
return n * factorial(n - 1)
print(factorial(5))- 회문 검사
똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장
- Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오
input = "abcba"
def is_palindrome(string):
# n에 string의 길이를 할당한다
n = len(string)
# n의 길이만큼 i에 할당하고 for문을 돌린다
for i in range(n):
# string[i] 가 string[n - 1 - i](끝글자 - i)와 같지 않다면 False를 반환한다
if string[i] != string[n - 1 - i]:
return False
# 그것이 아니라면 True를 반환한다
return True
print(is_palindrome(input))- 회문 검사 - 재귀함수
input = "abcba"
def is_palindrome(string):
# string의 길이가 1 이하라면 True를 반환한다
if len(string) <= 1:
return True
# string의 0번째 배열이 string의 마지막 배열과 같지않다면 False를 반환한다
if string[0] != string[-1]:
return False
# 반환이 다 되었기 때문에 다시 함수를 불러서 string의 첫번째 배열과 마지막 배열을 비교한다
return is_palindrome(string[1:-1])
print(is_palindrome(input))
2주차 숙제
- 링크드 리스트 끝에서 K 번째 값 출력하기
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_kth_node_from_last(self, k):
length = 1
cur = self.head
# cur의 length 를 구하기 위한 함수
# cur.next 가 None이 아니라면 cur에 cur.next를 할당하고 length에 +1을 한다 그리고 end_length에 length - k를 할당한다
while cur.next is not None:
cur = cur.next
length += 1
end_length = length - k
# 그 후 cur 을 end_length 만큼 돌린 후 cur을 리턴한다.
cur = self.head
for i in range(end_length):
cur = cur.next
return cur
linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)
linked_list.append(9)
print(linked_list.get_kth_node_from_last(1).data) # 7이 나와야 합니다!- 배달의 민족 배달 가능 여부
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
# menus를 집합 자료형으로 변환하여 menus_set에 할당
menus_set = set(menus)
# order가 menus_set에 없으면 False 다 있다면 True를 반환한다
for order in orders:
if order not in menus_set:
return False
return True
result = is_available_to_order(shop_menus, shop_orders)
print(result)- 더하거나 빼거나
numbers = [1, 1, 1, 1, 1]
target_number = 3
result_count = 0 # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
# curr index가 array의 길이와 같다면
if current_index == len(array):
# curr sum이 target과 같다면
if current_sum == target:
# result count를 글로벌하게 영향을 줄 수 있게 하고 +1을 한다
global result_count
result_count += 1
return
# 다시 함수를 출하되 curr sum + array[curr index]한 함수와 curr sum - array[curr index]한 함수를 호출한다
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum + array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum - array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count)