《 Python 데이터 구조 와 알고리즘 》
《Data Structures and Algorithms Using Python》
1 장: ADT 추상 데이터 형식, 데이터 와 조작 정의
ADT: 추상 적 인 데이터 형식 이 무엇 인지 데이터 구 조 를 배 운 사람 은 모두 알 고 있 을 것 이다.
How to select datastructures for ADT
다음 코드 는 간단 한 예제 입 니 다. 예 를 들 어 간단 한 Bag 류 를 실현 하고 먼저 가지 고 있 는 조작 을 정의 한 다음 에 우 리 는 유형의 magic method 로 이런 방법 을 실현 합 니 다.
class Bag:
"""
constructor:
size
contains
append
remove
iter
"""
def __init__(self):
self._items = list()
def __len__(self):
return len(self._items)
def __contains__(self, item):
return item in self._items
def add(self, item):
self._items.append(item)
def remove(self, item):
assert item in self._items, 'item must in the bag'
return self._items.remove(item)
def __iter__(self):
return _BagIterator(self._items)
class _BagIterator:
""" """
def __init__(self, seq):
self._bag_items = seq
self._cur_item = 0
def __iter__(self):
return self
def __next__(self):
if self._cur_item < len(self._bag_items):
item = self._bag_items[self._cur_item]
self._cur_item += 1
return item
else:
raise StopIteration
b = Bag()
b.add(1)
b.add(2)
for i in b: # for __iter__ , __next__
print(i)
"""
# for
i = b.__iter__()
while True:
try:
item = i.__next__()
print(item)
except StopIteration:
break
"""
2 장: array vs list
array: 길이 가 정 해 져 있 고 조작 이 제한 되 어 있 지만 메모 리 를 절약 합 니 다.내 인생 에서 아직 사용 해 본 적 이 없 는 것 같 지만 python 3.5 에서 나 는 확실히 array 류 가 있어 서 import array 로 직접 가 져 올 수 있다.
list: 메모 리 를 미리 분배 하고 조작 이 풍부 하지만 메모 리 를 소모 합 니 다.나 는 sys. getsize of 로 실험 을 했다.저 는 개인 적 으로 C + STL 의 vector 와 유사 하 게 가장 자주 사용 하 는 데이터 구 조 를 이해 합 니 다.
array 의 ADT 를 실현 합 니 다:
import ctypes
class Array:
def __init__(self, size):
assert size > 0, 'array size must be > 0'
self._size = size
PyArrayType = ctypes.py_object * size
self._elements = PyArrayType()
self.clear(None)
def __len__(self):
return self._size
def __getitem__(self, index):
assert index >= 0 and index < len(self), 'out of range'
return self._elements[index]
def __setitem__(self, index, value):
assert index >= 0 and index < len(self), 'out of range'
self._elements[index] = value
def clear(self, value):
""" value """
for i in range(len(self)):
self._elements[i] = value
def __iter__(self):
return _ArrayIterator(self._elements)
class _ArrayIterator:
def __init__(self, items):
self._items = items
self._idx = 0
def __iter__(self):
return self
def __next__(self):
if self._idex < len(self._items):
val = self._items[self._idx]
self._idex += 1
return val
else:
raise StopIteration
Two-Demensional Arrays
class Array2D:
"""
Array2D(nrows, ncols): constructor
numRows()
numCols()
clear(value)
getitem(i, j)
setitem(i, j, val)
"""
def __init__(self, numrows, numcols):
self._the_rows = Array(numrows) #
for i in range(numrows):
self._the_rows[i] = Array(numcols)
@property
def numRows(self):
return len(self._the_rows)
@property
def NumCols(self):
return len(self._the_rows[0])
def clear(self, value):
for row in range(self.numRows):
row.clear(value)
def __getitem__(self, ndx_tuple): # ndx_tuple: (x, y)
assert len(ndx_tuple) == 2
row, col = ndx_tuple[0], ndx_tuple[1]
assert (row >= 0 and row < self.numRows and
col >= 0 and col < self.NumCols)
the_1d_array = self._the_rows[row]
return the_1d_array[col]
def __setitem__(self, ndx_tuple, value):
assert len(ndx_tuple) == 2
row, col = ndx_tuple[0], ndx_tuple[1]
assert (row >= 0 and row < self.numRows and
col >= 0 and col < self.NumCols)
the_1d_array = self._the_rows[row]
the_1d_array[col] = value
The Matrix ADT, m 줄, n 열.이것 은 역시 pandas 로 행렬 을 처리 하 는 것 이 좋 습 니 다. 스스로 실현 하 는 것 이 비교적 * 아 픕 니 다.
class Matrix:
""" pandas DataFrame
Matrix(rows, ncols): constructor
numCols()
getitem(row, col)
setitem(row, col, val)
scaleBy(scalar): scalar
transpose(): transpose
add(rhsMatrix): size must be the same
subtract(rhsMatrix)
multiply(rhsMatrix)
"""
def __init__(self, numRows, numCols):
self._theGrid = Array2D(numRows, numCols)
self._theGrid.clear(0)
@property
def numRows(self):
return len(self._theGrid.numRows())
@property
def NumCols(self):
return len(self._theGrid.numCols())
def __getitem__(self, ndxTuple):
return self._theGrid[ndxTuple[0], ndxTuple[1]]
def __setitem__(self, ndxTuple, scalar):
self._theGrid[ndxTuple[0], ndxTuple[1]] = scalar
def scaleBy(self, scalar):
for r in range(self.numRows):
for c in range(self.numCols):
self[r, c] *= scalar
def __add__(self, rhsMatrix):
assert (rhsMatrix.numRows == self.numRows and
rhsMatrix.numCols == self.numCols)
newMartrix = Matrix(self.numRows, self.numCols)
for r in range(self.numRows):
for c in range(self.numCols):
newMartrix[r, c] = self[r, c] + rhsMatrix[r, c]
3 장: Sets and Maps
list 를 제외 하고 가장 많이 사용 되 는 것 은 python 에 내 장 된 set 와 dict 일 것 입 니 다.
sets ADT
A set is a container that stores a collection of unique values over a given comparable domain in which the stored values have no particular ordering.
class Set:
""" list set ADT
Set()
length()
contains(element)
add(element)
remove(element)
equals(element)
isSubsetOf(setB)
union(setB)
intersect(setB)
difference(setB)
iterator()
"""
def __init__(self):
self._theElements = list()
def __len__(self):
return len(self._theElements)
def __contains__(self, element):
return element in self._theElements
def add(self, element):
if element not in self:
self._theElements.append(element)
def remove(self, element):
assert element in self, 'The element must be set'
self._theElements.remove(element)
def __eq__(self, setB):
if len(self) != len(setB):
return False
else:
return self.isSubsetOf(setB)
def isSubsetOf(self, setB):
for element in self:
if element not in setB:
return False
return True
def union(self, setB):
newSet = Set()
newSet._theElements.extend(self._theElements)
for element in setB:
if element not in self:
newSet._theElements.append(element)
return newSet
Maps or Dict: 키 값 쌍, python 내 부 는 hash 로 이 루어 집 니 다.
class Map:
""" Map ADT list implemention
Map()
length()
contains(key)
add(key, value)
remove(key)
valudOf(key)
iterator()
"""
def __init__(self):
self._entryList = list()
def __len__(self):
return len(self._entryList)
def __contains__(self, key):
ndx = self._findPosition(key)
return ndx is not None
def add(self, key, value):
ndx = self._findPosition(key)
if ndx is not None:
self._entryList[ndx].value = value
return False
else:
entry = _MapEntry(key, value)
self._entryList.append(entry)
return True
def valueOf(self, key):
ndx = self._findPosition(key)
assert ndx is not None, 'Invalid map key'
return self._entryList[ndx].value
def remove(self, key):
ndx = self._findPosition(key)
assert ndx is not None, 'Invalid map key'
self._entryList.pop(ndx)
def __iter__(self):
return _MapIterator(self._entryList)
def _findPosition(self, key):
for i in range(len(self)):
if self._entryList[i].key == key:
return i
return None
class _MapEntry: # or use collections.namedtuple('_MapEntry', 'key,value')
def __init__(self, key, value):
self.key = key
self.value = value
The multiArray ADT, 다 차원 배열 은 보통 1 차원 배열 로 시 뮬 레이 션 을 한 다음 에 계산 을 통 해 요 소 를 가 져 옵 니 다.
class MultiArray:
""" row-major or column-marjor ordering, this is row-major ordering
MultiArray(d1, d2, ...dn)
dims(): the number of dimensions
length(dim): the length of given array dimension
clear(value)
getitem(i1, i2, ... in), index(i1,i2,i3) = i1*(d2*d3) + i2*d3 + i3
setitem(i1, i2, ... in)
:index(i1,i2,...in) = i1*f1 + i2*f2 + ... + i(n-1)*f(n-1) + in*1
"""
def __init__(self, *dimensions):
# Implementation of MultiArray ADT using a 1-D # array, 。。。
assert len(dimensions) > 1, 'The array must have 2 or more dimensions'
self._dims = dimensions
# Compute to total number of elements in the array
size = 1
for d in dimensions:
assert d > 0, 'Dimensions must be > 0'
size *= d
# Create the 1-D array to store the elements
self._elements = Array(size)
# Create a 1-D array to store the equation factors
self._factors = Array(len(dimensions))
self._computeFactors()
@property
def numDims(self):
return len(self._dims)
def length(self, dim):
assert dim > 0 and dim < len(self._dims), 'Dimension component out of range'
return self._dims[dim-1]
def clear(self, value):
self._elements.clear(value)
def __getitem__(self, ndxTuple):
assert len(ndxTuple) == self.numDims, 'Invalid # of array subscripts'
index = self._computeIndex(ndxTuple)
assert index is not None, 'Array subscript out of range'
return self._elements[index]
def __setitem__(self, ndxTuple, value):
assert len(ndxTuple) == self.numDims, 'Invalid # of array subscripts'
index = self._computeIndex(ndxTuple)
assert index is not None, 'Array subscript out of range'
self._elements[index] = value
def _computeIndex(self, ndxTuple):
# using the equation: i1*f1 + i2*f2 + ... + in*fn
offset = 0
for j in range(len(ndxTuple)):
if ndxTuple[j] < 0 or ndxTuple[j] >= self._dims[j]:
return None
else:
offset += ndexTuple[j] * self._factors[j]
return offset
4 장: 알고리즘 분석
일반적으로 큰 O 표기 법 을 사용 하여 알고리즘 의 평균 시간 복잡 도 를 평가 합 니 다. 1 < log (n) < n < nlog (n) < n ^ 2 < n ^ 3 < a ^ n.자주 사용 하 는 데이터 구조 작업 의 평균 시간 복잡 도 를 이해 하 는 것 은 더욱 효율 적 인 데이터 구 조 를 사용 하 는 데 유리 하 다. 물론 시간 과 공간 에서 평가 해 야 한다. 어떤 조작 은 심지어 퇴화 하기 도 한다. 예 를 들 어 list 의 append 작업 은 list 공간 이 부족 하면 새로운 공간 을 개척 하고 작업 복잡 도 는 O (n) 로 퇴화 하 며 가끔 은 평균 노점 분석 (amortized) 을 사용 해 야 한다.
5 장: 검색 및 정렬
정렬 과 찾기 는 가장 기본 적 이 고 빈번 한 작업 입 니 다. python 에는 in 연산 자 와 bisect 2 분 작업 모듈 이 내장 되 어 있 습 니 다. 정렬 작업 을 수행 하기 위해 sorted 방법 이 내장 되 어 있 습 니 다.2 점 과 빠 른 줄 도 면접 에서 자주 볼 수 있 는 것 으로 본 장 은 기본 적 인 정렬 과 찾기 를 말한다.
def binary_search(sorted_seq, val):
""" bisect.bisect_left """
low = 0
high = len(sorted_seq) - 1
while low <= high:
mid = (high + low) // 2
if sorted_seq[mid] == val:
return mid
elif val < sorted_seq[mid]:
high = mid - 1
else:
low = mid + 1
return low
def bubble_sort(seq): # O(n^2), n(n-1)/2 = 1/2(n^2 + n)
n = len(seq)
for i in range(n):
for j in range(n-1): #
if seq[j] > seq[i]:
seq[j], seq[i] = seq[i], seq[j] # swap seq[j], seq[i]
# , flag,
def select_sort(seq):
""" , , """
n = len(seq)
for i in range(n-1):
min_idx = i # assume the ith element is the smallest
for j in range(i+1, n):
if seq[j] < seq[min_idx]: # find the minist element index
min_idx = j
if min_idx != i: # swap
seq[i] = seq[min_idx]
def insertion_sort(seq):
""" , ��� """
n = len(seq)
for i in range(1, n):
value = seq[i] # save the value to be positioned
# find the position where value fits in the ordered part of the list
pos = i
while pos > 0 and value < seq[pos-1]:
# Shift the items to the right during the search
seq[pos] = seq[pos-1]
pos -= 1
seq[pos] = value
def merge_sorted_list(listA, listB):
""" """
new_list = list()
a = b = 0
while a < len(listA) and b < len(listB):
if listA[a] < listB[b]:
new_list.append(listA[a])
a += 1
else:
new_list.append(listB[b])
b += 1
while a < len(listA):
new_list.append(listA[a])
a += 1
while b < len(listB):
new_list.append(listB[b])
b += 1
return new_list
6 장: 링크 된 구조
list 는 가장 자주 사용 하 는 데이터 구조 이지 만 list 는 중간 에 요 소 를 증감 할 때 효율 이 낮 습 니 다. 이때 linked list 가 더욱 적합 합 니 다. 단점 은 요 소 를 얻 는 평균 시간 복잡 도가 O (n) 로 바 뀌 었 다 는 것 입 니 다.
#
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
def travsersal(head, callback):
curNode = head
while curNode is not None:
callback(curNode.data)
curNode = curNode.next
def unorderdSearch(head, target):
curNode = head
while curNode is not None and curNode.data != target:
curNode = curNode.next
return curNode is not None
# Given the head pointer, prepend an item to an unsorted linked list.
def prepend(head, item):
newNode = ListNode(item)
newNode.next = head
head = newNode
# Given the head reference, remove a target from a linked list
def remove(head, target):
predNode = None
curNode = head
while curNode is not None and curNode.data != target:
#
predNode = curNode
curNode = curNode.data
if curNode is not None:
if curNode is head:
head = curNode.next
else:
predNode.next = curNode.next
7 장: 스 택
스 택 도 컴퓨터 에서 많이 사용 하 는 데이터 구조 입 니 다. 스 택 은 후진 에서 먼저 나 오 는 데이터 구조 로 한 통 에 접 시 를 넣 는 것 으로 이해 할 수 있 습 니 다. 먼저 넣 은 것 은 땅 에 깔 리 고 접 시 를 꺼 낼 때 나중에 놓 은 것 은 먼저 꺼 냅 니 다.
class Stack:
""" Stack ADT, using a python list
Stack()
isEmpty()
length()
pop(): assert not empty
peek(): assert not empty, return top of non-empty stack without removing it
push(item)
"""
def __init__(self):
self._items = list()
def isEmpty(self):
return len(self) == 0
def __len__(self):
return len(self._items)
def peek(self):
assert not self.isEmpty()
return self._items[-1]
def pop(self):
assert not self.isEmpty()
return self._items.pop()
def push(self, item):
self._items.append(item)
class Stack:
""" Stack ADT, use linked list
list , push ,list O(n)
linked list O(1)
"""
def __init__(self):
self._top = None # top , _StackNode or None
self._size = 0 # int
def isEmpty(self):
return self._top is None
def __len__(self):
return self._size
def peek(self):
assert not self.isEmpty()
return self._top.item
def pop(self):
assert not self.isEmpty()
node = self._top
self.top = self._top.next
self._size -= 1
return node.item
def _push(self, item):
self._top = _StackNode(item, self._top)
self._size += 1
class _StackNode:
def __init__(self, item, link):
self.item = item
self.next = link
8 장: Queues
대기 열 도 자주 사용 하 는 데이터 구조 입 니 다. 예 를 들 어 메 시 지 를 보 내 는 등 celery 는 redis 가 제공 하 는 list 를 사용 하여 메시지 대기 열 을 실현 할 수 있 습 니 다.이 장 에서 우 리 는 list 와 linked list 로 대기 열과 우선 순위 대기 열 을 실현 합 니 다.
class Queue:
""" Queue ADT, use list。list , push pop O(n)
Queue()
isEmpty()
length()
enqueue(item)
dequeue()
"""
def __init__(self):
self._qList = list()
def isEmpty(self):
return len(self) == 0
def __len__(self):
return len(self._qList)
def enquue(self, item):
self._qList.append(item)
def dequeue(self):
assert not self.isEmpty()
return self._qList.pop(0)
from array import Array # Array Array ADT
class Queue:
"""
circular Array , 。list append pop ,
O(1), 。
"""
def __init__(self, maxSize):
self._count = 0
self._front = 0
self._back = maxSize - 1
self._qArray = Array(maxSize)
def isEmpty(self):
return self._count == 0
def isFull(self):
return self._count == len(self._qArray)
def __len__(self):
return len(self._count)
def enqueue(self, item):
assert not self.isFull()
maxSize = len(self._qArray)
self._back = (self._back + 1) % maxSize #
self._qArray[self._back] = item
self._count += 1
def dequeue(self):
assert not self.isFull()
item = self._qArray[self._front]
maxSize = len(self._qArray)
self._front = (self._front + 1) % maxSize
self._count -= 1
return item
class _QueueNode:
def __init__(self, item):
self.item = item
class Queue:
""" Queue ADT, linked list 。 ,
linked list 。
"""
def __init__(self):
self._qhead = None
self._qtail = None
self._qsize = 0
def isEmpty(self):
return self._qhead is None
def __len__(self):
return self._count
def enqueue(self, item):
node = _QueueNode(item) #
if self.isEmpty():
self._qhead = node
else:
self._qtail.next = node
self._qtail = node
self._qcount += 1
def dequeue(self):
assert not self.isEmpty(), 'Can not dequeue from an empty queue'
node = self._qhead
if self._qhead is self._qtail:
self._qtail = None
self._qhead = self._qhead.next #
self._count -= 1
return node.item
class UnboundedPriorityQueue:
""" PriorityQueue ADT: item p, dequeue
:
- bounded PriorityQueue: [0...p)
- unbounded PriorityQueue:
PriorityQueue()
BPriorityQueue(numLevels): create a bounded PriorityQueue with priority in range
[0, numLevels-1]
isEmpty()
length()
enqueue(item, priority): bounded PriorityQueue, priority
dequeue(): , FIFO
- :
1. , , O(n)
2. , , O(1)
( list list.append pop )
"""
from collections import namedtuple
_PriorityQEntry = namedtuple('_PriorityQEntry', 'item, priority')
# 1, list unbounded PriorityQueue
def __init__(self):
self._qlist = list()
def isEmpty(self):
return len(self) == 0
def __len__(self):
return len(self._qlist)
def enqueue(self, item, priority):
entry = UnboundedPriorityQueue._PriorityQEntry(item, priority)
self._qlist.append(entry)
def deque(self):
assert not self.isEmpty(), 'can not deque from an empty queue'
highest = self._qlist[0].priority
for i in range(len(self)): # O(n),
if self._qlist[i].priority < highest:
highest = self._qlist[i].priority
entry = self._qlist.pop(highest)
return entry.item
class BoundedPriorityQueue:
""" BoundedPriorityQueue ADT, linked list 。 BoundedPriorityQueue
BoundedPriorityQueue ? BoundedPriorityQueue [0, maxPriority-1]
UnboundedPriorityQueue, item,
O(n) , BoundedPriorityQueue, ,
。 , 。
( , )
qlist
[0] -> ["white"]
[1]
[2] -> ["black", "green"]
[3] -> ["purple", "yellow"]
"""
# Implementation of the bounded Priority Queue ADT using an array of #
# queues in which the queues are implemented using a linked list.
from array import Array # ADT
def __init__(self, numLevels):
self._qSize = 0
self._qLevels = Array(numLevels)
for i in range(numLevels):
self._qLevels[i] = Queue() # linked list Queue
def isEmpty(self):
return len(self) == 0
def __len__(self):
return len(self._qSize)
def enqueue(self, item, priority):
assert priority >= 0 and priority < len(self._qLevels), 'invalid priority'
self._qLevel[priority].enquue(item) # priority
def deque(self):
assert not self.isEmpty(), 'can not deque from an empty queue'
i = 0
p = len(self._qLevels)
while i < p and not self._qLevels[i].isEmpty(): #
i += 1
return self._qLevels[i].dequeue()
9 장: 고급 링크 목록
이전에 소 개 된 단일 체인 테이블 은 하나의 체인 테이블 노드 에 data 와 next 필드 만 있 고 본 장 은 고급 체인 테이블 을 소개 한다.
Doubly Linked List, 더 블 링크, 각 노드 에 prev 가 앞 노드 를 가리 키 고 있 습 니 다.더 블 링크 는 텍스트 편집기 의 buffer 를 만 드 는 데 사용 할 수 있 습 니 다.
class DListNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def revTraversa(tail):
curNode = tail
while cruNode is not None:
print(curNode.data)
curNode = curNode.prev
def search_sorted_doubly_linked_list(head, tail, probe, target):
""" probing technique , , O(n)
searching a sorted doubly linked list using the probing technique
Args:
head (DListNode obj)
tail (DListNode obj)
probe (DListNode or None)
target (DListNode.data): data to search
"""
if head is None: # make sure list is not empty
return False
if probe is None: # if probe is null, initialize it to first node
probe = head
# if the target comes before the probe node, we traverse backward, otherwise
# traverse forward
if target < probe.data:
while probe is not None and target <= probe.data:
if target == probe.dta:
return True
else:
probe = probe.prev
else:
while probe is not None and target >= probe.data:
if target == probe.data:
return True
else:
probe = probe.next
return False
def insert_node_into_ordered_doubly_linekd_list(value):
""" , , """
newnode = DListNode(value)
if head is None: # empty list
head = newnode
tail = head
elif value < head.data: # insert before head
newnode.next = head
head.prev = newnode
head = newnode
elif value > tail.data: # insert after tail
newnode.prev = tail
tail.next = newnode
tail = newnode
else: # insert into middle
node = head
while node is not None and node.data < value:
node = node.next
newnode.next = node
newnode.prev = node.prev
node.prev.next = newnode
node.prev = newnode
순환 링크
def travrseCircularList(listRef):
curNode = listRef
done = listRef is None
while not None:
curNode = curNode.next
print(curNode.data)
done = curNode is listRef #
def searchCircularList(listRef, target):
curNode = listRef
done = listRef is None
while not done:
curNode = curNode.next
if curNode.data == target:
return True
else:
done = curNode is listRef or curNode.data > target
return False
def add_newnode_into_ordered_circular_linked_list(listRef, value):
"""
1. ;2. ;3. ;4.
"""
newnode = ListNode(value)
if listRef is None: # empty list
listRef = newnode
newnode.next = newnode
elif value < listRef.next.data: # insert in front
newnode.next = listRef.next
listRef.next = newnode
elif value > listRef.data: # insert in back
newnode.next = listRef.next
listRef.next = newnode
listRef = newnode
else: # insert in the middle
preNode = None
curNode = listRef
done = listRef is None
while not done:
preNode = curNode
preNode = curNode.next
done = curNode is listRef or curNode.data > value
newnode.next = curNode
preNode.next = newnode
10 장: Recursion
Recursion is a process for solving problems by subdividing a larger problem into smaller cases of the problem itself and then solving the smaller, more trivial parts.
재 귀 함수: 자신의 함수 호출
# : , ,
def printRev(n):
if n > 0:
print(n)
printRev(n-1)
printRev(3) # 10 1
# ,print
def printInOrder(n):
if n > 0:
printInOrder(n-1)
print(n) # n==1 ,
# , print , n==1, ,
printInOrder(3) #
Properties of Recursion: stack 으로 해결 하 는 문 제 는 재 귀적 으로 해결 할 수 있 습 니 다.
# Recursive Binary Search
def recBinarySearch(target, theSeq, first, last):
#
if first > last: # 1
return False
else:
mid = (first + last) // 2
if theSeq[mid] == target:
return True # 2
elif theSeq[mid] > target:
return recBinarySearch(target, theSeq, first, mid - 1)
else:
return recBinarySearch(target, theSeq, mid + 1, last)
11 장: Hash Tables
비교 검색 (선형 검색, 질서 있 는 배열 의 2 분 검색) 을 바탕 으로 가장 좋 은 시간 복잡 도 는 O (logn) 에 만 도달 할 수 있 습 니 다. hash 를 이용 하여 O (1) 검색 을 실현 할 수 있 습 니 다. python 내 장 된 dict 의 실현 방식 은 hash 입 니 다. dict 의 key 가 반드시 실현 되 어야 한 다 는 것 을 알 게 될 것 입 니 다.hash__와eq__방법의
Hashing: hashing is the process of mapping a search a key to a limited range of array indeices with the goal of providing direct access to the keys.
hash 방법 은 키 에 hash 값 을 계산 하 는 데 사용 되 는 hash 함수 가 있 습 니 다.키 가 hash 함수 에 따라 계 산 된 아래 표 시 를 계산 하 는 동시에 충돌 이 발생 합 니 다.충돌 을 해결 하 는 방법 은 여러 가지 가 있 습 니 다. 예 를 들 어 모든 슬롯 을 링크 로 만 들 고 충돌 할 때마다 이 슬롯 링크 의 끝 에 놓 지만 조회 시간 은 퇴화 되 고 더 이상 O (1) 가 아 닙 니 다.또 하나의 탐사 방식 은 키 의 홈 이 충돌 할 때 하나의 계산 방식 에 따라 다음 빈 홈 을 찾 아 저장 하고 탐사 방식 은 선형 탐사, 이차 탐사 법 등 이 있 으 며 cpython 해석 기 는 이차 탐사 법 을 사용한다.또 하나의 문 제 는 python 이 사용 하 는 슬롯 의 수량 이 미리 분 배 된 2 / 3 보다 많 을 때 메모 리 를 재배 치 하고 예전 의 데 이 터 를 복사 하기 때문에 가끔 dict 의 add 작업 대가 가 비교적 높 고 공간 을 희생 하지만 O (1) 의 조회 효율 을 항상 보장 할 수 있다 는 것 이다.만약 대량의 데이터 가 있다 면, Bloomfilter 나 redis 가 제공 하 는 HyperLogLog 를 사용 하 는 것 을 권장 합 니 다.
관심 이 있다 면 c 해석 기 가 어떻게 실현 하 는 python dict 대상: Python dictionary implementation 을 소개 합 니 다.우 리 는 Python 을 사용 하여 유사 한 hash 구 조 를 실현 합 니 다.
import ctypes
class Array: # ADT, HashMap
def __init__(self, size):
assert size > 0, 'array size must be > 0'
self._size = size
PyArrayType = ctypes.py_object * size
self._elements = PyArrayType()
self.clear(None)
def __len__(self):
return self._size
def __getitem__(self, index):
assert index >= 0 and index < len(self), 'out of range'
return self._elements[index]
def __setitem__(self, index, value):
assert index >= 0 and index < len(self), 'out of range'
self._elements[index] = value
def clear(self, value):
""" value """
for i in range(len(self)):
self._elements[i] = value
def __iter__(self):
return _ArrayIterator(self._elements)
class _ArrayIterator:
def __init__(self, items):
self._items = items
self._idx = 0
def __iter__(self):
return self
def __next__(self):
if self._idx < len(self._items):
val = self._items[self._idx]
self._idx += 1
return val
else:
raise StopIteration
class HashMap:
""" HashMap ADT , python dict
:
1. HashMap.UNUSED。 , UNUSEd
2. remove , HashMap.EMPTY, key
3. _MapEntry
"""
class _MapEntry: #
def __init__(self, key, value):
self.key = key
self.value = value
UNUSED = None # , , is
EMPTY = _MapEntry(None, None) #
def __init__(self):
self._table = Array(7) # 7
self._count = 0
# 2/3 ,load factor = 2/3
self._maxCount = len(self._table) - len(self._table) // 3
def __len__(self):
return self._count
def __contains__(self, key):
slot = self._findSlot(key, False)
return slot is not None
def add(self, key, value):
if key in self: # value
slot = self._findSlot(key, False)
self._table[slot].value = value
return False
else:
slot = self._findSlot(key, True)
self._table[slot] = HashMap._MapEntry(key, value)
self._count += 1
if self._count == self._maxCount: # 2/3 rehash
self._rehash()
return True
def valueOf(self, key):
slot = self._findSlot(key, False)
assert slot is not None, 'Invalid map key'
return self._table[slot].value
def remove(self, key):
""" remove EMPTY"""
assert key in self, 'Key error %s' % key
slot = self._findSlot(key, forInsert=False)
value = self._table[slot].value
self._count -= 1
self._table[slot] = HashMap.EMPTY
return value
def __iter__(self):
return _HashMapIteraotr(self._table)
def _slot_can_insert(self, slot):
return (self._table[slot] is HashMap.EMPTY or
self._table[slot] is HashMap.UNUSED)
def _findSlot(self, key, forInsert=False):
""" , ,
Args:
forInsert (bool): if the search is for an insertion
Returns:
slot or None
"""
slot = self._hash1(key)
step = self._hash2(key)
_len = len(self._table)
if not forInsert: # key
while self._table[slot] is not HashMap.UNUSED:
# UNUSED,
if self._table[slot] is HashMap.EMPTY:
slot = (slot + step) % _len
continue
elif self._table[slot].key == key:
return slot
slot = (slot + step) % _len
return None
else: # key
while not self._slot_can_insert(slot): #
slot = (slot + step) % _len
return slot
def _rehash(self): # 2/3 table
origTable = self._table
newSize = len(self._table) * 2 + 1 # 2*n+1
self._table = Array(newSize)
self._count = 0
self._maxCount = newSize - newSize // 3
# key value table
for entry in origTable:
if entry is not HashMap.UNUSED and entry is not HashMap.EMPTY:
slot = self._findSlot(entry.key, True)
self._table[slot] = entry
self._count += 1
def _hash1(self, key):
""" key hash """
return abs(hash(key)) % len(self._table)
def _hash2(self, key):
""" key """
return 1 + abs(hash(key)) % (len(self._table)-2)
class _HashMapIteraotr:
def __init__(self, array):
self._array = array
self._idx = 0
def __iter__(self):
return self
def __next__(self):
if self._idx < len(self._array):
if self._array[self._idx] is not None and self._array[self._idx].key is not None:
key = self._array[self._idx].key
self._idx += 1
return key
else:
self._idx += 1
else:
raise StopIteration
def print_h(h):
for idx, i in enumerate(h):
print(idx, i)
print('
')
def test_HashMap():
""" , """
h = HashMap()
assert len(h) == 0
h.add('a', 'a')
assert h.valueOf('a') == 'a'
assert len(h) == 1
a_v = h.remove('a')
assert a_v == 'a'
assert len(h) == 0
h.add('a', 'a')
h.add('b', 'b')
assert len(h) == 2
assert h.valueOf('b') == 'b'
b_v = h.remove('b')
assert b_v == 'b'
assert len(h) == 1
h.remove('a')
assert len(h) == 0
n = 10
for i in range(n):
h.add(str(i), i)
assert len(h) == n
print_h(h)
for i in range(n):
assert str(i) in h
for i in range(n):
h.remove(str(i))
assert len(h) == 0
12 장: 고급 정렬
제5 장 은 기본 적 인 정렬 알고리즘 을 소개 하고 이 장 은 고급 정렬 알고리즘 을 소개 한다.
병합 정렬 (mergesort): 분할 방법
def merge_sorted_list(listA, listB):
""" ,O(max(m, n)) ,m n """
print('merge left right list', listA, listB, end='')
new_list = list()
a = b = 0
while a < len(listA) and b < len(listB):
if listA[a] < listB[b]:
new_list.append(listA[a])
a += 1
else:
new_list.append(listB[b])
b += 1
while a < len(listA):
new_list.append(listA[a])
a += 1
while b < len(listB):
new_list.append(listB[b])
b += 1
print(' ->', new_list)
return new_list
def mergesort(theList):
""" O(nlogn),log , n
mergesort: divided and conquer
1.
2.
"""
print(theList) # ,
if len(theList) <= 1: #
return theList
else:
mid = len(theList) // 2
#
left_half = mergesort(theList[:mid])
right_half = mergesort(theList[mid:])
#
newList = merge_sorted_list(left_half, right_half)
return newList
"""
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[10, 9, 8, 7, 6]
[10, 9]
[10]
[9]
merge left right list [10] [9] -> [9, 10]
[8, 7, 6]
[8]
[7, 6]
[7]
[6]
merge left right list [7] [6] -> [6, 7]
merge left right list [8] [6, 7] -> [6, 7, 8]
merge left right list [9, 10] [6, 7, 8] -> [6, 7, 8, 9, 10]
[5, 4, 3, 2, 1]
[5, 4]
[5]
[4]
merge left right list [5] [4] -> [4, 5]
[3, 2, 1]
[3]
[2, 1]
[2]
[1]
merge left right list [2] [1] -> [1, 2]
merge left right list [3] [1, 2] -> [1, 2, 3]
merge left right list [4, 5] [1, 2, 3] -> [1, 2, 3, 4, 5]
"""
빠 른 정렬
def quicksort(theSeq, first, last):
"""
quicksort : , , (pivot)
1. pivot ,pivot ,
2. , ( 2)
3. pivot
"""
if first < last:
pos = partitionSeq(theSeq, first, last)
#
quicksort(theSeq, first, pos - 1)
quicksort(theSeq, pos + 1, last)
def partitionSeq(theSeq, first, last):
""" , pivot , pivot """
pivot = theSeq[first]
print('before partitionSeq', theSeq)
left = first + 1
right = last
while True:
# pivot
while left <= right and theSeq[left] < pivot:
left += 1
# pivot
while right >= left and theSeq[right] >= pivot:
right -= 1
if right < left:
break
else:
theSeq[left], theSeq[right] = theSeq[right], theSeq[left]
# pivot
theSeq[first], theSeq[right] = theSeq[right], theSeq[first]
print('after partitionSeq {}: {}\t'.format(theSeq, pivot))
return right # pivot
def test_partitionSeq():
l = [0,1,2,3,4]
assert partitionSeq(l, 0, len(l)-1) == 0
l = [4,3,2,1,0]
assert partitionSeq(l, 0, len(l)-1) == 4
l = [2,3,0,1,4]
assert partitionSeq(l, 0, len(l)-1) == 2
test_partitionSeq()
def test_quicksort():
def _is_sorted(seq):
for i in range(len(seq)-1):
if seq[i] > seq[i+1]:
return False
return True
from random import randint
for i in range(100):
_len = randint(1, 100)
to_sort = []
for i in range(_len):
to_sort.append(randint(0, 100))
quicksort(to_sort, 0, len(to_sort)-1) # ,
print(to_sort)
assert _is_sorted(to_sort)
test_quicksort()
빠 른 배열 의 paritionseq 작업 을 이용 하여 우 리 는 또 다른 알고리즘 을 실현 할 수 있 습 니 다. nthelement, 무질서 한 배열 의 k 번 째 요 소 를 빠르게 찾 습 니 다.
def nth_element(seq, beg, end, k):
if beg == end:
return seq[beg]
pivot_index = partitionSeq(seq, beg, end)
if pivot_index == k:
return seq[k]
elif pivot_index > k:
return nth_element(seq, beg, pivot_index-1, k)
else:
return nth_element(seq, pivot_index+1, end, k)
def test_nth_element():
from random import shuffle
n = 10
l = list(range(n))
shuffle(l)
print(l)
for i in range(len(l)):
assert nth_element(l, 0, len(l)-1, i) == i
test_nth_element()
13 장: 바 이 너 리 트 리
The binary Tree: 이 진 트 리, 노드 마다 많이 하면 두 개의 키 노드 만 있 습 니 다.
class _BinTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# depth-first
def preorderTrav(subtree):
""" ( ) """
if subtree is not None:
print(subtree.data)
preorderTrav(subtree.left)
preorderTrav(subtree.right)
def inorderTrav(subtree):
""" ( ) """
if subtree is not None:
preorderTrav(subtree.left)
print(subtree.data)
preorderTrav(subtree.right)
def postorderTrav(subtree):
""" ( ) """
if subtree is not None:
preorderTrav(subtree.left)
preorderTrav(subtree.right)
print(subtree.data)
# (bradth-First Traversal): , queue
def breadthFirstTrav(bintree):
from queue import Queue # py3
q = Queue()
q.put(bintree)
while not q.empty():
node = q.get()
print(node.data)
if node.left is not None:
q.put(node.left)
if node.right is not None:
q.put(node.right)
class _ExpTreeNode:
__slots__ = ('element', 'left', 'right')
def __init__(self, data):
self.element = data
self.left = None
self.right = None
def __repr__(self):
return '<_exptreenode:>'.format(
self.element, self.left, self.right)
from queue import Queue
class ExpressionTree:
"""
: 。( )
*
/ \
+ -
/ \ / \
9 3 8 4
(9+3) * (8-4)
Expression Tree Abstract Data Type,
ExpressionTree(expStr): user string as constructor param
evaluate(varDict): evaluates the expression and returns the numeric result
toString(): constructs and retutns a string represention of the expression
Usage:
vars = {'a': 5, 'b': 12}
expTree = ExpressionTree("(a/(b-3))")
print('The result = ', expTree.evaluate(vars))
"""
def __init__(self, expStr):
self._expTree = None
self._buildTree(expStr)
def evaluate(self, varDict):
return self._evalTree(self._expTree, varDict)
def __str__(self):
return self._buildString(self._expTree)
def _buildString(self, treeNode):
""" , """
# print(treeNode)
if treeNode.left is None and treeNode.right is None:
return str(treeNode.element) #
else:
expStr = '('
expStr += self._buildString(treeNode.left)
expStr += str(treeNode.element)
expStr += self._buildString(treeNode.right)
expStr += ')'
return expStr
def _evalTree(self, subtree, varDict):
# , ,
if subtree.left is None and subtree.right is None:
#
if subtree.element >= '0' and subtree.element <= '9':
return int(subtree.element)
else: #
assert subtree.element in varDict, 'invalid variable.'
return varDict[subtree.element]
else: #
lvalue = self._evalTree(subtree.left, varDict)
rvalue = self._evalTree(subtree.right, varDict)
print(subtree.element)
return self._computeOp(lvalue, subtree.element, rvalue)
def _computeOp(self, left, op, right):
assert op
op_func = {
'+': lambda left, right: left + right, # or import operator, operator.add
'-': lambda left, right: left - right,
'*': lambda left, right: left * right,
'/': lambda left, right: left / right,
'%': lambda left, right: left % right,
}
return op_func[op](left, right)
def _buildTree(self, expStr):
expQ = Queue()
for token in expStr: #
expQ.put(token)
self._expTree = _ExpTreeNode(None) # root
self._recBuildTree(self._expTree, expQ)
def _recBuildTree(self, curNode, expQ):
token = expQ.get()
if token == '(':
curNode.left = _ExpTreeNode(None)
self._recBuildTree(curNode.left, expQ)
# next token will be an operator: + = * / %
curNode.element = expQ.get()
curNode.right = _ExpTreeNode(None)
self._recBuildTree(curNode.right, expQ)
# the next token will be ')', remmove it
expQ.get()
else: # the token is a digit that has to be converted to an int.
curNode.element = token
vars = {'a': 5, 'b': 12}
expTree = ExpressionTree("((2*7)+8)")
print(expTree)
print('The result = ', expTree.evaluate(vars))
Heap (더미): 이 진 트 리 의 가장 직접적인 응용 은 바로 더 미 를 실현 하 는 것 이다.더 미 는 완전히 이 진 트 리 로 가장 많은 비 잎 노드 의 가 치 는 모두 아이 보다 크 고 가장 작은 비 잎 노드 의 가 치 는 모두 아이 보다 작다.python 에 hepq 모듈 이 내장 되 어 있 습 니 다. 예 를 들 어 내 장 된 hepq 모듈 로 쌓 기 정렬 을 실현 합 니 다.
# python heapq heap sort
def heapsort(iterable):
from heapq import heappush, heappop
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
그러나 일반적으로 무 더 기 를 실현 할 때 실제 적 으로 몇 개의 노드 로 이 루어 지 는 것 이 아니 라 배열 로 이 루어 져 효율 이 비교적 높다.왜 배열 로 이 루어 질 수 있 습 니까?완전 이 진 트 리 의 성질 때문에 아래 표 시 된 관계 로 노드 간 의 관 계 를 나 타 낼 수 있 습 니 다. MaxHeap 의 docstring 에서 설명 되 었 습 니 다.
class MaxHeap:
"""
Heaps:
, ,
Heap ,order property shape property(a complete binary tree),
,
: , sift-up
extract : , copy ,sift-down
heap, , ,
, i, :
parent = (i-1) // 2
left = 2 * i + 1
rgiht = 2 * i + 2
, , ,
。
"""
def __init__(self, maxSize):
self._elements = Array(maxSize) # Array ADT
self._count = 0
def __len__(self):
return self._count
def capacity(self):
return len(self._elements)
def add(self, value):
assert self._count < self.capacity(), 'can not add to full heap'
self._elements[self._count] = value
self._count += 1
self._siftUp(self._count - 1)
self.assert_keep_heap() # add
def extract(self):
assert self._count > 0, 'can not extract from an empty heap'
value = self._elements[0] # save root value
self._count -= 1
self._elements[0] = self._elements[self._count] # root siftDown
self._siftDown(0)
self.assert_keep_heap()
return value
def _siftUp(self, ndx):
if ndx > 0:
parent = (ndx - 1) // 2
# print(ndx, parent)
if self._elements[ndx] > self._elements[parent]: # swap
self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
self._siftUp(parent) #
def _siftDown(self, ndx):
left = 2 * ndx + 1
right = 2 * ndx + 2
# determine which node contains the larger value
largest = ndx
if (left < self._count and
self._elements[left] >= self._elements[largest] and
self._elements[left] >= self._elements[right]): # largest
largest = left
elif right < self._count and self._elements[right] >= self._elements[largest]:
largest = right
if largest != ndx:
self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
self._siftDown(largest)
def __repr__(self):
return ' '.join(map(str, self._elements))
def assert_keep_heap(self):
""" add extract , """
_len = len(self)
for i in range(0, int((_len-1)/2)): # ( )
l = 2 * i + 1
r = 2 * i + 2
if l < _len and r < _len:
assert self._elements[i] >= self._elements[l] and self._elements[i] >= self._elements[r]
def test_MaxHeap():
""" """
_len = 10
h = MaxHeap(_len)
for i in range(_len):
h.add(i)
h.assert_keep_heap()
for i in range(_len):
# ,
assert h.extract() == _len-i-1
test_MaxHeap()
def simpleHeapSort(theSeq):
""" MaxHeap , inplace """
if not theSeq:
return theSeq
_len = len(theSeq)
heap = MaxHeap(_len)
for i in theSeq:
heap.add(i)
for i in reversed(range(_len)):
theSeq[i] = heap.extract()
return theSeq
def test_simpleHeapSort():
""" """
def _is_sorted(seq):
for i in range(len(seq)-1):
if seq[i] > seq[i+1]:
return False
return True
from random import randint
assert simpleHeapSort([]) == []
for i in range(1000):
_len = randint(1, 100)
to_sort = []
for i in range(_len):
to_sort.append(randint(0, 100))
simpleHeapSort(to_sort) # ,
assert _is_sorted(to_sort)
test_simpleHeapSort()
14 장: 검색 트 리
이차 트 리 성질 찾기: 내부 노드 마다 V,
class _BSTMapNode:
__slots__ = ('key', 'value', 'left', 'right')
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
def __repr__(self):
return ' left:{}, right:{}'.format(
self.key, self.value, self.left, self.right)
__str__ = __repr__
class BSTMap:
""" BST, key payload。 BST hash Map ADT.
: V,
1. V, key V.key V 。
2. key V.key V
BST key
"""
def __init__(self):
self._root = None
self._size = 0
self._rval = None # remove
def __len__(self):
return self._size
def __iter__(self):
return _BSTMapIterator(self._root, self._size)
def __contains__(self, key):
return self._bstSearch(self._root, key) is not None
def valueOf(self, key):
node = self._bstSearch(self._root, key)
assert node is not None, 'Invalid map key.'
return node.value
def _bstSearch(self, subtree, target):
if subtree is None: # , key
return None
elif target < subtree.key:
return self._bstSearch(subtree.left, target)
elif target > subtree.key:
return self._bstSearch(subtree.right, target)
return subtree #
def _bstMinumum(self, subtree):
""" , """
if subtree is None:
return None
elif subtree.left is None:
return subtree
else:
return subtree._bstMinumum(self, subtree.left)
def add(self, key, value):
""" key value, O(N) """
node = self._bstSearch(self._root, key)
if node is not None: # if key already exists, update value
node.value = value
return False
else: # insert a new entry
self._root = self._bstInsert(self._root, key, value)
self._size += 1
return True
def _bstInsert(self, subtree, key, value):
""" """
if subtree is None:
subtree = _BSTMapNode(key, value)
elif key < subtree.key:
subtree.left = self._bstInsert(subtree.left, key, value)
elif key > subtree.key:
subtree.right = self._bstInsert(subtree.right, key, value)
# else , add key
return subtree
def remove(self, key):
""" O(N)
:
1. : None
2. : ,
3. :
(1) N S( )
(2) S key N
(3) N S( N )
"""
assert key in self, 'invalid map key'
self._root = self._bstRemove(self._root, key)
self._size -= 1
return self._rval
def _bstRemove(self, subtree, target):
# search for the item in the tree
if subtree is None:
return subtree
elif target < subtree.key:
subtree.left = self._bstRemove(subtree.left, target)
return subtree
elif target > subtree.key:
subtree.right = self._bstRemove(subtree.right, target)
return subtree
else: # found the node containing the item
self._rval = subtree.value
if subtree.left is None and subtree.right is None:
# node
return None
elif subtree.left is None or subtree.right is None:
#
if subtree.left is not None:
return subtree.left
else:
return subtree.right
else: #
successor = self._bstMinumum(subtree.right)
subtree.key = successor.key
subtree.value = successor.value
subtree.right = self._bstRemove(subtree.right, successor.key)
return subtree
def __repr__(self):
return '->'.join([str(i) for i in self])
def assert_keep_bst_property(self, subtree):
""" add delete bst """
if subtree is None:
return
if subtree.left is not None and subtree.right is not None:
assert subtree.left.value <= subtree.value
assert subtree.right.value >= subtree.value
self.assert_keep_bst_property(subtree.left)
self.assert_keep_bst_property(subtree.right)
elif subtree.left is None and subtree.right is not None:
assert subtree.right.value >= subtree.value
self.assert_keep_bst_property(subtree.right)
elif subtree.left is not None and subtree.right is None:
assert subtree.left.value <= subtree.value
self.assert_keep_bst_property(subtree.left)
class _BSTMapIterator:
def __init__(self, root, size):
self._theKeys = Array(size)
self._curItem = 0
self._bstTraversal(root)
self._curItem = 0
def __iter__(self):
return self
def __next__(self):
if self._curItem < len(self._theKeys):
key = self._theKeys[self._curItem]
self._curItem += 1
return key
else:
raise StopIteration
def _bstTraversal(self, subtree):
if subtree is not None:
self._bstTraversal(subtree.left)
self._theKeys[self._curItem] = subtree.key
self._curItem += 1
self._bstTraversal(subtree.right)
def test_BSTMap():
l = [60, 25, 100, 35, 17, 80]
bst = BSTMap()
for i in l:
bst.add(i)
def test_HashMap():
""" hash map, BST Map """
# h = HashMap()
h = BSTMap()
assert len(h) == 0
h.add('a', 'a')
assert h.valueOf('a') == 'a'
assert len(h) == 1
a_v = h.remove('a')
assert a_v == 'a'
assert len(h) == 0
h.add('a', 'a')
h.add('b', 'b')
assert len(h) == 2
assert h.valueOf('b') == 'b'
b_v = h.remove('b')
assert b_v == 'b'
assert len(h) == 1
h.remove('a')
assert len(h) == 0
_len = 10
for i in range(_len):
h.add(str(i), i)
assert len(h) == _len
for i in range(_len):
assert str(i) in h
for i in range(_len):
print(len(h))
print('bef', h)
_ = h.remove(str(i))
assert _ == i
print('aft', h)
print(len(h))
assert len(h) == 0
test_HashMap()
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.