오늘 배울것
- 어레이(Array)와 링크드 리스트(Linked List)
- 클래스
- 이진 탐색과 재귀 함수
어레이(Array)와 링크드 리스트(Linked List)
1. 어레이(Array, 배열)
- 배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없다.
- 배열은 각 원소에 즉시 접근할 수 있다. 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미한다. 즉, O(1) 내에 접근할 수 있다고 말할 수 있다.
- 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조.
2. 링크드 리스트(Linked List)
- 리스트는 크기가 정해지지 않은 데이터의 공간이다. 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있다
- 리스트는 특정 원소에 접근하려면 포인터를 따라 탐색해야 한다. 최악의 경우에는 모든 노드를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
- 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 따라서 원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.
비교 정리
**
Q) python 의 배열은 list 라고 부르고 append 를 막 하는데, python 의 배열은 list 인가요 array 인가요?
A) Python 의 list 는 array 로 구현되어 있습니다!
Q) 그러면 append 메소드를 쓰면 새로운 배열을 생성해서 되게 안 좋은 거 아닌가요??
A) 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계했습니다! 여러분이 기억하셔야 할 건, 파이썬의 배열은 링크드 리스트로 쓸 수도 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조다! 라고만 생각해주시면 됩니다.
더 자세히 탐색해보기(링크)
https://stackoverflow.com/a/5932364
Internals of Python list, access and resizing runtimes
Is Python's [] a list or an array? Is the access time of an index O(1) like an array or O(n) like a list? Is appending/resizing O(1) like a list or O(n) like an array, or is it a hybrid that can ma...
stackoverflow.com
https://en.wikipedia.org/wiki/Dynamic_array
Dynamic array - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search List data structure to which elements can be added/removed Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for e
en.wikipedia.org
클래스(Class)
class - 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념
객체 - 세상에 존재하는 유일무이한 사물 ex) 클래스-사람, 객체 - 유재석, 강호동 / 클래스-동물, 객체 - 강아지, 고양이
클래스를 이용하면 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있다
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>
생성자(Constructor) - 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있다.
파이썬에서 생성자 함수의 이름은 __init__ 으로 고정되어있다.
class Person:
def __init__(self):
print("hihihi", self)
person_1 = Person() # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
person_2 = Person() # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!생성자는 생성시에 호출되는 함수이다. 따라서, 위처럼 Person 을 생성하기만 해도 hihihi 와 self 가 동시에 출력이 된다.
self - self 는 객체 자기 자신을 가리킨다. 따라서, 파라미터를 따로 넣어줄 필요가 없이 그냥 호출하면 알아서 self에 자기 자신을 넣는다.
* self 를 사용해서 객체에 데이터를 쌓을 수가 있다.
class Person:
def __init__(self, param_name):
print("hihihi", self)
self.name = param_name
person_1 = Person("유재석") # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name) # 유재석
person_2 = Person("박명수") # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name) # 박명수self.name 에 param_name 을 저장해두겠다는 건 그 객체의 name 이라는 변수에 저장된다는 의미
메소드(method) - 클래스 내부의 함수
class Person:
def __init__(self, param_name):
print("hihihi", self)
self.name = param_name
def talk(self):
print("안녕하세요 저는", self.name, "입니다")
person_1 = Person("유재석") # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name) # 유재석
person_1.talk() # 안녕하세요 저는 유재석 입니다
person_2 = Person("박명수") # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name) # 박명수
person_2.talk() # 안녕하세요 저는 박명수 입니다talk 라는 메소드를 만들어 보면, 각 객체의 변수를 사용해서 메소드를 구현할 수 있다.
이처럼 클래스를 이용하면 연관성 있는 데이터들을 클래스 내에서 관리할 수 있으며, 다양한 객체들을 쉽게 생성할 수 있다
클래스의 활용 - 링크드 리스트 구현하기
ex)링크드 리스트의 구조
train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]링크드 리스트는 이렇게 생겼습니다! 노드는 아래 두 가지 정보가 필요합니다.
- 칸에 있는 데이터
- 다음 칸이 뭔지
엇, 그러면 두 가지 데이터를 가지고 있어야 하니까 클래스를 이용하면 되겠군요! 한 번, 클래스로 묶어보겠습니다!
우선 클래스의 생성자에 data 를 인자로 받아서 self.data 에 저장합니다! 그리고, 현재는 다음 이어진 노드가 없기 때문에 self.next 에는 None 을 넣어두면 됩니다!
다음처럼요!
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]
그러면 이제 노드들을 만들어서 연결해볼까요?
first_node = Node(5) # 현재는 next 가 없이 하나의 노드만 있습니다. [5]
second_node = Node(12) # [12] 를 들고 있는 노드를 만듭니다.
first_node.next = second_node # 그리고, [5]의 next 를 [12]로 지정합니다. [5] -> [12]
이 노드들을 일일이 계속 연결해주려면 변수를 지정하고 위와 같은 코드를 반복해야 하는데, 너무 번거롭습니다! 만약 1억개의 노드가 있다면, 저 코드를 반복해서 1억번을 쳐야 합니다. 상상만해도 손가락이 아프겠죠?
따라서 LinkedList 라는 클래스를 한 번 만들어볼게요! LinkedList 는 head node 만 딱 들고 있습니다. 기차를 다시 떠올려보면, 맨 앞 칸만 저장해두는 거에요. 다음 칸을 보기 위해서는 next를 통해서 다음 노드에 접근해야 합니다! 정리하면, 1) LinkdList 는 self.head 에 시작하는 노드를 저장한다. 2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다. 그럼 이제 한 번 만들어보겠습니다!
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head 에 시작하는 Node 를 연결합니다.
linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력됩니다!
# 현재 LinkedList 는 (5) 만 존재합니다!
이번에는,
LinkedList 의 맨 뒤에 새로운 Node 를 붙이는 append 함수를 만들어보겠습니다! 현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가해주시면 됩니다! 그러기 위해서는 가장 맨 뒤의 노드까지 가야 합니다.
맨 뒤의 노드까지 가기 위해서는 어떻게 해야 할까요? 현재 링크드 리스트는 다음과 같다고 합니다.
head
[3] → [5] → [6] → [8]
바로, head 를 따라서 계속 이동해야 합니다!
head 를 변경시킬 수는 없으니, cur 이라는 변수를 이용해볼게요
cur = this.head 에 넣으면 아래와 같이 되고,
cur
[3] → [5] → [6] → [8]
cur = cur.next 을 하면 다음과 같이 한 칸 이동합니다.
cur
[3] → [5] → [6] → [8]
cur = cur.next 또 하면?
cur
[3] → [5] → [6] → [8]
이걸 언제까지 반복할까요?
맨 뒤의 노드까지 라는 소리는 cur.next 가 None 이라는 것을 의미합니다. 맨 마지막 노드는 다음 노드가 없으니까 아무것도 가리키지 않을테니까요! 그럼 이제 코드로 한 번 만들어보겠습니다!
class LinkedList:
def __init__(self, value):
self.head = Node(value) # head 에 시작하는 Node 를 연결합니다.
def append(self, value): # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결합니다.
cur = self.head
while cur.next is not None: # cur의 다음이 끝에 갈 때까지 이동합니다.
cur = cur.next
cur.next = Node(value)
linked_list = LinkedList(5)
linked_list.append(12)
# 이렇게 되면 5 -> 12 형태로 노드를 연결한 겁니다!
linked_list.append(8)
# 이렇게 되면 5 -> 12 -> 8 형태로 노드를 연결한 겁니다!
링크드 리스트 구현 - 2
링크드 리스트 원소 찾기 / 원소 추가 / 원소 삭제
Q. 링크드 리스트에서 index번째 원소를 반환하시오.
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
def get_node(self, index):
return "index 번째 노드를 반환해보세요!"
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.get_node(0) # -> 5를 들고 있는 노드를 반환해야 합니다!- 해결방법
...
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
...노드를 따라가면서 값을 찾아야 합니다.
head에 저장되어있는 노드를 node 라는 변수에 담고,
count 라는 인덱스를 저장하기 위한 변수를 저장합니다.
그리고 count 가 index 가 될 때까지
(이 때, while 문 내부에서 1씩 더해주니까 작을때까지로 조건을 넣습니다)
node의 next 값을 node 에 대입하고 count 를 증가합니다.
이 과정을 count 가 index가 아닐때까지 반복하면 됩니다!
그리고 node 를 반환해줍니다.
Q. 링크드 리스트에서 index번째 원소를 추가하시오.
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
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
return "index 번째 Node 뒤에 value 를 추가하세요!"
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()- 해결방법
우리가 전에 이야기 했던 화물을 생각하면 됩니다!
# 1. 자갈 칸의 연결고리를 흑연 칸으로 연결하고,
["자갈"] -> ["흑연"] ["밀가루"] -> ["우편"]
# 2. 흑연 칸으로 연결고리를 밀가루 칸으로 연결합니다.
["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
이 때, 밀가루 칸의 위치를 저장해둬야 # 2 에서 흑연 칸을 밀가루 칸에 연결할 수 있습니다.
따라서 next_node 라는 변수에 현재 노드와 연결된 노드를 저장해두고,
# 1. 현재 노드의 다음 노드를 새로운 노드와 연결합니다.
# 2. 새로운 노드의 다음 노드를 이전에 저장해둔 노드에 연결합니다.
Tip : 현재 노드를 구하기 위해서는 방금 만든 get_node 를 사용하면 됩니다!
...
def add_node(self, index, value):
new_node = Node(value)
node = self.get_node(index - 1)
next_node = node.next
node.next = new_node
new_node.next = next_node
...
주의해야 할 점
어느 코드에서나 index - 1 처럼 -1 하는 코드가 있으면,
0의 경우에는 어떻게 될까? 에 대한 걱정을 해주셔야 됩니다!
만약 0이 입력된다면, get_node(-1) 이 호출되어서 원하지 않게 동작해버릴거에요!
따라서, 이런 경우는 예외처리를 따로 해주셔야 합니다.
만약 0번째에 노드를 넣고 싶다면 어떻게 해줘야 할까요?
새로운 노드의 next 를 현재 가지고 있는 head 에 연결하고,
우선 현재 가지고 있는 head 를 새로운 노드로 교체해주시면 됩니다!
...
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
...
Q. 링크드 리스트에서 index번째 원소를 제거하시오.
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
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
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
def delete_node(self, index):
return "index 번째 Node를 제거해주세요!"
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()- 해결 방법
우리가 전에 이야기 했던 화물을 생각하면 됩니다!
# 1. 흑연 칸의 연결고리를 떼서
["자갈"] → ["흑연"] ["밀가루"] → ["우편"]
# 2. 우편 칸으로 연결하면 됩니다!
["자갈"] -> ["흑연"] -> ["우편"]
["밀가루"]
흑연 칸의 포인터를 다음 다음 칸으로 연결하면 됩니다.
Tip : 현재 노드를 구하기 위해서는 방금 만든 get_node 를 사용하면 됩니다!
...
def delete_node(self, index):
node = self.get_node(index - 1)
node.next = node.next.next
...
주의해야 할 점
어느 코드에서나 index - 1 처럼 -1 하는 코드가 있으면,
0의 경우에는 어떻게 될까? 에 대한 걱정을 해주셔야 됩니다!
만약 0이 입력된다면, get_node(-1) 이 호출되어서 원하지 않게 동작해버릴거에요!
따라서, 이런 경우는 예외처리를 따로 해주셔야 합니다.
만약 0번째의 노드를 제거하고 싶다면 어떻게 해줘야 할까요?
현재 head 의 다음 노드를 head 로 만들기만 하면 됩니다!
...
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
...
이진 탐색
이진 탐색 vs 순차 탐색
ex) 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있을 때, 14를 찾는 코드
- 순차 탐색의 경우
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_sequential(target, array):
for number in array:
if target == number:
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result) # Truearray 를 따라가면서 target 이 존재한다면 True 를 반환하고, 끝까지 없다면 False 를 반환하는 간단한 코드.
- 이진 탐색의 경우
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):
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
current_guess = (current_min + current_max) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
- 시간복잡도 비교
- 순차 탐색의 경우 O(N)
- 이진 탐색의 경우 O(logN)
이진탐색의 경우 - 총 숫자가 N일 시 첫번째 탐색시 반절이 줄어 N/2, 다음은 N/2^2 ... k번시 N/2^k
이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다. 이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = \log_2{N} 횟수를 시도하면 정답을 찾을 수 있습니다!
상수는 무시해도 되기 때문에 이진 탐색을 위해서는 시간복잡도가 O(logN) 만큼 걸린다 라고 표현할 수 있다!
** 이진 탐색은 일정한 규칙으로 정렬되어 있는 데이터일때만 가능
재귀 함수
재귀(Recursion) - 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.
재귀 함수 - 자기 자신을 호출하는 함수
** 재귀함수는 반드시 빠져나가는 지점(탈출 경로)을 명확하게 정해줘야 한다!
Q. 60에서 0까지 숫자를 출력하시오.
A.
def count_down(number):
if number < 0: # 탈출 경로
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)
재귀함수의 활용 - 팩토리얼
팩토리얼 - 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것
ex)
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(60))으로 구현 가능!
재귀함수의 활용 - 회문 검사
회문 - 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장 ex) 기러기 토마토 스위스 별똥별 역삼역
Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
"abcba" # True- 해결방법
문자열을 돌면서
맨 앞의 문자와 맨 뒤의 문자,
맨 앞에서 두번째 문자와 맨 뒤에서 두번째 문자
...
를 비교하기!
A
input = "abcba"
def is_palindrome(string):
if len(string) <= 1: # 탈출경로 (문자열의 길이가 1보다 작거나 같을 때)
return True # 회문 (0이면 나눠떨어진거고 1이면 가운데글자)
if string[0] != string[-1]: # 탈출경로 (회문이 아닐때)
return False # False
return is_palindrome(string[1:-1])
print(is_palindrome(input))