____________________________________________________________________________________________________________
2주차
이번 주 목표 : 어레이와 링크드 리스트. 이진 탐색, 재귀함수.
어레이(배열)가 순차적으로, 인덱스에 맞게 데이터를 저장하는 것이라면,
링크드 리스트는 node 라고 불리는 공간에 데이터를 저장하고, 그 다음 공간을 지목하는 ‘포인터’ 라고 불리는 공간이 또 있어.
2-2 어레이와 링크드리스트
=> 어레이, 즉 배열은 기본적으로는 원소를 새로 추가하려면 새로운 공간을 할당해야 하기에
원소의 갯수가 가변적일 경우에는 비효율적인 자료구조야.
허나 링크드리스트에서는 각각의 노드가 다음 노드를 지목하는 ‘포인터’ 를 가지고 있기에, 이 포인터만 수정해주면
원소를 가변적으로 다룰 수 있어. 마치 기차의 화물간과 화물칸 사이에 연결고리를 잠시 분리해서 새로운 칸을 삽입하는 것처럼!
링크드 리스트는 크기가 정해져 있지 않은 데이터 공간. 연결 고리를 이어주기만 하면, 자유자재로 크기가 변해.
허나 한편으로는, 리스트는 특정 원소에 접근하려면 연결 고리를 따라서 탐색을 해야 해.
그래서 최악의 경우 모든 화물칸을 탐색해야 하기에, 특정 원소를 조회하는 데에 있어서 걸리는 시간 복잡도는 O(N) 이야.
앞으로는 링크드 리스트의 연결 고리를 ‘포인터’ 라고 부를 것이고, 각 화물칸을 ‘노드’ 라고 부를 거야.
리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 돼.
따라서 원소 삽입/삭제를 O(1) 의 시간 복잡도 안에 처리할 수 있어. 즉 상수 시간내에 가능.
*** 파이썬에서 우리가 list 라고 부르는 자료는 array 로 구현되어 있어.
그럼 append() 메소드 사용해서 배열의 요소를 추가할 때 굉장히 비효율적인 것 아닐까?
허나 내부적으로는 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어 있어.
파이썬의 배열은 링크드 리스트로로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조.
2-3 클래스
클래스는 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념.
객체는 세상에 존재하는 유일무이한 사물.
즉, 예를 들자면.
클래스가 사람이라면, 객체는 ‘김민수’가 될 수 있어.
클래스가 동물이라면, 객체는 우리집 고양이가 될 수 있어.
파일 : sparta_algorithm - week_2 - 00_study_class.py
——
class Person:
pass
person1 = Person()
print(person1) # <__main__.Person object at 0x7f9fe827e760>
person2 = Person()
print(person2) # <__main__.Person object at 0x7f9fe82636d0>
——
=> 출력되는 내용을 보면, Person 이라는 클래스의 객체(object) 가 생성되었다고.
그리고 뒤쪽의 내용은 해당 객체가 저장되어 있는 데이터 공간의 주소.
앞쪽의 __main__ 이거는 생성자 함수를 뜻해.
객체 인스턴스 생성 시 Person() 의 뒤의 () 는 객체가 생성될 때 사용하는 함수, 즉 constructor 생성자.
클래스를 만들 때 constructor 생성자를 설정하기 위해서는 __init__ 이라는 함수를 만들어야 해.
——
class Person:
def __init__(self):
print("i am created! ", self)
person1 = Person() # i am created! <__main__.Person object at 0x7fa84ac86760>
print(person1) # <__main__.Person object at 0x7f9fe827e760>
person2 = Person() # i am created! <__main__.Person object at 0x7fa84ae9f550>
print(person2) # <__main__.Person object at 0x7f9fe82636d0>
——
=> def __init__(self): 라고 명시한 부분이 생성자 함수. 해당 생성자 함수에서는 객체가 생성되며 print() 함수를 사용하고 있어.
그렇다면, self는 무엇인가.
파이썬에서는 constructor 를 생성하거나 내부에 있는 함수를 만들 때 인자에 자기 자신인 self 를 넘겨줘. 이게 기본 룰.
* 마치 자바스크립트의 addEventListener() 처럼!
그리고 맥락 상 self 는 JS의 this.
위 코드에서는,
self 를 constructor 사용을 통해서 주입받고 호출하는 것 까지 해본거야.
이제 클래스에 데이터를 저장해보자.
——
class Person:
def __init__(self, param_name):
print("i am created! ", self)
self.name = param_name
person1 = Person("김민수") # i am created! <__main__.Person object at 0x7fa84ac86760>
print(person1) # <__main__.Person object at 0x7f9fe827e760>
print(person1.name)
person2 = Person("가나다") # i am created! <__main__.Person object at 0x7fa84ae9f550>
print(person2) # <__main__.Person object at 0x7f9fe82636d0>
print(person2.name)
——
=> Person 클래스를 사용하여 객체 인스턴스를 생성할 때 생성자 함수에 파라미터로서 이름을 넣었어.
init 생성자 함수에서는 그 이름을 인자로 받아 자신 클래스(self)의 한 속성으로서 저장했는데(self.name = param_name),
그 속성의 이름이 name 이야.
다음으로, 클래스 내부에 또 다른 함수(메소드)를 추가시켜 보자.
——
class Person:
def __init__(self, param_name):
print("i am created! ", self)
self.name = param_name
def talk (self): # 괄호를 입력하려고 하면 자동으로 self 를 완성시켜줘. self 는 항상 존재해야 해.
print(f"안녕하세요, 제 이름은 {self.name} 입니다.")
person1 = Person("김민수") # i am created! <__main__.Person object at 0x7fa84ac86760>
print(person1) # <__main__.Person object at 0x7f9fe827e760>
print(person1.name)
person1.talk()
person2 = Person("가나다") # i am created! <__main__.Person object at 0x7fa84ae9f550>
print(person2) # <__main__.Person object at 0x7f9fe82636d0>
print(person2.name)
person2.talk()
/// 출력
i am created! <__main__.Person object at 0x7f8aaea86760>
<__main__.Person object at 0x7f8aaea86760>
김민수
안녕하세요, 제 이름은 김민수 입니다.
i am created! <__main__.Person object at 0x7f8aaee9f550>
<__main__.Person object at 0x7f8aaee9f550>
가나다
안녕하세요, 제 이름은 가나다 입니다.
——
=> def talk 라고 메소드를 선언하고 괄호를 치면 자동으로 self 를 입력해줘.
자바스크립트에서는 this 를 인자로 받지 않아도 바로 this. 으로 내부 속성에 접근할 수 있었는데 파이썬에서는 self 를 명시해주네.
__________________________________________
2-4 클래스를 이용해서 링크드 리스트 구현해보기.
링크드 리스트의 각각의 칸을 ‘노드’ 라고 표현한다면, 노드는 두 가지 정보를 필요로 해.
1) 칸에 있는 데이터
2) 다음 칸을 가리키는 ‘포인터’ 에 대한 정보.
두 가지를 데이터를 가지고 있다… 클래스를 사용하는 게 좋겠어.
* 링크드 리스트 라는 건 별도의 데이터 타입을 가리키는 것이 아니라, 클래스로 구성해서 만드는 자료구조 인거야.
*** 링크드 리스트 라는 클래스를 만들어볼 거야.
참고로, 링크드 리스트는 [‘기관실’] -> [“시멘트”] -> [“자갈”] -> [“밀가루”]
이런 식으로 열차 마냥 이어져 있는데, 링크드 리스트는 맨 앞칸만 알고 있으면 돼.
맨 앞 칸만 알면 나머지는 그냥 포인터로 따라가면서 정보를 추적할 수 있거든.
링크드 리스트는 맨 앞에 있는 칸, 즉 ‘헤드 노드’ 라는 것만 가지고 있으면 돼.
정리하면, 1) LinkdList 는 self.head 에 시작하는 노드를 저장한다.
2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다.
파일 : sparta_algorithm - week_2 - 01_print_all_linked_list.py
——
print('----- Node -----')
class Node:
def __init__(self, data):
self.data = data # 생성자 함수로 노드에 저장하고자 하는 데이터를 입력받고는 내부 변수에 저장.
self.next = None # 당장 처음 만드는 것이기에, 포인터로 가리킬 다음 노드는 지금으로서는 없어.
node = Node(3)
first_node = Node(4)
node.next = first_node # node의 포인터에 first_node 라는 노드의 래퍼런스를 저장해 둔 거야.
print(node.next.data)
print(node.data) # 3
print('----- LinkedList -----')
class LinkedList:
def __init__(self, data):
self.head = Node(data) # 노드를 생성해서 연결하는데 위의 방식으로 Node를 생성하고 연결하고 하면 너무 귀찮잖아?
# 그래서 링크드 리스트 클래스를 만들어서 관리를 해줄건데,
# 링크드 리스트에서는 data 를 입력받고 이를 head 에 해당 data 를 들고 있는 Node 를 저장.
# 이렇게 하면 링크드 리스트에 헤드 노드가 저장되는 거야.
linked_list = LinkedList(3)
print(linked_list.head.data) // 3
——
=> linked_list 에는 data 로 3을 넣은 Node 클래스를 생성해서 head 속성에 저장하고 있어. 뭔가 콜백 함수처럼 생겼다 ㅎ
이제 노드를 생성해서 맨 뒤의 노드의 next에 붙이는 기능을 수행하는 append() 라는 함수를 만들어볼거야.
이것만 있으면, 이젠 정말 편하고 쉽게 노드 생성 및 연결을 수행할 수 있을거야.
——
class LinkedList:
def __init__(self, data):
self.head = Node(data) # 노드를 생성해서 연결하는데 위의 방식으로 Node를 생성하고 연결하고 하면 너무 귀찮잖아?
# 그래서 링크드 리스트 클래스를 만들어서 관리를 해줄건데,
# 링크드 리스트에서는 data 를 입력받고 이를 head 에 해당 data 를 들고 있는 Node 를 저장.
# 이렇게 하면 링크드 리스트에 헤드 노드가 저장되는 거야.
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(f'cur is {cur.data}')
cur.next = Node(data)
linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
——
=>
1) 가장 먼저, self.head 가 있는지 없는지부터 체크를 해줘. 만약 < linked_list = LinkedList(3) > 이런 식으로
생성자 함수를 호출하지 않았다면, head가 없는 상태인 것이니까.
만약 헤드 노드가 없다? 그럼 새로 append() 할 때 입력한 data 를 받아서 그대로 self.head = Node(data) 해주면 돼.
2) 만약 헤드 노드가 있다, 그러면 연결된 노드들의 마지막 끝의 노드.next 에 새로 만드는 노드의 래퍼런스를 저장해야 해.
cur 라는 함수에 self.head 에 저장된 노드를 저장해. (실제로는 노드의 래퍼런스가 저장되겠지)
이 상태에서, head 부터 출발해서 연결된 노드들을 타고타고 내려가야 해.
그래서 while 문을 쓰는 거야. While 문은 () 안의 내용이 참이라면 계속해서 아랫 구문을 구동시키지.
3) while 문 안에서 cur 변수는 계속해서 자신의 .next, .next, .next 를 타고타고 내려 가.
그러다 언젠가 끝의 노드에 도달하겠지? 그럼 그 노드는 .next 라는 속성을 가지고 있지 않을거야.
따라서 while문은 종료되고, cur 변수에는 마지막 노드의 래퍼런스가 저장되어 있을거야. 당연히 그 노드는 next 속성이 없겠지.
그 마지막 노드의 .next에 새로 만든 노드의 래퍼런스를 저장하는 거지.
마지막으로, 현재 존재하는 노드들의 모든 데이터를 출력해주는 메소드를 작성.
——
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
——
여기까지 링크드 리스트에 원소를 추가하거나 혹은 원소를 출력하는 것을 구현해 봤어.
다음으로는, 링크드 리스트에서 내가 원하는 원소를 어떻게 찾을 수 있을지 시험해보자.
2-5 링크드 리스트 구현 - 2
=> 원소 찾기와 원소 추가, 그리고 원소 삭제.
파일 : sparta_algorithm - week_2 - 02_get_node_linked_list.py
다음은 인덱스를 입력했을 시, 해당 인덱스에 있는 노드의 데이터값을 반환하는 함수.
——
def get_node(self, index):
cur = self.head
for i in range(index):
cur = cur.next
return cur
<혹은>
def get_node(self, index):
Cur = self.head
Count = 0
While count < index:
cur = cur.next
count += 1
return cur
linked_list = LinkedList(5)
linked_list.append(6)
linked_list.append(7)
linked_list.append(8)
linked_list.append(12)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 함!
——
=> 입력받은 인덱스만큼 헤드로부터 next 로 연결된 노드들을 차례 차례 지나갈거야.
그래서 index 만큼 노드를 이동했을 때(for 문도 되고 while 도 돼), 해당 노드를 반환하면 끝.
다음으로, 링크드 리스트에서 index 번째 원소를 추가하는 방법에 대해서.
파일 : sparta_algorithm - week_2 - 03_add_node_linked_list.py
링크드 리스트의 중간인 index 번째에 노드를 새롭게 추가하는 방법.
——
def add_node(self, index, value):
new_node = Node(value) # 우선 링크드 리스트에 추가하고 싶은 원소를 Node() 로 만들어.
if index == 0: # 예외 처리. 만약 index가 0이라면? head node 로 놓고 싶은 것이라면?
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index-1) # 다음으로, 내가 (중간에) 삽입하고 싶은 index 번째의 노드를 저장해.
next_node = node.next # 마지막 준비로, node 의 바로 다음 노드를 미리 저장해 놔. 나중에 새로 삽입한 노드의 next에 래퍼런스를 저장해야 해.
node.next = new_node # 앞쪽의 노드를 이어주고
new_node.next = next_node # 뒤쪽의 노드를 이어줘.
linked_list = LinkedList(5)
linked_list.append(6)
linked_list.append(7)
linked_list.append(8)
linked_list.append(12)
linked_list.print_all() # 5 6 7 8 12
linked_list.add_node(2, 11)
print('---- add_node 이후 -----')
linked_list.print_all() # 5 6 11 7 9 12
——
이번에는, index 번째의 노드를 삭제하는 방법도 알아보자.
파일 : sparta_algorithm - week_2 - 04_delete_node_linked_list.py
——
def delete_node(self, index):
if index == 0: # 예외 처리. 만약 삭제하고 싶은 index가 0번째 node인 head node 라면?
self.head = self.head.next
return
node = self.get_node(index-1) # 내가 지우고 싶은 index 번째의 노드의 래퍼런스 값을 next 로서 가지고 있는 노드를 가져와.
node.next = node.next.next
linked_list = LinkedList(5)
linked_list.append(6)
linked_list.append(7)
linked_list.append(8)
linked_list.append(12)
linked_list.print_all() # 5 6 7 8 12
linked_list.add_node(2, 11)
print('---- add_node 이후 -----')
linked_list.print_all() # 5 6 11 7 9 12
print('---- delete_node 이후 -----')
linked_list.delete_node(0)
linked_list.print_all() # 6 11 7 8 12
——
=> add도 그렇고 delete 도 그렇고, index-1 을 할 경우에는 index 가 0일 때에 대한 예외 처리를 어케 해줄 것인가를 꼭 생각해야 해.
예외 처리 해준 다음에는 return 으로 함수를 종료시켜 주는 것도 잊지 말구.
2-6 링크드 리스트 실전 문제 풀어보기.
파일 : sparta_algorithm - week_2 - 05_get_linked_list_sum.py
두 링크드 리스트를 입력받고, 합한 값을 리턴.
——
def get_linked_list_sum(linked_list_1, linked_list_2):
sum1 = _get_linked_list_sum(linked_list_1)
sum2 = _get_linked_list_sum(linked_list_2)
return sum1 + sum2
def _get_linked_list_sum (linked_list):
result = 0
head = linked_list.head
while head is not None:
result = result * 10 + head.data
head = head.next
return result
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))
——
=> 결과적으로 678 + 354 = 1032 라는 값이 리턴.
중요한 건, 어쨌든 next 를 통해서 연결된 노드들을 다 이동하면서 찾으려면
——
head = linked_list.head
while head is not None:
result = result * 10 + head.data
head = head.next
____
이런 식으로 변수가 노드들의 래퍼런스를 계속 이동하면서 while 문을 이용해 더 이상 노드가 없는 곳까지 이동해야 한다는 것.
2-6_2 요세푸스 문제 풀어보기.
파일 : sparta_algorithm - week_2 - 05_02_problem_of_Josephus.py
문제.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
__________________________________________
2-7 이진 탐색
이진 탐색과 순차 탐색을 비교하면서 각각 어떤 특징들을 지니고 있는지 배워보자.
이진 탐색이란, 배열을 반으로 나누어서 탐색하는 방법을 말해.
우선 간단한 이진 탐색 로직을 구현해보자.
파일 : sparta_algorithm - week_2 - 06_is_existing_target_number_bunary.py
——
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
# target 과 array 가 입력되었을 때, array 안에 target 이 있으면 true 를, 없으면 false 를 반환.
def is_existing_target_number_binary(target, array):
current_min = 0 # 최솟값. array의 0번째 인덱스.
current_max = len(array) - 1 # 최대값. array의 마지막 인덱스.
current_guess = (current_min + current_max) // 2 # 최솟값과 최대값의 중간값을 찾아낸 거야. 이걸로 up,down 을 시도할거야.
find_count = 0 # 이건 그냥 while 문이 몇 번 반복됬는지 검사해 보려고.
while current_min <= current_max: # min 이 max 보다 같거나 작을 때 까지. 범위를 좁혀가는 과정에서 min 에 +1, max에 -1 을 하기 때문에,
find_count += 1 # 마지막의 마지막에는 min 과 max 의 값이 같아진 상태에서 연산이 일어나며 while문의 조건이 false로 변해.
if array[current_guess] == target: # 만약 시도값이 타겟과 같다면? 그냥 바로 return True
print(find_count)
return True
elif array[current_guess] < target: # target 이 시도값보다 크다, 즉 up.
current_min = current_guess + 1 # 시도값보다 타겟이 더 크니, 시도값의 인덱스보다 1 만큼 더 큰 인덱스부터 다시 탐색을 시도하라.
else:
current_max = current_guess - 1 # target 이 시도값보다 작다, 즉 down
# 시도값보다 타겟이 더 작으니, 시도값의 인덱스보다 1 만큼 더 작은 인덱스부터 아래를 다시 탐색.
current_guess = (current_min + current_max) // 2
print(find_count)
return False # 만약 끝까지 while 문을 돌리며 값을 찾아봤는데 없다, 그러면 최종적으로는 False 를 반환하겠다.
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
——
=> 참고로 이진 탐색의 시간 복잡도는 O(logN) 만큼 걸려. 뭔 수식이지 싶긴 해.
이진 탐색의 기본에 대해 배웠다면, 이를 활용하여 문제를 풀어보자.
파일 : sparta_algorithm - week_2 - 07_is_existing_target_number_binary.py
헌데 문제가 발생.
——
finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]
——
=> 이전 예시와 다르게 이번에는 배열에 숫자가 차순으로 들어가 있지 않아.
즉, 이진 탐색은 배열의 요소들이 무작위로 배치되어 있을 때는 사용할 수가 없어. 일정한 규칙으로 정렬되어 있을 때만 가능해.
이진 탐색을 위해선 정렬이 필요해. 정렬은 3주차 때 알아보자.
__________________________________________
2-8 재귀 함수
재귀란, 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻해.
재귀 함수는 쉽게 말하면 자기 자신을 계속해서 호출하는 함수를 말해.
카운트 다운을 해주는 재귀 함수 만들어보기.
파일 : sparta_algorithm - week_2 - 08_count_down.py
다음과 같이 카운트 다운 재귀 함수를 구성할 수 있어.
——
def count_down(number):
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)
——
=> 단, 이 경우 에러가 발생할거야. 왜? 끝도 없이 반복될 테니까.
처음에는 60,59,58 이렇게 시작하고 결국에는 0을 뚫고 -100, -101, … -900,-901 이런 식으로.
따라서, 재귀 함수는 ‘언젠가는’ 끝나야 해. 그리고 언제 끝나야 할 지를 명시해 줘야 해. 즉 탈출 조건을 정해주는거지.
재귀 함수는 자기 자신을 호출해 줌으로서 코드를 명확하고 간결하게 만들 수 있다는 장점이 있어.
2-9 재귀 함수를 응용해서 ‘팩토리얼’ 과 ‘회문 검사’ 라는 문제를 풀어 보자.
팩토리얼이란?
=> 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미함.
예를 들어서
3! => 3*2*1 = 6
4! => 4*3*2*1 = 24 = 4*3!
** ! 는 팩토리얼의 표기법.
파일 : sparta_algorithm - week_2 - 09_factorial.py
——
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1) # 5를 입력했으면, 5*4! 를 리턴하면서 4*3! 를 실행하러 가는거지. 그렇게 n 이 1이 되면 1을 리턴. 2*1! 이 마지막.
# 2*1! 까지 실행이 됬으면, 다시 위로 거슬러 올라가서 5*4! 까지 올라간 뒤 값을 반영하고 최종적으로 리턴 완료.
# 즉 최종적으로는 5 * 4 * 3 * 2 * factorial(1) 이 되는거야.
print(factorial(5))
——
다음으로 ‘회문 검사’ 를 해보자.
회문이란, 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미.
ex) 토마토, 오디오, 아시아, 일요일, 가련하시다 사장 집 아들 딸들아 집 장사 다시 하련가
——
print('----------------------- 2-9 재귀 함수 - 회문 검사 -----------------------')
def is_palindrome(string):
n = len(string)
for i in range(n): # i = n-1 까지 반복이 되겠지.
if string[i] != string[n - 1 - i]: # 예를 들어 len이 7이면, 0 = 6, 1 = 5, 2 = 4 이런 식으로 비교.
return False
return True
input = "abcba"
print(is_palindrome(input))
——
위의 회문 검사를 재귀 함수를 사용해서 풀어보자.
——
def is_palindrome2(string):
if len(string) <= 1: # 문자열을 계속 자르면 마지막에는 한 문자만 남거나 혹은 다 사라지겠지.
return True # 그 때 까지 검사를 했는데 False 가 리턴되지 않았으니 true 를 리턴하며 재귀 함수를 종료시켜.
if string[0] != string[-1]: # 인덱스를 -1 로 하면, 0번째 인덱스의 바로 이전 인덱스이니까, 돌아서 맨 마지막 인덱스를 반환해.
return False
return is_palindrome2(string[1: -1]) # 맨 앞, 맨 뒤 문자를 자른 문자열을 다시 입력해서 재귀 함수 호출.
input2 = "abcba"
print(is_palindrome2(input2))
——
!!! 재귀 함수를 풀기 위해서는 문제가 축소되는 특징이 보여야만 해.
즉, 특정 구조가 반복되는 것 같은 양상이 보인다면, 재귀 함수로 문제를 축소 시키면서 풀어볼 수 있겠구나 라는 생각을 해봄 직 하단 것.
또한, 재귀 함수를 사용할 때에는 반드시 탈출 조건을 설정해줘야 해.
________________________________________________
2-10 2주차 숙제
첫 번째. 링크드 리스트 끝에서 K번째 값을 반환.
파일 : sparta_algorithm - week_2 - homework_01_get_kth_node_from_last.py
——
def get_kth_node_from_last(self, k):
all_nodes_cnt = 1
node = self.head
result_node = self.head
while node.next is not None:
node = node.next
all_nodes_cnt += 1
k_length = all_nodes_cnt - k
print(f'all_nodes_cnt : {all_nodes_cnt} / k_length : {k_length}') # 4
for i in range(k_length):
result_node = result_node.next
return result_node
def get_kth_node_from_last_2(self, k):
min_k_point = self.head
max_k_point = self.head
for i in range(k):
max_k_point = max_k_point.next # k=2, max_k_point.data = 8
while max_k_point is not None:
min_k_point = min_k_point.next
max_k_point = max_k_point.next
return min_k_point
linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)
linked_list.append(9)
linked_list.append(10)
print(linked_list.get_kth_node_from_last(2).data) # 9이(가) 나와야 합니다! 뒤에서 2번째.
print('---- 더 나은 방법 ----')
print(linked_list.get_kth_node_from_last_2(2).data) # 9이(가) 나와야 합니다! 뒤에서 2번째.
——
=> 첫 번째 방법은 우선 노드의 전체 길이를 구한 다음, 그 전체 길이에서 k 만큼 뺀 길이를 다시 헤드 노드부터 이동해서 찾았어.
두 번째 방법은, 우선 min, max 라는 두 개의 변수에 헤드 노드를 각각 저장하고,
max만 k번 만큼 노드를 이동시켜. 중요한 건 k 만큼 min 과 max 의 거리를 벌려 놓는다는 것.
그 상태에서 max 가 마지막 노드의 .next 를 검색해서 None 값을 가지게 될 때까지 min 과 max 를 이동시켜.
이렇게 되면, max 와 k 만큼 떨어져 있는 min 은 뒤에서 K번째 노드를 가리키게 돼.
두 번째. Q. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다.
그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.
파일 : sparta_algorithm - week_2 - homework_02_is_available_to_order.py
——
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
set_all_menus = set(menus)
check_menu = []
for order in orders:
if order in set_all_menus:
check_menu.append(order)
return check_menu
result = is_available_to_order(shop_menus, shop_orders)
print(result)
——
=> 알고리즘은 단순해. In 문법을 사용해서, 전체 메뉴 중에 오더 메뉴가 포함되어 있느냐,
포함되어 있으면 해당 메뉴를 빈 배열에 append 해서, 최종적으로는 주문한 메뉴가 전체 메뉴 중에 포함되어 있으면 해당 메뉴를 출력.
근데, set_all_menus = set(menus) 이건 뭔가.
왜 전체 메뉴를 set() 으로 감싸서 집합 자료형으로 바꾸었는가?
이유는, in 문법을 사용할 때 대상이 배열이냐 집합이냐에 따라서 걸리는 시간이 달라. 참고로 집합 자료형이 더 빨라.
세 번째. Q. 음이 아닌 정수들로 이루어진 배열이 있다.
이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다.
예를 들어 [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이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서
타겟 넘버를 만드는 방법의 수를 반환하시오.
파일 : sparta_algorithm - week_2 - homework_03_get_count_of_ways_to_target_by_doing_plus_or_minus.py
——
numbers = [2, 3, 1]
target_number = 0
result_count = 0 # 모든 경우의 수를 체크
# 정수배열 타겟 for let i 각 분기 당 계산식의 값
def get_all_ways_to_by_doing_plus_or_minus(array, target_num, current_index, current_sum):
if current_index == len(array): # 탈출조건! 예를 들어 정수배열의 길이가 6개다. current_index는 0, 1, 2, 3, 4, 5 만큼 돌아.
if current_sum == target_num: # 함수가 정수 배열만큼 분기를 완료했어. 그렇게 해서 각 분기별로 최종값들을 타겟과 비교.
global result_count # 함수 외부의 전역 변수를 함수 내부에서 사용하겠다.
result_count += 1 # 정수 배열의 계산 분기 중에서 타겟과 같은 값을 최종적으로 산출한 경우의 총 횟수.
return
get_all_ways_to_by_doing_plus_or_minus(array, target_num, current_index + 1, current_sum + array[current_index])
get_all_ways_to_by_doing_plus_or_minus(array, target_num, current_index + 1, current_sum - array[current_index])
get_all_ways_to_by_doing_plus_or_minus(numbers, target_number, 0, 0)
print(result_count)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
# 모든 경우의 수가 출력됩니다!
# [6, 4, 0, -2, 2, 0, -4, -6]
——
=> 음… 분기 별로 함수가 계속 분열하면서 발생한다 라고 생각하면 편해.
'내일배움캠프_개발일지 > 프로그래밍 기초_알고리즘' 카테고리의 다른 글
| 프로그래밍 기초_알고리즘 5 (2) | 2022.11.29 |
|---|---|
| 프로그래밍 기초_알고리즘 4 (0) | 2022.11.25 |
| 프로그래밍 기초_알고리즘 3 (1) | 2022.11.25 |
| 프로그래밍 기초_알고리즘 1 (0) | 2022.11.22 |