수업목표
- 어레이와 링크드리스트에 대해 배우고 차이점을 익힌다.
- 이진 탐색의 효율성과 전제 조건에 대해 배운다.
- 재귀함수의 방법과 전제 조건에 대해 배운다.
어레이와 링크드 리스트
- 어레이 : 크기가 정해진 저장 공간
배열은 각 방에 접근할 수 있다. rooms[0]
- 데이터 추가 시 모든 공간이 다 차면 새로운 메모리 공간을 만들어야 함.
- 데이터에 접근하는 경우가 빈번하다면 어레이 사용하는게 좋음 - 링크드 리스트 : 크기가 정해져 있지 않은 저장 공간
- 리스트는 특정 원소에 접근하려면 연결 고리를 탐색 해야 한다. 그래서 O(N)이라는 시간 복잡도를 가진다.
- 모든 공간이 다 차도 뒤에 노드를 연결해서 추가할 수 있다.
- 삽입과 삭제 시 더 유리하다
클래스
클래스는 분류, 집합 같은 속성과 기능을 가진 객체를 말하는 것이다.
class Person:
pass # 여기서 pass 는 안에 아무런 내용이 없다는 의미입니다!
person_1 = Person()
print(person_1) # <__main__.Person object at 0x1090c76d0> => 공간의 주소
person_2 = Person()
print(person_2) # <__main__.Person object at 0x1034354f0>생성자 : 객체를 만들 때 쓰는 함수
def __init__(self):
print("hihihi", self)위 함수는 클래스가 처음 생성될 때 작동하는 함수이다. 생성자가 처음 생성될 때 __init__ 안에 있는 내용이 실행된다.
여기서 self는 자기 자신을 넘겨준다는 의미이다. (항상 self는 존재해야 한다.)
Person 클래스 코드를 보면, 밑에서 Person() 이렇게 생성자를 실행하는 코드를 볼 수 있는데, 이 코드는 __init__() 함수와 동일한 모습을 취해야 한다. 그래서 __init__()에 self이외의 인자를 받겠다면, 생성자의 인자 자리에도 클래스 생성시 넘겨주어야 하는 인자가 생겨야 한다.
class Person:
def __init__(self, param_name):
print("hihihi", self)
self.name = param_name
person_1 = Person("유재석")
print(person_1.name)
# hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!연관성 있는 데이터들을 클래스 내에서 관리할 수 있고, 다양한 객체들을 쉽게 생성할 수 있다.
링크드 리스트 구현
링크드 리스트의 자료구조 모습
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]
노드에는 칸에 있는 데이터와 다음 칸이 뭔지 알아야 하는 두 가지 정보가 필요하다.
그래서 클래스로 묶는 것이 효율적이다.
링크드 리스트는 self.head에 시작하는 노드를 저장한다.
다음 노드를 보기 위해서 각 노드의 next를 조회한다.
여기서 꿀팁
코드 전체를 한 줄 내리거나 올리는 방법
control + shift + 방향키
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):
print("hihihi")
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
Linked_list = LinkedList(3)
Linked_list.append(4)
Linked_list.append(5)
Linked_list.print_all()
# node = Node(3)
# first_node = Node(4)
# node.next = first_node
LinkedList 라는 클래스에 인자로 첫번째 node를 인자로 넘겨준다. -> 인자로 넘겨진 data는 Node 클래스의 생성자를 LinkedList 클래스의 head로 생성한다. -> (appedn 함수는 현재 존재하는 node의 next의 포인터로 가서 새로운 node를 append 해주는 함수이다.) 새로운 node를 append 함수를 이용해 연결해준다. -> print_all 함수를 통해 cur 변수에 cur.next로 다음 node를 가리키게 하면서 현재의 모든 노드들을 출력하게 한다.
특정한 index의 node 값을 알기 위해서 할 수 있는 코드는?
def get_node(self, index)라는 함수를 만들어 index 별로 링크드 리스트에 들어 있는 node를 반환해 준다.
함수에 알고 싶은 index의 번호를 넘겨주면, count 변수로 1씩 키우면서 index보다 작을 때까지 node.next로 node를 옮긴다.
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node함수 내에서 다른 함수를 호출하고 싶을 때에는 self.함수이름() 으로 함수를 호출하면 된다.
링크드 리스트에 원소 추가하기
index의 다음 노드로 연결되어 있는 화살표를 새로 생성한 노드에 연결해주고, 화살표가 닿아 있었던 index의 다음 노드는 새로 생긴 노드의 화살표를 다시 받기 위해서 다른 변수에 저장되어 있어야 한다.
새로운 노드 (index.next): new_node
new_node.next = next_node(새로운 노드의 화살표가 닿는 노드)
def add_node(self, index, value):
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node # head -> [6] -> [5]
return
node = self.get_node(index-1) # index -> [5] -> [12] -> [6] -> [8]
next_node = node.next
node.next = new_node
new_node.next = next_nodeindex-1을 해주어서 인자가 1 이상이면 정상적으로 작동하지만, 0일 때는 -1이 되므로 예외처리를 해주어야 한다.
=> 이때는 index == 0 인 조건을 만들어 새롭게 생긴 노드에 next 자리에 현재 head 노드가 되는 노드를 집어 넣고, head 자리에 새로 만든 노드를 집어 넣어주면 된다.
링크드 리스트에 원소 삭제하기
[0] -> [1] -> [2]
이 리스트 중에서 1을 빼고 싶다면(삭제하고 싶다면) [0]이 가리키는 화살표를 [2]로 옮기면 된다.
그래서 옮기고 싶은 index번호에 1을 빼서 빼고 싶은 노드의 앞 노드를 가져오고, 앞 노드의 .next.next로 [2]의 노드로 화살표가 가게 한다.
=> node.next = node.next.next
def delete_node(self, index):
if index == 0:
self.head = self.head.next
return
node = self.get_node(index-1)
node.next = node.next.next링크드 리스트 문제
문제 1
Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오.
⠀
예를 들어 아래와 같은 링크드 리스트를 입력받았다면,
각각 678, 354 이므로 두개의 총합
678 + 354 = 1032 를 반환해야 한다.
⠀
단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.
⠀
[6] -> [7] -> [8]⠀⠀⠀⠀⠀
[3] -> [5] -> [4]
각 list의 head를 가지고 있으니, head.next로 다음 노드를 찾아 더할 수 있다.
그러나, 6 + 7 + 8 = 21이므로 각 원소의 data로만 가지고는 문제를 풀 수 없다.
=> 6 10 + 7 = 67
=> 67 10 + 8 = 678
로 각 단계마다 10을 곱해주면 된다는 것을 생가하면 된다!!! (이거 생각한 사람 개천재 ㄷㄷ)
linked_list가 2개 이기 때문에 중복된 코드를 함수로 구현해준다.
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)
return sum_1 + sum_2
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_get_linked_list_sum 함수로 중복된 내용을 잡아준다.
이진 탐색
배열에서 중간부터 탐색하여 효율적으로 배열을 탐색하는 탐색 방법이다.
숫자를 내림하는 방법 : //
// 연산자를 이용하면 소수점 이하으 ㅣ수를 모두 버리고 몫만 나타낼 수 있다.
Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다. 이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오.
이진 탐색으로 시도해 본다.
<이진탐색의 핵심이 되는 코드만 작성>
while current_min <= current_max:
if array[current_guess] == target:
return True
elif array[current_guess] < target: # up
current_min = current_guess + 1
else: # down
current_max = current_guess - 1
current_guess = (current_min + current_max) // 2
return False⠀
⠀
⠀
일정한 규칙으로 정렬되어 있는 데이터일때만 이진 탐색이 가능하다
재귀함수
자신을 계속해서 반복적으로 호출하는 함수이다.
재귀함수를 사용하는 이유는 ??
- 재귀 함수를 이용해서 간결하고 효율성 있는 코드를 작성할 수 있기 때문
재귀함수를 돌 때는 언제 탈출할지 조건을 꼭 정해 주어야 한다.
⠀
가장 대표적인 재귀 함수 예시 코드
def count_down(number): if number < 0: return print(number) count_down(number - 1) ⠀ count_down(60)
팩토리얼
팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.
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(5))
회문 검사
회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미한다.
회문검사 문제
Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
⠀
"abcba" # True
코드
input = "abcba"
# 회문 검사
def is_palindrome(string):
length = len(string)
for i in range(length):
print(string[length - 1 - i])
if string[i] is not string[length - 1 - i]:
return False
return True
print(is_palindrome(input))
문자열 슬라이싱
-
'가나다라마바사'[0:5]
=> '가나다라마'
=> 0번째 인덱스부터 5번 인덱스(6번째) 앞에 까지 짤라서 반환해준다. -
뒤에서 2번째까지 문자열을 자르고 싶다면?
'가나다라마바사'[0:-2]
'가나다라마'
위에 회문검사 코드를 재귀함수로 다시 작성해보자
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))재귀함수로 작성하기 위해서는 문제가 축소되는 특징이 보여야만 한다.
특정 구조가 반복되는 것 같으면, 재귀함수로 축소시켜볼 수도 있다.
-> 재귀함수 사용시 반드시 탈출 조건 작성하기!!
숙제
Q1. 링크드 리스트의 끝에서 K번째 값을 반환하시오.
⠀
[6] -> [7] -> [8] ⠀
⠀# 이런 링크드 리스트가 입력되었을 때, 끝에서 2번째 값은 7을 반환해야 합니다!
시작점을 2개를 잡고 간다. 첫번째보다 k번째 떨어진 두번째 변수가 끝에 가게 되면, 첫번째 변수가 두번째 변수보다 k만큼 떨어져 있으니까 첫번째 변수의 node 값이 링크드 리스트의 끝에서 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):
start = self.head
end = self.head
for i in range(k):
end = end.next
while end is not None:
start = start.next
end = end.next
return start
linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)
print(linked_list.get_kth_node_from_last(2).data) ⠀
⠀
Q2. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다.
⠀
그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.
⠀menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"] orders = ["오뎅", "콜라", "만두"]
이진 탐색 보다는 set() 함수인 집합 자료형을 사용하는 것이 좋다.
집합 자료형은 중복을 허용하지 않는 자료형이다.
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
# 현재 주문 가능한 상태인가?
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
result = is_available_to_order(shop_menus, shop_orders)
print(result)⠀
⠀
Q3. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
⠀
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
⠀
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
⠀numbers = [1, 1, 1, 1, 1] target_number = 3
재귀함수를 이용하여 문제를 풀어야 했는데, 너무 너무 너무 어려웠다...
1로만 풀기는 너무 어렵기 때문에 [2, 3, 1]로 두고 보기 쉽게 풀어보았다.
- +2 +3 → +1 = +2 +3 +1
→ -1 = +2 +3 -1- +2 -3 → +1 = +2 -3 +1
→ -1 = +2 -3 -1- -2 +3 → +1 = -2 +3 +1
→ -1 = -2 +3 -1- -2 -3 → +1 = -2 -3 +1
→ -1 = -2 -3 -1
이 방법을 생각하면서, +2 +3 +1 / -1 을 사용할 수 있는 재귀 함수를 이용하는 것이었다. 문제를 이해하며 풀긴 하였지만, 정확히 설명할 수가 없어서 제대로 이해했는지 장담할 수가 없다...
index 번호가 1개씩 올라가면서 array[0]=2 -> array[1]=3 -> array[2]=1 -> index = 3일때 값들을 다 더한 값을 배열에 append 시켜 최종적으로 6, 4, 0, -2, 2, 0, 4, 6 의 합들이 append되게 하여, 그 값을 출력시키는 코드를 먼저 작성하였다.
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]하지만 이 문제는 target의 수가 나오는 경우의 수를 묻는 문제이기 때문에 마지막 index = 3일 때 all_ways 배열에 append 시키는 대신 target과 current_sum의 값을 비교해 그 값이 맞다면 global 변수인 target_count에 저장하게 하여 최종적으로 주어진 배열에서 정해진 target의 결과값이 나올 수 있는 방법의 수를 구할 수 있게 된다.
numbers = [1, 1, 1, 1, 1]
target_number = 3
target_count = 0
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_number:
global target_count
target_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) # 5를 반환해야 합니다! target_number
print(target_count)알고리즘이라는 것이 필요하다고는 느끼지만, 아직 내가 자유롭게 알고리즘에 대해 생각하고, 프로그램의 효율성을 생각하며 프로그래밍을 하는 단계에 가기에는 부족하다는 생각이 많이 든다. 복잡한건 사실이지만, 조금만 더 깊게 생각하면 이해할 수 있다고 생각하며 수업을 듣고 싶다.
엄청나게 더운 2021년 여름에 머리가 답답하게 막혀오는 알고리즘을 수업을 듣고 과제를 하니 좀 힘든 부분도 많지만 그래도 결국에는 이해해 내고, 코드를 작성해나가는 나에게 더 잘할 수 있다고 말해주고 싶다.
