링크드 리스트 수업 각각 20분짜리 2강 듣는 동안, 2시간이 지났다. 오늘 어레이와 링크드 리스트를 새롭게 배웠다. 링크드 리스트는 중반부로 갈수록 재미있다. 예전에 초등학생 때 유행하던 창의력 퀴즈 같은 거 푸는 느낌이다. 완전 기초적인 내용이겠지만 답을 볼 때마다 신기하다.
그렇지만 아직은 공부가 더 많이 필요하다. 중간의 연습문제마다 2분의 생각할 시간을 주는데 30분 넘게 잡고 있어도 실마리 끝만 아른거릴 뿐, 명확한 풀이를 찾지 못했다. 매번 이렇게 간단한 방법이 있었다니 하고 놀라고 있다. 너무 인간의 관점에서 보다 보니, 당연하다고 생각한 부분도 막상 컴퓨터에게 전달하려니 그 과정이 어렵다.
기존의 강의와 달리 알고리즘 강의는 총 수강 시간이 엄청 오래 걸렸다. 새로운 개념을 배워서 그런 것도 있지만, 아무래도 직접 문제를 몇십 분이고 고민하다 보니 진도가 계속 늘어지고 있다. 아직 기초를 쌓는 단계니까 더 문제도 많이 풀어보고 열심히 해보자. 화이팅~
class Person:
pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미
person_1 = Person() # person_1에 클래스를 통한 새로운 객체를 만들겠다.
print(person_1) # <__main__.Person object at 0x1090c76d0>, Person 이라는 클래스에 객체가 생성되었다. 주소값으로 분류.
person_2 = Person()
print(person_2) # <__main__.Person object at 0x1034354f0>
생성자: 생성 시 호출되는 함수.
클래스의 생성자(Constructor): 객체 생성 시 데이터 입력, 또는 내부적으로 원하는 행동을 실행해준다.
파이썬 생성자 함수 이름: _init_ 으로 고정됨.
self: 객체 자신을 가리킴. 따로 파라미터 넣지 않고 self 로 호출하면 알아서 self 에 자기자신 입력.
constructor 생성, 내부에 있는 함수를 만들 때 인자에 자기 자신을 넘겨주는 것임.
self 로 객체에 데이터 쌓기 가능. self.name = param_name # 자기자신 객체의 name 변수에 입력됨.
클래스를 이용하면 유사한 행동, 데이터를 쌓을 수 있게 구조를 쉽게 만들 수 있음. 틀 같은 느낌.
메소드(method): 클래스 내부의 함수
클래스 이용하면 연관성 있는 데이터들을 클래스 내에서 관리 가능, 다양한 객체들의 쉬운 생성 가능.
class Person:
def __init__(self, param_name):
print("i am created!", self)
self.name = param_name # 자기 자신에게 param_name 을 저장하겠다.
# 메소드: 클래스 내부의 함수. ex) 우리는 talk 메소드를 만든 거야.
def talk(self): # self는 항상 존재해야 함.
print("안녕하세요, 제 이름은", self.name, "입니다.")
person_1 = Person("유재석") # () == __init__()
print(person_1.name)
print(person_1)
person_1.talk()
person_2 = Person("박명수")
print(person_2.name)
print(person_2)
person_2.talk()
노드가 필요한 정보 2가지: 1) 칸에 있는 데이터(ex. 기관실, 자갈), 2) 다음 칸의 정보 (포인터)
두 가지 데이터를 가지고 있어야 하므로, 클래스를 이용하여 해결한다.
## 01.
class Node:
def __init__(self, data):
self.data = data # 3이 저장되고,
self.next = None # 현재 다음 노드를 가리키는 포인터는 아무 것도 가리키지 않는 상태
# 다음 포인터를 지목하지 않으면 연결되지 않는다.
node= Node(3)
print(node)
## 02.
first_node = Node(5) # 현재는 next 없이 하나의 노드만 있음. [5]
second_node = Node(12) # [12]를 들고 있는 노드 하나 생성.
first_node.next = second_node # [5]의 next를 [12]로 지정함. [5] -> [12]
## 03.
# 노드를 계속 연결해주려면 매번 쳐야 하는가? 아니다.
# 이럴 때 클래스를 이용해서 반복행동을 간단하게 해준다. #04에 이어서.
class Node:
def __init__(self, data):
self.data = data
self.next = None
node = Node(3) # [3]
first_node = Node(4) # [4]
node.next = first_node
print(node.next.data)
## 04.
# LinkedList 라는 클래스를 만드는데, 딱 head node 만 들고 있음. (맨 앞 칸만 저장함)
# 1. LinkedList 는 self.head에 시작하는 노드를 저장한다.
# 2. 다음 노드를 보려면 각 노드의 next를 조회해서 찾아가야 함.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, data):
self.head = Node(data)
# LinkedList 끝에 새로운 노드를 붙이고 싶다면, head 노드를 따라 맨 뒤까지 이동 필요.
# 맨 끝 노드는 next가 None 이므로 while 문 사용.
# 예외처리: self.head가 None 인 경우.
def append(self, data):
if self.head is None:
self.head = Node(data)
return # 함수 종료
cur = self.head
while cur.next is not None:
cur = cur.next
print("cur is ", cur.data)
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
02. [실습] 링크드 리스트 모든 원소 출력
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, data):
self.head = Node(data)
def append(self, data):
if self.head is None:
self.head = Node(data)
return # 함수 종료
cur = self.head
while cur.next is not None:
cur = cur.next
# print("cur is ", cur.data)
cur.next = Node(data)
def print_all(self):
cur = self.head # 맨 처음 cur의 위치는 head
while cur is not None: # 마지막 None이 아닐 때까지 이동
print(cur.data) # 하나씩 출력해준다.
cur = cur.next
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all() # 3, 4, 5 출력됨
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
## 링크드 리스트 원소 찾기: 링크드 리스트에서 index번째 원소 반환하기
def get_node(self, index):
# index = next node로 가는 것을 n번 하는 것.
node = self.head # 맨 처음 시작점
count = 0 # 인덱스만큼 이동하는 횟수
while count < index: # 인덱스보다 작으면 계속 이동
node = node.next
count += 1
return node # index와 같아지면 그곳의 node 반환
## 링크들 리스트 원소 추가: index번째 원소를 추가하시오
def add_node(self, index, value):
new_node = Node(value) # [6], 새로운 값
if index == 0:
new_node.next = self.head # [6] -> [5]
self.head = new_node # head -> [6] -> [5] -> ...
return
node = self.get_node(index-1) # [5]. 같은 클래스 내의 함수 호출 가능, index번째의 요소 가져오기
# index - 1 을 해야지 index 번째에 추가 가능하다.
# -1 이라는 코드가 있다면 0에 대한 예외처리 해야 함.
next_node = node.next # [12], 기존 노드의 다음 칸을 미리 저장해둔다.
node.next = new_node # [5] -> [6]
new_node.next = next_node # [6] -> [12]
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!
linked_list.add_node(1, 6)
linked_list.print_all()
02. [실습] 링크드 리스트 원소 삭제
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
## 링크드 리스트 원소 찾기: 링크드 리스트에서 index번째 원소 반환하기
def get_node(self, index):
# index = next node로 가는 것을 n번 하는 것.
node = self.head # 맨 처음 시작점
count = 0 # 인덱스만큼 이동하는 횟수
while count < index: # 인덱스보다 작으면 계속 이동
node = node.next
count += 1
return node # index와 같아지면 그곳의 node 반환
## 링크들 리스트 원소 추가: index번째 원소를 추가하시오
def add_node(self, index, value):
new_node = Node(value) # [6], 새로운 값
if index == 0:
new_node.next = self.head # [6] -> [5]
self.head = new_node # head -> [6] -> [5] -> ...
return
node = self.get_node(index-1) # [5]. 같은 클래스 내의 함수 호출 가능, index번째의 요소 가져오기
# index - 1 을 해야지 index 번째에 추가 가능하다.
# -1 이라는 코드가 있다면 0에 대한 예외처리 해야 함.
next_node = node.next # [12], 기존 노드의 다음 칸을 미리 저장해둔다.
node.next = new_node # [5] -> [6]
new_node.next = next_node # [6] -> [12]
## 링크드 리스트 원소 삭제: 링크드 리스트에서 index번째 원소 제거하기
def delete_node(self, index):
if index == 0:
self.head = self.head.next # 아예 헤드 날려버리기
return # 밑의 코드를 호출하지 않도록 return
node = self.get_node(index-1)
node.next = node.next.next # 간단!
return
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!
linked_list.add_node(1, 6)
linked_list.delete_node(1)
linked_list.print_all() # 얘는 제일 마지막으로.
1. 한 바퀴 돌면서 길이를 알아낸 다음, 그 길이에서 k만큼을 뺀 순서의 노드를 반환한다.
def get_kth_node_from_last(self, k):
length = 1
cur = self.head
while cur.next is not None:
cur = cur.next
length += 1
end_length = length = k
cur = self.head
for i in range(end_length):
cur = cur.next
return cur
2. k만큼의 길이가 떨어진 포인터 2개를 두고, 끝의 노드가 마지막에 도달하면 k번째 노드도 반환 가능.
def get_kth_node_from_last(self, k):
slow = self.head
fast = self.head
for i in range(k):
fast = fast.next
while fast is not None:
slow = slow.next
fast = fast.next
return slow
그렇지만 결국 링크드리스트 끝까지 가야하므로 시간복잡도는 둘 다 O(N)으로 동일.
두 번째 방법은 두 개의 공간값을 가지고 이동해야하므로 연산량도 첫 번째와 비슷하게 사용함.
따라서 두 번 도는 첫 번째 방법보다, 한 번 도는 두 번째 방식이 무조건 빠른 건 아님.
def is_available_to_order(menus, orders):
menus.sort()
for order in orders:
if not is_existing_target_number_binary(order, menus):
return False
return True
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
return False
2. 정렬할 필요 없이, 집합 자료형 사용하면 쉽게 해결됨.
시간복잡도: menus → menus_set, O(N) (orders 길이: N)
집합 내에서 탐색 시간복잡도는 O(1), 주문 개수 M만큼 반복하므로 O(M)의 연산이 필요함.
따라서, 총 O(M+N)의 시간복잡도가 소요됨.
def is_available_to_order(menus, orders):
menus_set = set(menus)
for order in orders:
if order not in menus_set:
return False
return True
in 연산자는 어떤 자료형을 탐색하느냐에 따라 시간복잡도의 차이가 발생한다.
ex) list는 O(N), set에 대한 in 연산은 O(1)의 시간복잡도로 처리함.
03. [실습] 더하거나 빼거나
numbers = [1, 1, 1, 1, 1], target_number = 3, 더하기와 빼기로 타겟넘버 만드는 경우의 수를 반환하라.
하나씩 원소를 추가할 때마다, 새로 추가된 원소를 더하고 빼는 경우의 수를 추가하면 된다.
## 모든 경우의 수를 출력하는 방법
numbers = [2, 3, 1]
target_number = 0
result = [] # 모든 경우의 수를 담기 위한 배열
def get_all_ways_to_by_doing_plus_or_minus(array, current_index, current_sum, all_ways):
if current_index == len(array): # 탈출조건!
all_ways.append(current_sum) # 마지막 인덱스에 다다랐을 때 합계를 추가해주면 됩니다.
return
get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index], all_ways)
get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index], all_ways)
get_all_ways_to_by_doing_plus_or_minus(numbers, 0, 0, result)
print(result)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
# 모든 경우의 수가 출력됩니다!
# [6, 4, 0, -2, 2, 0, -4, -6]
## 경우의 수를 구하는 법
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):
if current_index == len(array): # 탈출조건!
if current_sum == target:
global result_count
result_count += 1 # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
return
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) # 5가 반환됩니다!
