이진 탐색은 정렬된 배열에서 원하는 value의 element를 O(logn) 이라는 좋은 성능으로 수행할 수 있는 알고리즘입니다.


문제 해결 방법은 간단합니다.


이미 정렬이 되어 있는 배열이기 때문에 배열중에 중간에 위치한 값을 체크해서 체크해야 하는 element들의 수를 반씩 줄이는 방법입니다.


import unittest
from typing import List


def binary_search(target: int, a: List[int]) -> int:
start, end = 0, len(a)
mid = (start + end) // 2
while mid != 0 and mid != len(a):
if target > a[mid]:
start = mid + 1
mid = (start + end) // 2
elif target < a[mid]:
end = mid - 1
mid = (start + end) // 2
else:
return mid

return -1


class TestCase(unittest.TestCase):
def test(self):
input_a = [i for i in range(100)]
target = 55
expected = 55

input_a2 = [i ** 2 for i in range(10)]
target2 = 81
expected2 = 9

input_a3 = [i ** 2 for i in range(10)]
target3 = -81
expected3 = -1

self.assertEqual(binary_search(target, input_a), expected)
self.assertEqual(binary_search(target2, input_a2), expected2)
self.assertEqual(binary_search(target3, input_a3), expected3)


코드를 보시면 보는 것 과 같이 가운데 값을 체크해서 원하는 값보다 크면 오른 쪽을 버리고,


작으면 왼쪽을 버리고 길이를 반으로 줄인 배열을 다시 같은 방법으로 줄여가면서 원하는 값을 찾습니다.


코드는 github으로도 확인하실수 있습니다.


https://github.com/baidoosik/ProblemSolving/blob/master/Search/binary_search.py



감사합니다.








이진 트리 구현

이진 트리는 부모 노드가 left, right 자식 노드를 가지는 나무를 거꾸로 한 모양의 자료구조

* search, add, delete가 O(logn)의 성능으로 좋은 성능을 가진 자료구조이기 때문에 여러가지 프로그램을 만드는데 자주 쓰입니다.

* preorder_traverse 는 말 그대로 root 노드를 먼저 순회하기 때문에 preorder traverse이고, root노드 -> left 노드 -> right 노드 순으로 순회하고, 전송시에 이진 트리의 모형을 그대로 유지하기 때문에 전송시에 사용됩니다.

* inorder_traverse 도 마찬가지로 root 노드를 중간에 순회해서 inorder traverse입니다. left 노드 -> root 노드 -> right 노드 순으로 순회하고, 오름차순으로 정렬된 값이 나오게 됩니다.

* postorder_traverse 는 root 노드를 가장 나중에 순회하는 방법으로 left 노드 -> right 노드 -> root 노드 순으로 순회합니다.





구현 코드 및 테스트 코드

import unittest


class Node:
def __init__(self, value):
self.value = value
self.right = None
self.left = None


class BinaryTree:
def __init__(self):
self.head = Node(None)

# test purpose lists
self.preorder_list = []
self.inorder_list = []
self.postorder_list = []

def add(self, value):
if self.head.value is None:
self.head.value = value
else:
self._add(self.head, value)

def _add(self, cur, value):
if cur.value < value:
if cur.right is None:
cur.right = Node(value)
else:
self._add(cur.right, value)
else:
if cur.left is None:
cur.left = Node(value)
else:
self._add(cur.left, value)

def search(self, value):
if self.head.value is None:
return False
else:
return self._search(self.head, value)

def _search(self, cur, value):
if cur.value == value:
return True
else:
if cur.value < value:
if cur.right is None:
return False
else:
return self._search(cur.right, value)
else:
if cur.left is None:
return False
else:
return self._search(cur.left, value)

def remove(self, value):
if self.head.value is None:
return print("there is no value in this binary tree")
else:
if self.head.value == value:
if self.head.left is None and self.head.right is None:
self.head = Node(None)
elif self.head.left is None and self.head.right is not None:
self.head = self.head.right
elif self.head.left is not None and self.head.right is None:
self.head = self.head.left
else:
self.head.value = self._most_left_val_from_right_node(self.head.right).value
self._remove_item(self.head, self.head.right)
return True
else:
if self.head.value < value:
self._remove(self.head, self.head.right, value)
else:
self._remove(self.head, self.head.left, value)

def _remove(self, prev, cur, value):
if cur is None:
return print("not found value")

if cur.value < value:
self._remove(cur, cur.right, value)
elif cur.value > value:
self._remove(cur, cur.left, value)
else:
if cur.left is None and cur.right is None:
if prev.left.value == value:
prev.left = None
else:
prev.right = None
elif cur.left is None and cur.right is not None:
if prev.left.value == value:
prev.left = cur.right
else:
prev.right = cur.right
elif cur.left is not None and cur.right is None:
if prev.left.value == value:
prev.left = cur.left
else:
prev.right = cur.left
else:
cur.value = self._most_left_val_from_right_node(cur.right).value
self._remove_item(cur, cur.right)
return True

def _most_left_val_from_right_node(self, cur):
if cur.left is not None:
return self._most_left_val_from_right_node(cur.left)
else:
return cur

def _remove_item(self, prev, cur):
if cur.left is None:
prev.right = cur.right
else:
while cur.left is not None:
prev = cur
cur = cur.left
if cur.right is not None:
prev.left = cur.right
else:
prev.left = None

def preorder_traverse(self):
if self.head is not None:
self._preorder_traverse(self.head)

def _preorder_traverse(self, cur):
self.preorder_list.append(cur.value)
if cur.left is not None:
self._preorder_traverse(cur.left)
if cur.right is not None:
self._preorder_traverse(cur.right)

def inorder_traverse(self):
if self.head is not None:
self._inorder_traverse(self.head)

def _inorder_traverse(self, cur):
if cur.left is not None:
self._inorder_traverse(cur.left)

self.inorder_list.append(cur.value)

if cur.right is not None:
self._inorder_traverse(cur.right)

def postorder_traverse(self):
if self.head is not None:
self._postorder_traverse(self.head)

def _postorder_traverse(self, cur):
if cur.left is not None:
self._postorder_traverse(cur.left)
if cur.right is not None:
self._postorder_traverse(cur.right)
self.postorder_list.append(cur.value)


class BinaryTreeTest(unittest.TestCase):
def test(self):
bt = BinaryTree()
bt.add(6)
bt.add(3)
bt.add(4)
bt.add(1)
bt.add(7)
print("pre order")
bt.preorder_traverse()
self.assertEqual(bt.preorder_list, [6, 3, 1, 4, 7])

print("in order")
bt.inorder_traverse()
self.assertEqual(bt.inorder_list, [1, 3, 4, 6, 7])

print("post order")
bt.postorder_traverse()
self.assertEqual(bt.postorder_list, [1, 4, 3, 7, 6])

print("bt root remove")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(50)
bt_root_remove_test.add(70)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [70, 50])

print("bt root remove2")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(50)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [50])

print("bt root remove3")
bt_root_remove_test = BinaryTree()
bt_root_remove_test.add(60)
bt_root_remove_test.add(70)
bt_root_remove_test.remove(60)
bt_root_remove_test.preorder_traverse()
self.assertEqual(bt_root_remove_test.preorder_list, [70])

print("bt left remove 1")
bt_left_remove_test_1 = BinaryTree()
bt_left_remove_test_1.add(60)
bt_left_remove_test_1.add(50)
bt_left_remove_test_1.add(70)
bt_left_remove_test_1.remove(50)
bt_left_remove_test_1.preorder_traverse()
self.assertEqual(bt_left_remove_test_1.preorder_list, [60, 70])

print("bt left remove 2")
bt_left_remove_test_2_left = BinaryTree()
bt_left_remove_test_2_left.add(60)
bt_left_remove_test_2_left.add(50)
bt_left_remove_test_2_left.add(70)
bt_left_remove_test_2_left.add(40)
bt_left_remove_test_2_left.remove(50)
bt_left_remove_test_2_left.preorder_traverse()
self.assertEqual(bt_left_remove_test_2_left.preorder_list, [60, 40, 70])

print("bt right remove 2")
bt_left_remove_test_2_right = BinaryTree()
bt_left_remove_test_2_right.add(60)
bt_left_remove_test_2_right.add(50)
bt_left_remove_test_2_right.add(70)
bt_left_remove_test_2_right.add(55)
bt_left_remove_test_2_right.remove(50)
bt_left_remove_test_2_right.preorder_traverse()
self.assertEqual(bt_left_remove_test_2_right.preorder_list, [60, 55, 70])

print("bt right remove 1")
bt_right_remove_test_1 = BinaryTree()
bt_right_remove_test_1.add(60)
bt_right_remove_test_1.add(50)
bt_right_remove_test_1.add(70)
bt_right_remove_test_1.remove(70)
bt_right_remove_test_1.preorder_traverse()
self.assertEqual(bt_right_remove_test_1.preorder_list, [60, 50])

print("bt right remove 2")
bt_right_remove_test_2_left = BinaryTree()
bt_right_remove_test_2_left.add(60)
bt_right_remove_test_2_left.add(50)
bt_right_remove_test_2_left.add(70)
bt_right_remove_test_2_left.add(65)
bt_right_remove_test_2_left.remove(70)
bt_right_remove_test_2_left.preorder_traverse()
self.assertEqual(bt_right_remove_test_2_left.preorder_list, [60, 50, 65])

print("bt right remove 3")
bt_right_remove_test_1 = BinaryTree()
bt_right_remove_test_1.add(60)
bt_right_remove_test_1.add(78)
bt_right_remove_test_1.add(70)
bt_right_remove_test_1.add(50)
bt_right_remove_test_1.add(55)
bt_right_remove_test_1.add(65)
bt_right_remove_test_1.add(67)
bt_right_remove_test_1.add(69)
bt_right_remove_test_1.add(79)
bt_right_remove_test_1.remove(70)
bt_right_remove_test_1.preorder_traverse()
self.assertEqual(bt_right_remove_test_1.preorder_list, [60, 50, 55, 78, 65, 67, 69, 79])

print("bt right remove 2")
bt_right_remove_test_2_right = BinaryTree()
bt_right_remove_test_2_right.add(60)
bt_right_remove_test_2_right.add(50)
bt_right_remove_test_2_right.add(70)
bt_right_remove_test_2_right.add(75)
bt_right_remove_test_2_right.remove(70)
bt_right_remove_test_2_right.preorder_traverse()
self.assertEqual(bt_right_remove_test_2_right.preorder_list, [60, 50, 75])

print("bt left remove 3")
bt_left_remove_test_3 = BinaryTree()
bt_left_remove_test_3.add(60)
bt_left_remove_test_3.add(50)
bt_left_remove_test_3.add(70)
bt_left_remove_test_3.add(40)
bt_left_remove_test_3.add(55)
bt_left_remove_test_3.add(52)
bt_left_remove_test_3.remove(50)
bt_left_remove_test_3.preorder_traverse()
self.assertEqual(bt_left_remove_test_3.preorder_list, [60, 52, 40, 55, 70])

print("BST search test")
bt_search_test = BinaryTree()
bt_search_test.add(60)
bt_search_test.add(50)
bt_search_test.add(70)
bt_search_test.add(40)
bt_search_test.add(55)
bt_search_test.add(52)
self.assertTrue(bt_search_test.search(60))
self.assertTrue(bt_search_test.search(50))
self.assertTrue(bt_search_test.search(70))
self.assertTrue(bt_search_test.search(40))
self.assertTrue(bt_search_test.search(55))
self.assertTrue(bt_search_test.search(52))
self.assertFalse(bt_search_test.search(61))
self.assertFalse(bt_search_test.search(81))


코드가 조금 많이 긴 편입니다. 도움이 되셨으면 좋겠습니다.

github에서도 쉽게 코드를 확인하실 수 있습니다.


https://github.com/baidoosik/ProblemSolving/blob/master/DataStructure/BinaryTree.py


감사합니다.









어떤 문자열을 URL 화 하고 싶을 때가 있습니다.


예를 들면 공백을 기준으로 URL 화 하거나 어떤 기호를 기준으로 URL 화 할 수 있습니다.



'hello world' -> 'hello/world'



이를 파이썬 코드로 만들어 보겠습니다.



해결 방법 : 순회하면서 특정 문자일 때 / 로 변환하여 저장.




매일 간단한 문제라도 푸려고 하고 있습니다.


감사합니다.








오랜만에 다시 알고리즘 문제


기본 문제부터 파이썬 알고리즘 문자열 중복 체크하기.



문자열 중복을 체크하는 방법으로 


1) 중복된 element를 제거해주는 자료구조인 set 을 이용해서 해결.


2) 단순하게 for 문으로 element 들을 순회 하면서 중복을 체크.



1) 자료구조 set 을 이용.





2) for 문을 순회





이제 한 동안은 알고리즘과 자료구조를 공부를 열심히 해보려고 합니다.


감사합니다.






리스트에서 자주 출현한 숫자 구하기

주사위를 굴려서 나온 숫자를 리스트에 순서대로 적은 값과 k를 입력 받았을 때, 리스트에 자주 출현한 k개의 숫자를 리턴하는 코드를 작성.

  • ex) 주사위 던진 결과 [3,2,3,1,2,5,3,6,2,4] 이고 k가 2이면 2가 세번 3이 세번으로 자주출현한  [2,3]을 출력.
  • 예를 들어, 주사위 던진 결과가 [1,1,1,2,2,2,3,3,4,4] 이고 k 가 3이면 [1,2,3] or [1,2,4] 를 출력


접근 1)

dictionary + sorting 으로 구현

sorting O(nlogn) 의 시간 복잡도를 필요. 코드는 간결한 편.



-> lambda 함수를 이용해서 정렬 후에 k개의 key 를 리턴



접근 2)

dictionary + while 문으로 구현

큰 k값을 구할 때 리스트를 순회하면서 k개의 값을 뽑으므로 O(kn) 의 시간 복잡도를 필요로 함. 성능이 더 좋음.

하지만, 코드는 위에 코드보다 조금 긴편.



오늘도 알고리즘 문제를 파이썬으로 해결해봤습니다. 


감사합니다.






먼저 QUEUE 란?


- 선입 선출의 First In , First Out (FIFO) 의 특성을 갖는 자료구조.


- 조금 더 풀어서 말하면 먼저 들어온 데이터가 먼저 나간다.



가장 대표 적인 예시는 패스트 푸드 점의 주문 관리 시스템 먼저 받은 주문부터 먼저 음식을 줘야한다. (안주면 큰 일 나지요..)




Queue 를 구현하는 방법으로는 직선구조의 Queue나 원형 구조의 Queue, Linked Queue 가 있다.



단순한 직선 구조의 Queue 는 데이터가 10000 개 있다고 했을 때 enqueue, dequeue 과정에서 모든 데이터가 한 칸씩 움직여야 함으로 비효율


적이다.


이를 해결하기 위해서 Linked Queue 나 Circular Queue 를 이용하는데 Linked Queue를 이용하면 First Node 와 Last Node로 맨 앞의 데이터


와 뒤를 가리키게 하고, enqueue , dequeue시 이를 변경해주기만 하면 됨으로 효율적이다.


그래서 파이썬으로 



기본 적으로 파이썬의 자료구조인 리스트를 이용해서 구현해보고, 아쉬워서 Linked Queue도 구현해봤다.


코드는 기본적으로 리뷰가 안되었기 때문에 많이 가다듬은 코드는 아니기 때문에 참고하는데 주의를 ...



파이썬 built-in list로 구현한 QUEUE




두 번째로 파이썬으로 구현한 Linked QUEUE






다시 한 번 말하자면 혼자 생각하면서 바로 쓴 것이어서 문제가 발생할 수도 있으니 ㅎㅎ 


그냥 느낌만 보시길 추천..!






나는 어떤 과정으로 Problem Solving을 하는지 , 


즉 문제를 해결해나가는지 정리 정리해보면서 그 과정에 맞추어 triple sum이라는 문제를 풀어봤다.


triple sum은 어떤 배열이 주어졌을 때 배열의 3가지 원소로 0을 만드는 경우의 수를 찾는 문제이다.



나는 어떤 과정으로 문제를 푸는지 생각해봤다.




1. 코딩을 하기 전


문제 파악 : 어떤 문제인지 이해


문제 쪼개기: 해결해야하는 문제를 나눈다.


나눈 문제를 어떤 로직이나 알고리즘 모듈로 해결할지 고민한다.



2. 코딩


위에 생각한 내용을 바탕으로 해당 기능이 수행되도록 구현한다.



3. 코딩 후


테스트 / 디버깅 : 테스트 및 버그 수정


시간/공간 복잡도 계산 및 개선점 찾아보기





다시 위 과정 순서대로 triple sum이라는 문제를 보면



코딩 전


문제는 명확하기 때문에 바로 이해할 수 있고, 


task를 두 개로 나눈다.



1) 리스트에서 가능한 3가지 수를 뽑아서 모든 리스트로 만든다. 


2) 그리고 그 리스트에서 합이 0인지 확인하고, 합이 0인 배열을 return 한다.



이제 코딩


def pick_triple_number(alist):

    result_list = []

    for i in range(len(alist)):

        for j in range(i+1,len(alist)):

            for k in range(j+1, len(alist)):

                result_list.append([alist[i], alist[j], alist[k]])

    return result_list



def triple_sum(alist):

    result = pick_triple_number(alist)

    final = []

    [final.append(i) for i in result if sum(i)==0]

    return final



테스트




시간/공간 복잡도, 개선점 찾기


생각해보면 전체 리스트를 저장할 필요가 없다. 애초에 조건에 해당하는 리스트만 저장하면 메모리 및 실행 속도를 줄일 수 있다.




 


Triple sum 이라는 문제를 풀면서 내가 문제를 풀 때 어떤 과정으로 문제를 해결하는지 정리해봤다....


부족한게 많겠지만 이 또한 과정이겠지...!







캐글을 통해 입문하는 사람들은 보통 타이타닉의 예제를 통해 입문하는 경우가 많습니다.

최근에 몇 가지 강의에서도 타이타닉 예제를 사용하고 있는 것으로 알고 있습니다.


타이타닉 예제를 통해서 데이터 사이언티스트(Data scientist) 들이 어떤 일을 하는지 

데이터 분석에서 어떤 일을 하는지 조금 이해할 수 있게 됐습니다.


간단하게 flow를 정리해봤습니다.


1. 정확하게 문제를 정의해야 합니다.

어떤 데이터로 어떤 문제를 해결하고 싶은지 정의 해야 합니다.

타이타닉 문제를 예로 들자면, 타이타닉에 탑승했던 승객들의 정보를 통해 미래에 어떤 배를 타는 승객들이 배가 침몰했을 때 죽을지 죽지 않을지 

예측합니다.


2. 데이터를 processing하여 정리해서 모으는 과정이 필요합니다.

데이터를 분석 할 수 있는 형태의 데이터 모아서 데이터를 분석할 수 있는 형태로 만드는 과정입니다. 

아래의 데이터는 kaggle에서 주어지는 데이터입니다.



보통은 이렇게 데이터가 주어지는 경우가 없기 때문에

분석하려는 데이터를 DB에서 자신이 필요한 필드의 데이터들을 csv로 추출하는 과정이나 크롤링을 통해서 데이터를 정리하는 과정이 필요합니다.

다음에 기회가 된다면 이 과정을 자세히 포스팅하도록 하겠습니다.



3. 데이터를 보면서 어떤 데이터들이 중요한 데이터인지 확인하는 과정이 필요합니다. 

이 과정에서 데이터의 시각화를 이용해서 데이터에서 깨달음을 얻는 경우가 많습니다.


마찬가지로 타이타닉 사건의 예로 들자면, 표를 구매한 가격에 따라 생존/죽음 에 영향을 주는지 승객들의 탑승 장소에 따라서 생존/죽음과 관련이 있는지 파악하는 과정이 필요합니다.

이 과정이 필요한 이유는 이 과정을 통해 각 Feature engineering 이 이뤄집니다.  Feature engineering은 벡터 연산을 위해서 연산이 가능한 형태로 데이터를 변경하는 과정입니다.


4. Feature engineering , 데이터 벡터화

컴퓨터가 데이터를 통해 학습은 벡터 연산으로 이뤄지기 때문에  3번 과정에서 분석했던 데이터를 알맞게 숫자로 변경해주어야 합니다.


위의 그림처럼 모든 필드의 데이터들을 숫자로 만듭니다. (우린 컴퓨터에게 학습을 시켜야 하니깐요.)



5. Modeling

쉽게 설명하면 지금까지 만든 데이터를 통해 어떤 방법의 알고리즘을 통해 학습 시켰을 때 가장 학습이 잘 되서 결과값을 잘 예측하는지 파악해서 해당 알고리즘으로 학습 시키는 과정입니다.

KNN , Decision Tree, SVM, naive bayes 등 알고리즘을 통해 학습을 시켜가면서 어떤 알고리즘을 통해 학습을 시켰을 때 결과값이 좋은지 찾을 수 있습니다. 



6. Testing

이제 만든 학습 시킨 데이터를 통해 실제 값을 넣어서 데이터의 결과 값을 얼마나 잘 예측 했는지 테스트 합니다.


간단하게 데이터 분석의 과정을 kaggle의 타이타닉 예제를 예로 들어 설명하면서 적어봤습니다.


참고 자료: 

https://www.youtube.com/user/TheEasyoung 허민석 님의 유튜브 강의를 참고하였습니다.


감사합니다.








기본 정렬 중에 네 번째는 quick sort 입니다.




quick sort 의 핵심 개념은 pivot 입니다.


리스트의 element 중에서 아무 element 나 뽑았을 때 그 값은 정렬 했을 때 가장자리 보다는 중간정도 위치에 들어갈 확률이 더 높습니다.


그 수를 중심으로 양쪽으로 나누어서 정렬하는 것이 quick sort인데 여기서 랜덤으로 뽑은 수를 pivot으로 사용합니다. 


(여기서는 구현의 편의를 위해서 가장 마지막 element 를 pivot으로 사용했고, 그렇기 때문에 정렬되어 있는 경우는 시간 복잡도가 n**2 이 될 수 있습니다.)



리스트의 길이가 1이 될 때 까지 pivot을 기준으로 양쪽으로 나누고 O(log n), pivot이 자리를 잡는데 O(n)의 시간이 필요합니다.


리스트를 나눠가면서 정렬을 하기 때문에 평균 시간복잡도가 O(nlogn) 이 됩니다.



시간복잡도: O(nlogn)  최악의 경우 O(n^2)(정렬되어 있는 경우)


공간복잡도: O(1) 


을 필요로 합니다.



또, 구현하는데 recursive 재귀 개념이 들어가 있어서 인터뷰에서도 자주 출제되는 알고리즘이기 때문에 


에디터 환경 뿐만아니라 구글 닥스나 손으로 코딩을 작성해보시는 것 을 추천드립니다.



코드는 다음과 같습니다.





혹시, 잘못된 부분이 있으면 언제든지 댓글 남겨주세요!


감사합니다.


  1. 일산헤이터 2017.11.28 08:26 신고

    요즘 게시글이 뜸하십니다.



파이썬에서 list는 가장 많이 사용하는 자료구조 중에 하나라고 할 수 있습니다.


tuple은 list에 비해 빈번하게 이용되지는 않지만 tuple 만의 장점을 가지고 있는 자료구조입니다.


이 두 자료구조에 대해 자세히 알아보도록 하겠습니다.






자료구조를 공부해야하는 이유는 궁극적으로 좋은 성능을 내는 코드를 작성하기 위해서 입니다.



현재 개발하고 있는 프로그램에 맞는 자료구조를 선택함으로써 성능을 높일 수 있습니다. 빈번한 데이터 변환은 프로그램의 성능을 떨어뜨리기 때문입니다.


사실 성능을 고려한 프로그래밍에서는 어떤 데이터를 어떻게 다룰를 고민하고, 그 상황에서 빠르게 작동하는 자료구조를 선택하는 일이 큰 비중을 차지합니다.


그래서 어떤 상황에서 리스트를 사용하고, 튜플을 사용하는지 어떻게 동작하는지 공부해야합니다.





리스트와 튜플은 배열이라고 하는 자료구조의 한 종류입니다.



C 언어에서 처럼 배열은 


어떤 정해진 순서에 따라서 데이터를 나열해 둔 것입니다. 그렇기 때문에 순서를 알고 있으면 O(1) 시간 복잡도로 데이터에 접근할 수 있습니다.


리스트와 튜플은 배열의 한 종류로 리스트는 동적으로 생성되는 배열이고, 튜플은 정적으로 생성되는 배열입니다.



배열이 할당되면 시스템 메모리에 블록이 할당되고, 정해진 순서에 따라 각 블록에 데이터를 가리키는 주소를 저장합니다.


+ 리스트의 경우는 메모리에 리스트의 길이까지도 저장합니다.



위에서 언급한 것 처럼 기본적으로 순서를 알고 있다고 가정하면 시간 복잡도는 O(1)이기 때문에 배열의 길이에 상관없이 접근하는 시간은 거의 비슷합니다.




하지만, 위 상황과 다르게 순서를 모른다면 원하는 데이터를 찾기 위해 선형적으로 배열에 접근해야 하기 때문에


최악의 경우(찾지 못하는 경우 마지막 인덱스 까지 탐색) O(n)의 시간복잡도를 갖습니다.




그렇다면 더 효율적인 탐색을 위해서는 어떻게 해야 할까요?


그 동안 많이 들어왔던 이진 탐색을 이용하면 시간복잡도가 O(logn) 이지만 이는 정렬된 리스트에서만 이용할 수 있습니다.



정렬이 되어 있다는 전제하에 O(logn)의 시간복잡도로 데이터의 인덱스를 얻을 수 있습니다.


리스트를 정렬하는 방법으로는


1) quick sort

2) merge sort

3) bubble sort 

4) inser sort 


등 이있고,


list 의 멤버함수인 list.sort 의 경우 Tim Sort를 이용합니다. (tim sort는 insert sort와 merge sort를 조합해서 사용합니다.)



+ 정렬이 되어 있다는 전제하에 bisect 모듈을 이용하면 이진 탐색 기법으로 인덱스를 찾고, 또 정렬을 유지하면서 데이터를 삽입할 수 있습니다.


이는 나중에 기회가 된다면 따로 공부하여 포스팅 할 예정입니다.




이제 list와 tuple 을 본격적으로 비교해 보도록 하겠습니다.



먼저 대다수 분들이 알듯이


list 는 동적 배열이기 때문에 배열을 추가하거나 변경할 수 있습니다.


이에 반해, tuple은 정적 배열로 배열을 추가하거나 변경 할 수 없습니다.



여기 까지만 생각하면 생각없이 list를 사용하는 것이 좋습니다. 배열을 바꿀 경우가 아주 빈번하게 있기 때문이죠.


하지만 list가 가지고 있는 단점과 tuple이 가지고 있는 장점이 있습니다.



1)  list는 동적 배열이기 때문에 배열의 늘어날 것을 대비해서 미리 여분의 메모리 공간을 할당해 놓습니다.


    그렇기 때문에 10개의 항목인 리스트를 생성해도 16개 항목만큼 메모리를 사용하게 됩니다. 


    배열의 개수가 10,000개 라고 하면 160,000개의 항목만큼의 메모리를 사용하게 됩니다.


    하지만, tuple은 딱 100,000개의 항목만큼의 메모리를 사용합니다.



2) tuple은 크기가 20이하인 경우 파이썬의 캐싱 메모리에 저장되기 때문에 GC(Garbage collector)에 의해서 메모리가 회수되지 않기 때문에


    재사용하는 경우 빠르게 생성이 가능하다.


 


- 참조자료


*고성능파이썬 

http://www.yes24.com/searchcorner/Search?keywordAd=&keyword=&domain=ALL&qdomain=%C0%FC%C3%BC&Wcode=001_005&query=%B0%ED%BC%BA%B4%C9+%C6%C4%C0%CC%BD%E3


* askdjango 강의자료 ( http://nomade.kr )



잘못된 내용이 있거나 부족한 내용이 있으면


 댓글로 알려주시면 감사하겠습니다.



감사합니다.










+ Recent posts