2주차의 목표는 Array와 Linked List의 차이, 이진탐색, 재귀함수을 이해하는 것이 포인트이다.
자료구조와 알고리즘의 필요성을 아래와 같이 정의하며 시작한다.
어떤 자료구조는 삽입/삭제가 빠르고
어떤 자료구조는 조회가 빠릅니다.
이처럼 어떤 경우에는 이 자료구조가 좋고,
어떤 경우에는 저 자료구조가 좋은 것처럼
경우에 따라 다양한 자료구조와 알고리즘을 사용해야 합니다.
비유를 들어보면, 못을 박을 때는 망치가 필요하고, 나사를 뺄 때는 뺀치가 필요한 것처럼
여러분이 다양한 공구들을 하나하나 배워가는 것이라고 생각하시면 됩니다.
공구들의 사용법을 하나하나 이해해봅시다.
※ 캡슐 호텔 예제를 통한 Array의 이해
✅ 여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요? 오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라고 합니다.
배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없다.
✅ 떨리는 마음으로 체크인을 받고, 각 호수에 있는 멤버들의 방에 방문해 웰컴 드링크를 전달했습니다.
배열은 각 호텔방(요소)에 즉시 접근할 수 있다. rooms[0]처럼 방문하기 원하는 곳을 바로 지정해서 접근 가능하다.
이때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미한다. 따라서 O(1)의 시간복잡도 내에 접근할 수 있다고 말한다.
✅ 앗 그런데, 제일 끝방에 있는 서현이 수영과 티파니 사이의 방에서 자고 싶다고 합니다. 다른 멤버들의 순서는 유지한채요! 그래서 다음과 같이 이동해야 했습니다. 너무 힘들게 방을 옮겨서 피곤해진 서현이는 바로 곯아떨어졌다고 합니다.
배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야한다. 최악의 경우, 배열의 길이 N만큼을 옮겨야 하므로 O(N)의 시간복잡도를 가진다.
✅ 갑자기 호텔 프론트에 전화가 왔습니다. 매니저가 곧 도착할 예정이니, 방 하나를 더 준비해달라고 연락이 왔습니다! 이런, 어떡하죠? 그래서 옆 공터에 방이 9개인 호텔을 지었습니다. 물론 새로운 호텔을 짓느라 돈과 시간을 다 써 사업이 망해버리고 말았습니다 ㅠㅠ
공간이 꽉 찬 상태에서 요소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조라고 할 수 있다.
※ 화물 열차를 이용한 Linked List의 이해
✅ 여러분이 이번엔 화물 열차를 만들었습니다. 총 5칸을 실은 화물 열차입니다. 각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있습니다!
리스트는 크기가 정해지지 않은 데이터의 공간이다. 연결고리로 이어주기만 하면, 자유자재로 늘어날 수 있다.
✅ 우편 칸에 잠시 일이 생겼습니다! 시멘트 칸을 지나, 자갈칸을 지나, 밀가루 칸을 지나 겨우 우편칸에 도착했습니다.
리스트는 특정 요소에 접근하려면 연결고리를 따라 탐색해야한다. 최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간복잡도를 가진다. 여기서, 앞으로 연결 고리를 포인터라 부르고, 각 화물 칸을 노드라고 부르도록 한다.
✅ 앗 그런데, 시멘트 칸과 자갈 칸 사이에 흑연이라는 칸을 넣기로 했습니다. 그래서, 화물칸의 연결고리를 이어 붙였습니다. 시멘트 칸의 연결고리를 흑연 칸에 연결하고, 흑연 칸의 연결고리를 자갈 칸으로 연결했습니다. 가던 도중 밀가루가 상해서 밀가루 칸을 버리기로 했습니다. 그래서 흑연 칸의 연결고리를 떼서 우편 칸으로 연결하기로 했습니다! 밀가루 칸을 버려버렸습니다.
리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 따라서 요소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.
| 특징 | Array | Linked List |
|---|---|---|
| 데이터 탐색 | O(1) | O(N) |
| 데이터 삽입&삭제 | O(N) | O(1) |
| 데이터 추가 | 데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 한다. | 동적으로 추가하기 때문에 공간에 구애받지 않는다. |
| 정리 | 데이터에 접근하는 경우가 빈번하다면 Array를 사용하자 | 삽입과 삭제가 빈번하다면 Linked List를 사용하는 것이 좋다. |
클래스는 객체를 만들기 위한 설계도를 의미하며, 객체는 유일무이한 사물(자동차, 비행기 etc)이다. 예를 들면 클래스가 동물이라면, 객체는 강아지가 될수도 있고, 고양이가 될수도 있다.
클래스는 설계도라고 했는데, 설계도에는 상태값과 기능이 정리가 되어 있다. 상태값은 멤버변수라고 하고, 기능은 메소드(method)라고 한다. 예를 들어서 사람이라는 클래스가 있으면, 그 사람의 이름이나 나이는 상태값이 되고, 사람이 말하거나 먹거나 등의 행동은 메소드가 된다.
또한 처음 클래스를 통해 객체를 만들어낼 때, 필요한 상태값을 초기화하거나 선행되어야하는 기능이 있으면 생성자(constructor)를 통해 실행할 수 있다. python에서는 init 라는 이름으로 생성자 함수의 이름이 고정되어 있다.
# python에서 class를 만드는 방법
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def talk(self):
print(f"안녕하세요 저는 {self.name}입니다.")
print(f"저는 {self.age}살 입니다.")Linked List를 구현하기 위해서는 먼저 요소가 되는 Node를 정의 해야한다. 화물열차를 생각해보면, 화물칸 하나는 화물과 다음 칸을 연결할 고리가 달려 있었다. 즉 데이터와 다음칸이 뭔지 저장할 수 있도록 구현해야한다.
class Node:
def __init__(self, data):
self.data = data
self.next = None위에 정의한 Node를 바탕으로 Linked List를 구현하면 아래와 같다.
class LinkedList:
def __init__(self, value):
self.head = Node(value)
# 마지막 위치에 노드 추가
# cur.next가 None이 되는 순간
# 현재 가리키고 있는 대상이 맨 마지막 노드라는 것을 알 수 있다.
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
# 모든 노드 출력
# cur.next가 None = 즉 맨 마지막 노드가 될 때까지 출력하면 된다.
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 = node.next
count += 1
return node
# 원하는 위치에 노드 추가
# index-1 같은 연산을 할 때에 index가 0인 경우에는 어떻게 될까 꼭 생각해봐야한다.
# get_node(-1)이 호출되면 원하지 않게 동작할테니 예외처리를 꼭 추가해야한다.
# 아니면 처음부터 더미노드를 만들어도 좋다.
def add_node(self, index, value):
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index-1)
next_node = node.next
node.next = new_node
new_node.next = next_node
# 노드 삭제
# 똑같이 index-1 연산을 보고 index가 0인 경우의 처리를 생각해봐야한다.
def delete_node(self, index):
if index == 0:
self.head = self.head.next
return
prev_node = self.get_node(index-1)
del_node = prev_node.next
prev_node.next = del_node.next
# [5] -> [6] -> [12] -> [8]
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(1, 6)
linked_list.delete_node(0)
linked_list.print_all()이진탐색(Binary Search) 이란 데이터에서 범위의 가운데 값(=절반값)을 기준으로 탐색을 진행하는 방법을 말한다. 주의해야할점은 일정한 규칙으로 정렬되어 있는 데이터일때만 이진 탐색이 가능하다.
이진탐색시 3가지를 준비해야한다.
1) 시작 위치(start_idx)
2) 마지막 위치(end_idx)
3) 중간 위치(mid_idx)
이진 탐색은 정렬된 데이터의 가운데 값을 가지고 탐색을 진행하기 때문에 시작위치와 마지막 위치를 통해 중간 위치값을 구하고, 해당값이 탐색 대상인지를 확인하며 진행된다.
이진 탐색 알고리즘 순서
1) 시작 위치값이 마지막 위치보다 앞에 있다면 탐색 과정을 반복한다. 만약 시작 위치 값이 마지막 위치 값보다 커지면 탐색 대상이 없음을 의미한다.
while start_idx <= end_idx:2) 시작 위치와 마지막 위치를 통해 중간 위치 산출
mid_idx = (start_idx + end_idx) // 23) 중간 위치의 값이 탐색 대상인가 확인
if target > array[mid_idx]:
start_idx = mid_idx + 1
elif target < array[mid_idx]:
end_idx = mid_idx - 1
else:
return True위의 이진 탐색 알고리즘을 구현해보면 아래와 같다.
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):
start_idx = 0
end_idx = len(array) - 1
while start_idx <= end_idx:
mid_idx = (start_idx + end_idx) // 2
if target > array[mid_idx]:
start_idx = mid_idx + 1
elif target < array[mid_idx]:
end_idx = mid_idx - 1
else:
return True
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
📃 재귀(Recursion)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. [위키백과]
즉 재귀 함수는 바로 자기 자신을 호출하는 함수를 말한다. 자기 자신을 호출한다는 것은 같은 연산을 반복해서 사용하는 경우에 사용한다는 것이다. 같은 연산을 반복해서 사용하는 대표적인 예제로는 팩토리얼과 회문검사가 있다.
재귀 함수는 자기 자신을 호출하기 때문에, 빠져나가는 지점을 명확하게 지정하지 않으면 무한루프에 빠지게 된다. 반드시 빠져나가는 지점을 만들어야함을 명심하자.
# 재귀함수를 이용한 팩토리얼 구현
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1) # 자기 자신을 호출하고 있으므로 재귀함수이다.
print(factorial(60))