이진 탐색은 정렬된 배열에서 원하는 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) 의 시간 복잡도를 필요로 함. 성능이 더 좋음.

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



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


감사합니다.







안녕하세요.



오늘은 HEAP TREE 구조에 대해서 알아보겠습니다.


MAX Heap Tree 는 부모 노드가 자식 노드보다 크기만 크면 되는 구조를 가진 자료형입니다. 


(반대로 Minium heap tree 도 있습니다.)





부모노드가 자식노드 보다 큰 특성을 가지고 있으니 가지고 있으니 


당연히 ROOT 노드는 가장 큰 수가 됩니다.



그렇기 때문에  가장 큰 수와 가장 작은 수를 O(1) 의 성능으로 가져올 수 있다는 장점이 있습니다.



그렇기 때문에 최대 값, 최소 값을 위해 정렬이 필요한 경우 사용하면 O(N) 의 성능으로 heap 구조를 만들고 


최대, 최소 값을 o(1)의 성능으로 가져올 수 있습니다.



다음에는 heap sort에 대해서도 구현해보겠습니다.


감사합니다.



나는 어떤 과정으로 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 이라는 문제를 풀면서 내가 문제를 풀 때 어떤 과정으로 문제를 해결하는지 정리해봤다....


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




기본 정렬 중에 네 번째는 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 신고

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

https://programmers.co.kr/ 의 


모든 파이썬 알고리즘 문제를 푸는 것을 목표로 삼고,


문제를 풀고 있습니다.


오늘 드디어 Python level 3까지 다 풀었습니다~!!


문제들이 조금씩 어려워지네요.



오늘 푼 문제는 파이썬으로 N개의 수의 최소 공배수 구하기 입니다.



먼저 다음과 같이 나눠서 해결 방법을 생각해 보았습니다.


1) 두 수의 최소공배수


2) 두 수의 최대공약수


3) 여러 가지 수의 최대공약수 -> 2개 씩 묶어서 최소공배수를 구하자 .


->즉,  n개의 원소를 가진 list에서 최소공배수를 n 번 구하지 말고 


logn /log2 번 만 연산할 수 있도록 merge 개념을 생각했습니다.



그냥 순회하는 경우 성능 측면에서 느리기 때문에 다음과 같이 두 개씩 짝을 지어서 최소공배수를 구하고,


다시 짝을 지어 최소공배수를 구하는 방법을 사용했습니다.



언제든지 조언은 감사히 듣겠습니다.


감사합니다.








  1. 이갈이 2017.10.25 21:50 신고

    꾸준히하시는 모습에 응원 보냅니다 :D

  2. taewon7 2018.03.07 18:53 신고

    와 님 정말 대단하시네요!
    어떻게 저걸... 저는 엄두도 못 냅니다.
    글들 잘 보고 배워갑니다!

    • jordan_bae jordan17 2018.06.05 14:54 신고

      칭찬 감사합니다!! ㅠㅠㅠ 저도 아직 실력이 많이 부족한데 같이 열심히 해서 실력이 많이 늘었으면 좋겠네요~

https://programmers.co.kr/ 의 


모든 파이썬 알고리즘 문제를 푸는 것을 목표로 삼고,


문제를 풀고 있습니다.


드디어 Python level 2까지 다 풀었습니다.





파이썬으로 행렬의 곱셈 결과 구하기.





언제든지 조언은 감사히 듣겠습니다.


감사합니다.



+ Recent posts