이진 탐색은 정렬된 배열에서 원하는 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


감사합니다.









안녕하세요.


요즘 Cracking the coding interview 라는 책을 통해서 공부하고 있습니다.


연결 리스트 문제 중에  비정렬 연결 리스트에서 중복 문자열을 제거하는 코드 문제를 파이썬으로 해결해보려고 합니다.


+ 임시 버퍼를 사용하는 방법과 임시 버퍼를 사용하지 않는 방법 두가지 모두 코드를 작성하여 봤습니다.



일단 값과 다음 노드를 가르키는 객체인 Node 객체를 만듭니다.




복사 가능한 코드


class Node:

    def __init__(self, value, next_node):

        self.value = value

        self.next = next_node



그리고 LinkedList 를 구현합니다.


여기서 설명은 원소를 추가, 삭제 ,조회 등을 구현하는 것은 설명하지 않고 중복 문자열을 제거하는 코드에 대해서만 설명을 할 것 입니다.



첫번째 함수는 임시 버퍼인 dictonary를 사용해서 O(n)의 시간 복잡도로 문제를 해결했습니다.


순회하면서  dictonary에 value를 넣고 중복되는 값이 있는지 체크하면서 중복된 경우 중복된 노드를 삭제하고 전 노드와 중복 노드가 가리키는 노드를 연결해서 문제를 해결했습니다.


두 번째 문제인 임시버퍼를 사용하지 않는 경우는 하나의 node 변수를 추가해서 시간 복잡도 O(n**2)의 시간복잡도로 하나의 값을 가지고 있으면서 


순회하면서 중복된 값을 찾아서 제거하는 방법을 사용했습니다.



전체 LinkedList 코드입니다.


class LinkedList:

    def __init__(self):

        self.head = Node(None, None)

        self.cur = None

        

    def add(self, value):

        self.cur = self.head

        while self.cur.next is not None:

            self.cur = self.cur.next

        self.cur.next = Node(value, None)

    

    def _remove(self, cur):

        cur.next = cur.next.next

    

    def remove(self, value):

        self.cur = self.head

        while self.cur.next is not None:

            if self.cur.next.value == value:

                self._remove(self.cur)

                return value

            self.cur = self.cur.next

        raise Exception("value not found")

        

    def show_all(self):

        self.cur = self.head.next

        

        while self.cur is not None:

            print(self.cur.value)

            self.cur = self.cur.next

    

    def remove_duplicate_word(self):

        self.cur = self.head

        temporary_buffer = {}

        while self.cur.next is not None:

            if temporary_buffer.get(self.cur.next.value) is not None:

                self._remove(self.cur)

            else:

                temporary_buffer[self.cur.next.value] = 0

                self.cur = self.cur.next

    

    # 임시 버퍼 사용 x

    def remove_duplicate_word_without_buffer(self):

        runner = self.head.next

        self.cur = self.head

        

        while runner is not None:

            self.cur = runner

            while self.cur.next is not None:

                if runner.value == self.cur.next.value:

                    self._remove(self.cur)

                else:

                    self.cur = self.cur.next

            runner = runner.next


해당 책의 문제들을 파이썬으로 해결한 코드를 Github에 올릴 예정입니다.


repository가 만들어지면 공유 드리도록 하겠습니다.








서버 개발을 할 때 데이터베이스와 관련된 프로그래밍을 할 때 가장 중요하고 신경써야 하는 부분 중에 하나는 데이터베이스 트랜잭션 처리입니다.


특히, 마이크로 서비스 아키텍쳐로 이뤄진 서비스의 트랜잭션 처리는 정말 쉽지 않은 일입니다.



예를 들어 쿠폰 관련 Domain을 처리하는 서비스 A 가 있고, 결제 관련 Domain을 처리하는 서비스 B 가 나누어져 있다고 생각하면 쿠폰을 사용해서 결제를 하다가 중간에 실패를 하였는데 쿠폰이 사용되어 버리면 아주 큰 문제가 발생합니다. 여기서 각 서비스별로 DB connection이 각각 이뤄지기 때문에 하나의 DB connection으로 작업할 때 보다 복잡도가 올라갑니다. 일단 이런 복잡한 경우는 뒤로 미뤄보고, 데이터 베이스 트랜잭션이 무엇이고 이와 관련된 성질인 ACID에 대해서 살펴보려고 합니다. 



트랜잭션이란?


하나의 논리적 작업 단위를 구성하는 일련의 연산들의 집합을 트랜잭션입니다. 즉, 작업을 묶어놓은 단위입니다.



트랜잭션의 예로 위에 예보다는 대부분 은행에 입출금을 하는 것을 예시로 많이 사용합니다.



예를 들어, 우리은행의 A의돈을  =>국민은행 계좌를 사용하는 B에게 돈을 입금했을 때 A의 돈은 먼저 우리은행 DB에 저장이 되고(출금 기록을 저장), 그 후에 우리은행 DB에서 국민은행 DB에 B의 계좌로 이동할 것 이다. 

즉, 1) 우리은행 DB 작업  2) 국민은행의 DB 작업이 있다. 만약에 우리은행에서 국민은행으로 데이터를 전송 중 실패한다면 다시 A의 통장에 돈을 넣어줘야 한다. 

우리은행에서 A의 계좌에서는 돈이 없어졌는데 국민은행 B의 계좌로 입금된 기록이 없다면 현재 은행 시스템은 존재하지 않을것입니다.( 모두 직접 돈을 가져다 주겠죠.)

(위의 예시 과정은 제가 추측한 것이므로 실제 구현과는 다를 가능성이 큽니다.)


트랜잭션은 주로 ACID 성질이라고 하는 다음의 네가지 성질로 설명됩니다. 

이 중 하나라도 해당되지 않으면 트랜잭션이 잘 처리되었다고 할 수 없습니다.


Atomicity(원자성)

이체 과정 중에 트랜잭션이 실패하게 되어 예금이 사라지는 경우가 발생해서는 안 되기 때문에 DBMS는 완료되지 않은 트랜잭션의 중간 상태를 데이터베이스에 반영해서는 안 된다. 즉, 트랜잭션의 모든 연산들이 정상적으로 수행 완료되거나 아니면 전혀 어떠한 연산도 수행되지 않은 상태를 보장해야 한다. atomicity는 쉽게 'all or nothing' 특성으로 설명된다. 즉, 가장 작은 작업 단위이기 때문에 분리할 수 없기 때문에 수행이 되었거나 안되었거나 둘 중 하나라는 성질을 가지고 있습니다.

Consistency(일관성)

고립된 트랜잭션의 수행이 데이터베이스의 일관성을 보존해야 한다. 즉, 성공적으로 수행된 트랜잭션은 정당한 데이터들만을 데이터베이스에 반영해야 한다. 트랜잭션의 수행을 데이터베이스 상태 간의 전이(transition)로 봤을 때, 트랜잭션 수행 전후의 데이터베이스 상태는 각각 일관성이 보장되는 서로 다른 상태가 된다. 트랜잭션 수행이 보존해야 할 일관성은 기본 키, 외래 키 제약과 같은 명시적인 무결성 제약 조건들뿐만 아니라, 자금 이체 예에서 두 계좌 잔고의 합은 이체 전후가 같아야 한다는 사항과 같은 비명시적인 일관성 조건들도 있다.

Isolation(독립성)

여러 트랜잭션이 동시에 수행되더라도 각각의 트랜잭션은 다른 트랜잭션의 수행에 영향을 받지 않고 독립적으로 수행되어야 한다. 즉, 한 트랜잭션의 중간 결과가 다른 트랜잭션에게는 숨겨져야 한다는 의미인데, 이러한 isolation 성질이 보장되지 않으면 트랜잭션이 원래 상태로 되돌아갈 수 없게 된다. Isolation 성질을 보장할 수 있는 가장 쉬운 방법은 모든 트랜잭션을 순차적으로 수행하는 것이다. 하지만 병렬적 수행의 장점을 얻기 위해서 DBMS는 병렬적으로 수행하면서도 일렬(serial) 수행과 같은 결과를 보장할 수 있는 방식을 제공하고 있다. 각각의 트랜잭션은 독립적으로 묶이기 때문에 A,B,C 라는 트랜잭션이 있다면 각각이 독립적이어서 A가 처리가 된것이나 중간에 실패하여 처리가 되지 않은것과 B,C 는 독릭적이라는 의미입니다.

Durability(지속성)

트랜잭션이 성공적으로 완료되어 커밋되고 나면, 해당 트랜잭션에 의한 모든 변경은 향후에 어떤 소프트웨어나 하드웨어 장애가 발생되더라도 보존되어야 한다. 지속성이 보존 되지 않는다면 원자성 또한 파괴됩니다. 일주일 뒤에 확인했더니 출금한 기록은 사라지고, 입금한 기록만 있다면 아주 끔찍할 것 입니다.



데이터 베이스에서는 이러한 트랜잭션을 지원하기 위하여 UNDO, REDO 같은 기능을 구현하였고, 또 이는 DBMS가 어떻게 구현해야에 따라서 차이가 있습니다.


이와 관련된 자료 중에 아주 좋은 글이 있어서 추천드립니다. 혹시, DBMS 가 어떻게 트랜잭션을 관리하는지 궁금하신분이 있다면 읽어보시면 좋을 것 같습니다.


https://d2.naver.com/helloworld/407507



- 참고한 글


나무위키


https://d2.naver.com/helloworld/407507




혹시, 관련해서 피드백이 있다면 언제든지 댓글로 남겨주시면 감사하겠습니다.


감사합니다.








'프로그래밍 > DB(DataBase)' 카테고리의 다른 글

데이터베이스 트랜잭션과 ACID  (0) 2018.12.28






오늘 풀어본 문제는 프로그래머스에 있는 완주하지 못한 선수라는 문제입니다.


링크: https://programmers.co.kr/learn/courses/30/lessons/42576



이 문제에 대해 간단히 설명을 하자면


마라톤에 참여한 선수들의 이름 리스트가 있고, 그 중 완주한 선수들의 이름 리스트가 있습니다.


완주하지못한 선수는 단 1명 뿐입니다. 그러므로 참여선수리스트와 완주한 선수들의 리스트의 길이 차는 1입니다.



참가자 중에는 동명이인이 있습니다.



먼저, 해당 문제에서는 어떤 자료구조를 선택해서 문제를 해결하느냐가 핵심일 것 같습니다.


생각해본 문제 풀이 방법은


1) 정렬을 해서 비교하면 다른 원소일 때 해당 값을 리턴 하는 방법. 정렬하는데 O(nlogn)의 시간이 소요되는데 리스트가 2개이고 또 마지막에 순회할 때 O(n) 의 시간복잡도가 필요하기 때문에 좋은 방법이라고 생각하지 않았습니다.


2) 해쉬 자료구조를 사용해서 이름을 키로 사용한 후에 해당 키에 접근에서 빼는 방식으로 하면 O(n) 의 시간복잡도를 2번 필요로 하기 때문에 위에 방법보다 더 좋은 방법이라고 생각했습니다.




제가 작성한 코드입니다.


먼저 완주한 선수 리스트를 dictonary에 넣어준 후에


참가자리스트에 있는 선수들을 나온 순서로 체크해서 이미 해당 값의 key의 value가 0이 되거나 value이 없는경우 해당 key 를 리턴해주도록 작성하였습니다.




복사 가능한 코드


def solution(participant: list , completion:list ) -> str:

    dictionary = {}

    for v in completion:

        if dictionary.get(v):

            dictionary[v] +=1

        else:

            dictionary[v] = 1

    

    for v in participant:

        if dictionary.get(v):

            if dictionary == 0:

                return v

            else:

                dictionary[v] -=1

        else:

            return v

        

    return answer



다른 분이 작성한 코드 중에서 파이썬이 collections 패키지의 Counter 를 사용해서 문제를 해결한 분이 있어서 소개드리려고 합니다.


collections 패키지는 파이썬에서 제공하는 강력한 컨테이너 데이터 타입입니다.


그 중에서 Counter는 hashable 객체의 카운팅을 위한 Dict의 서브클래스입니다. 


즉, 위에서 제가 dictonary를 사용해서 해당 키의 빈도를 counting한 경우에 사용하면 딱인 데이터 타입입니다.




이런식으로 리스트를 이용해서 생성하면 다음과 같이 dictionary가 만들어집니다.



Counter 를 사용한 코드입니다.




코드가 보다 간결해진 것을 확인할 수 있습니다.



문제를 풀다 보면 다양한 방법으로 푼 다른 분들의 

코드를 볼 수 있어서 많이 도움이 됩니다.


혹시, 잘못된 부분이 있거나 궁금하신점이 있으면 댓글 남겨주세요.


감사합니다.







알고리즘 문제를 풀다보면 10진수에서 2진수로 2진수에서 10진수로 변경을 필요로 하는 문제가 많이 있습니다.


이러한 문제가 나오는 이유는 컴퓨터가 애초에 2진수 체계로 만들어져 있기 때문에 컴퓨터에 대한 이해에 있어서 진법을 이해하는 것이 중요하기 때문이라고 생각합니다.



실제로 컴퓨터에서 곱하기 연산이나 나누기 연산을 한 자리 씩 shift 시키면서 하는 것을 보면


흡사 십진수를 이진수로 변환하는 프로그래밍과 유사하다는 느낌도 받았습니다.(저의 개인적인 생각입니다...!)




십진수를 이진수로 바꾸는 방법은 십진수를 2로 나눈 몫, 나머지 를 이용해서 각 자리를 정해줍니다.


19 이라는 수가 있다면


맨처음 2로 나누면 몫 9이고 나머지는 1 이기 때문에 최하위 bit 1이되고


다시 9를 2로 나누면 몫 4 이고 나머지는 1이기 때문에 그 다음 자리의 bit 1이 됩니다.


계속에서 끝까지 살펴보면 4를 2로 나누면 몫2 나머지 0 그 다음 자리의 bit 0


그 다음 2를 2로 나누면 몫 1 나머지 0 이니깐 그 다음 자리의 bit 0


이제 1을 2로 나누면 몫 0 나머지 1 이니깐 최상위 비트는 1 그리고 몫이 0이므로 루프를 종료합니다.


그래서 10001(2) 라고 변경이 됩니다.




위의 과정을 코드로 구현 하면 10진수에서 2진수로 변경하는 함수가 됩니다.


그리고 저위에 나누는 수를 2 대신 3으로 하면 3진수로 변경하는 함수가 됩니다.



제가 구현한 코드를 보면 다음과 같습니다.





테스트코드에서 사용한 bin 함수는 파이썬에서 10진수를 2진수로 변환하는 builtin 함수입니다. 


bin(20) 을 출력하면 '0b10100' 문자열로 앞에 0b를 출력하기 때문에 이부분을 제외하기 위해서 slicing을 해서 int로 형변환을 하였습니다.




복사 가능한 코드


def change_binary(n : int) -> int:

    result, idx = 0,0

    while (n >=1):

        remainder =n % 2

        n = n // 2

        result += (10**idx)* remainder

        idx +=1

    return result



위에서 이야기 한 것처럼 이번에는 3진수로 변환하는 함수를 그대로 구현보겠습니다.





3진수로 변환하는 함수는 단순히 나누는 수를 2->3으로 변경한 것입니다. 


그렇기 때문에 2진수로 바꾸는 방법을 이해하신 분은 4진수 5진수 등도 쉽게 변경하는 함수를 만들 수 있을 것 입니다.






조언이나 피드백은 언제나 감사합니다.


감사합니다.








해당 문제는 프로그래머스에서 제공하는 문제에 대한 개인적인 풀이입니다.


더 좋은 방법이 있거나 의견이 있으신분은 댓글 주시면 자유롭게 의견교환 하실 수 있습니다.




이번에 풀어본 문제는 주식가격이라는 문제입니다.


초단위당 주식 가격이 리스트로 매개변수로 주어질 때 각 시간에 주식가격이 유지된 기간이 몇 초인지 return 하는 함수를 작성하는 문제입니다.


문제에서 제한 사항이 주어졌지만, 혹시 주어지지 않았다면 면접시에는 수의 범위나 리스트의 대략적인 크기에 대해서 물어보시면 더욱 좋을 것 같습니다.



여기서 저는 가격이 유지된다는 의미를 가격이 아예 같다라는 의미로 받아들였는데 예시를 보니 하락 하지 않은 상태를 의미하는 것 이었습니다.





해당 문제에 대한 제 코드입니다.


먼저, 가격이 유지되었는지 확인하는 부분은 비교해보는 방법 뿐이고, 필요한 연산을 위해서 첫번째 for 루프에서 이미 계산한 index를 제외하고 시작하는 index라는 표현을 하기위해서 start라고 변수명을 지어서 사용했습니다. 


두 번째 for loop에서 


1) 유지되어 있는 기간을 찾으면 더 이상 비교해볼 필요가 없으모로 break 를 사용해서 그 당시에 index에서 start를 빼줘서 유지되는 기간을 반환할 리스트에 더해줬습니다.


2) 계속 유지된 경우라면 마지막 for loop에서 i-start가 유지된 기간이 되므로 아래와 같이 작성하면 코드가 조금 더 간결해질 것 이라고 생각했습니다.





복사 가능한 코드


def solution(prices: list) -> list:

    answer = []

    for start in range(0, len(prices)):

        pivot = prices[start]

        for i in range(start, len(prices)):

            if prices[start] > prices[i]:

                break

        answer.append(i-start)

    return answer




읽어 주셔서 감사합니다. 


조언이나 피드백은 언제나 환영입니다.


  1. ㅎㅈ 2019.01.07 15:20 신고

    글 올려주셔서 고마운데 여러군데 봐도 설명이 이해가 안 되는 제 머리....ㅠ pivot 변수는 등장 이후 안 쓰인거 같은데 왜 필요한건가요...ㅠ



다시 알고리즘 공부를 시작해보려고 쉬운 문제부터 다시 천천히 풀어보고 있습니다.



최근에 읽고 있는 책에서 기술 문제를 푸는 과정이나 접근방법에 대해서도 배우고 있어서 간단하게 기술 문제를 푸는 과정에 대해서 간단히 소개하고 문제를 풀어보도록 하겠습니다.



Cracking The Code Interview에서 소개한 기술 문제를 푸는 다섯 단계


1. 면접관에게 문제의 모호한 부분에 대해 묻는다.


2. 알고리즘을 설계한다.


3. 가상 코드 


4. 코드


5. 테스트




문제:


문자열의 입력을 받아서 해당 문자열에 들어 있는 소괄호가 올바른지 판단하는 함수를 만드시오.



알고리즘에서 체크해야하는 부분


- 괄호는 열리면 닫혀야 한다. (즉, 열리면 닫혀야함)


- 괄호는 열리는게 먼저다. 즉, 항상 열린 후에 닫혀야 한다.



코드:


def parenthesis_validator(a: str) -> bool:

    total: int = 0

    for w in a:

        if w == "(":

            total +=1

        elif w==")":

            total -=1

            if total <0:

                return False

    return True if total==0 else False



테스트:


class ValidatorTest(unittest.TestCase):

    testcase1 = "((abcd))"

    testcase2 = "(((abcd))"

    testcase3 = "((abcd)))"

    testcase4=""

    

    def test(self):

        self.assertEqual(parenthesis_validator(self.testcase1), True)

        self.assertEqual(parenthesis_validator(self.testcase2), False)

        self.assertEqual(parenthesis_validator(self.testcase3), False)

        self.assertEqual(parenthesis_validator(self.testcase4), True)


test = ValidatorTest()


test.test()



오랜만에 쉬운 문제풀이를 하나 포스팅했습니다. 


이제부터 꾸준히 알고리즘 문제를 풀고 공유하도록 하겠습니다.


감사합니다.







C# 에서 

어떤 변수를 기존에 만든 객체로 할당하게 되면 해당 변수는 그냥 기존에 만들어진 객체를 참조하기 때문에 기존에 있던 객체와 같은 객체가 된다.


예시를 보면 쉽게 이해할 수 있다.


Ex)

public class Car
{
    public string Name;

    public string Color;
}

Car car1 = new Car{Name=“supercar”, Color=“red”};

Car car2 = car1;

car1.Name = “my supercar”;

라고 car1의 Name 을 변경했을 때

Console.WriteLine(car2.Name);

을 출력하면 my supercar 가 출력된다.

즉, car1과 car2는 같은 메모리 어드레스를 참조하는 변수인 것이다.


그렇다면 car1과 같은 value를 같는 새로운 객체를 만들고 싶다면 어떻게 해야할까?

Copy 와 관련된 메서드인 닷넷 프레임워크에서 제공해주는 Object 클래스의 MemberwiseClone 메서드를 이용해서 ShallowCopy() 메서드와 DeepCopy() 메서드를 만들어서 사용하면된다.

두 메서드 의 차이는 클래스가 참조형 멤버를 가지고 있을 때 참조형 멤버 객체를 새로 생성하는냐 생성하지 않느냐에 차이다.


일단 참조형 멤버를 가진 클래스를 만들어보자.

public class CarBrand
{
    public string Name;

    public string PhoneNum;
}

public class Car
{
    public string Name;

    public string Color;

    public CarBrand Brand; 

    public Car ShallowCopy()
    {
        return (Car)this.MemberwiseClone();
    {

    public Car DeepCopy()
    {
        Car other = (Car) this.MemberwiseClone();
        other.Brand = new CarBrand(Brand);
        other.Name = String.Copy(Name);
        other.Color = String.Copy(Color);
        return other;
    }
}

Car 라는 객체는 CarBrand라는 객체를 멤버로가지고 있다.


이제 우리가 만든 ShallowCopy 와 DeepCopy()를 예제 코드를 사용해서 비교해보자.

EX)
CarBrand carBrand = new CarBrand{Name=“Audi”, PhoneNum=“01012341234”};
Car car1 = new Car {Name=“a4”, Color=“white”, Brand=carBrand};

Car car2 = car1.ShallowCopy();
car2.Name = “sonata”;
car2.Brand = new CarBrand{Name=“Hyundai”, PhoneNum=“01012341234”};

로 하고 값을 확인해보면

car1의 Brand로 현대로 바뀐 것을 확인할 수 있다. Name 은 여전히 a4이다.

즉, Brand 객체를 같이 참조하고 있는 것을 확인 할 수 있다.



포함하고 있는 참조 객체까지 새롭게 만들고 싶다면 위에서 만든 DeepCopy() 함수를 이용하면 된다.

EX)
CarBrand carBrand = new CarBrand{Name=“Audi”, PhoneNum=“01012341234”};
Car car1 = new Car {Name=“a4”, Color=“white”, Brand=carBrand};

Car car2 = car1.ShallowCopy();
car2.Name = “sonata”;
car2.Brand = new CarBrand{Name=“Hyundai”, PhoneNum=“01012341234”};

로 하고 값을 확인해보면

car1의 Brand는 여전히 audi이고 car2의 Brand만 현대로 바뀐 것을 확인할 수 있다. 

즉, car2 에서 Brand 객체를 새롭게 만들어서 사용한것 을 확인할 수 있다.



위에서 살펴본 것 처럼 기본적으로 만들어진 객체를 이용해서 변수에 할당하게 되면 새로운 객체가 아니라 기존에 객체를 참조하게 되므로 shallowcopy나 deepcopy 같은 함수를 만들어서 사용해야 한다. 

shallowcopy와 deepcopy의 차이는 가지고 있는 멤버 중에 참조객체를 
새로 만드느냐 아니면 기존의 것을 같이 참조하냐의 차이다.







C# 과 ASP.NET CORE를 공부하면서 가장 힘든 점 중 하나는 턱없는 한글 문서입니다.

그래서 비동기 함수에서 ConfigureAwait(false)를 왜 사용하는지에 대한 좋은 글이 있어서 번역하게 됐습니다.

저자의 동의를 얻어서 번역한 자료입니다!



다른 분들에게 도움이 되었으면 좋겠네요 :)



원본:

저자: Juan


본문:

.NET4.5  부터 async/await 를 도입하면서 asynchronous code를 작성하기가 많이 쉬워졌다.

Async/Await 키워드들은 synchronous 코드 와 비슷하고 컴파일러가 asynchrous 프로그래밍에서 처리하기 가장 어려운 부분을 처리해주면서코드 가독성과 프로그래머의 생산성을 향상시켰다.

Async 코드를 만들기가 얼마나 쉬운지 알아보기 위해 컨텐츠를 string으로 반환하는 curl 코드를 example로 만들어보자.

public async Task<string> DoCurlAsync()
{
    using(var httpClient = new HttpClient())
    using(var httpresponse = await httpclient.GetAsync(“https://www.bynder.com”))
    {
        return await httpResponse.Content.ReadAsStringAsync();
    }
}


우리는 bynder의 content를 가져오는 동안 다른 쓰레드를 호출하는 것을 막지 않는 비동기 호출을 했다.

이론적으로(상상 속에서) 사람들은 항상 우리가 만든 DoCurlAsync 함수를 아래와 같이 사용할 것 이다.

var bynderContnets = await DoCurlAsync();


하지만, 프로그래밍 세계는 이상과 거리가 멀다. 몇몇 사람들은 다음과 같이 사용할 수 있다.

var bynderContents = DoCurlAsync().Result

이렇게 코드를 작성하면 동기 방식으로 코드가 수행되기 때문에 curl 함수가 종료될 때 까지 다른 쓰레드를 호출 하는것을 막는다. 만약 콘솔 어플리케이션을 실행시키는 중이라면, 우리의 코드는 대부분 예상대로 실행될 것이다.

그러나 아래와같이, 만약 UI Application에서 수행이 되어진다면, 예를 들어서 button을 클릭했을 때 수행이 되는거라면

public void OnButtonClicked(object sender, RouteEventArgs e)
{
    var bynderContents = DoCurlAsync().Result;
}


이 어플리케이션은 동작하지 않을 것이고 deadlock 상태가 되어 버립니다. 물론, 우리가 만든 함수를 사용하는 사람들은 우리의 함수가 application을 응답하지 못하게 만들었다고 불평할 것 입니다.

이와 같은 상황의 문제를 해결하기 위해서 우리는 함수를 아래와 같이 다시 작성합니다.

public async Task<string> DoCurlAsync()
{
    using(var httpClient = new HttpClient())
    using(var httpresponse = await httpclient.GetAsync(“https://www.bynder.com”).ConfigureAwait(false))
    {
        return await httpResponse.Content.ReadAsStringAsync().ConfigureAwait(false);
    }


사실 , 첫번째의 비동기 구문에 ConfigureAwait(false) 를 붙이는 것으로 이 문제는 충분히 해결할 수 있습니다.

public async Task<string> DoCurlAsync()
{
    using(var httpClient = new HttpClient())
    using(var httpresponse = await httpclient.GetAsync(“https://www.bynder.com”).ConfigureAwait(false))
    {
        return await httpResponse.Content.ReadAsStringAsync();
    }

결론적으로, 항상 ConfigureAwait(false)를 사용하는 것은 우리가 원치 않은 상황을 막기위한 good practice 입니다.




이제, 우리는 UI 어플리케이션(대부분의 콘솔 어플리케이션이 아닌)에서 dead lock이 발생하는지 분석하고 왜 ConfigureAwait(false)과 이 문제를 해결하는지 분석해볼 것 입니다.


먼저, 우리는 UI 어플리케이션 어떻게 동작하는지 이해하는 작업이 필요합니다.

  • UI 응답을 위한 UI 스레드라는 하나의 스레드가 있습니다. UI는 오직 이 쓰레드를 호출해야만 업데이트 할 수 있습니다. 그래서 만약 에 쓰레드 호출이 막혀 있다면 어플리케이션은 응답하지 않은 것으로 보입니다.
  • UI 쓰레드는 수행할 notification과 action을 받을 message queue를 가지고 있습니다. Win32에서는 아래와 같이 표현할 수 있습니다.

    • while( (bRet = GetMessage( &msg, NULL, 0, 0 )) != 0)
      {
          // No errors are handled, for simplicity purposes.
         TranslateMessage(&msg);
         DispatchMessage(&msg);
      }

  • UI 쓰레드는 기본적으로 SynchronizationContext를 가지고 있습니다.
    • SynchronizationContext
      다양한 동기화 모델에서 동기화 컨텍스트를 전파하는 기본 기능을 제공해주는 class

만약에 SynchronizationContext가 있다면 (UI 스레드에서 코드가 실행된다면) await 이후의 코드들은 원래의 thread context에서 수행될 것 라고 기본적으로 예상할 수 있습니다.

만약, 아래 예제와 같이 우리가 UI 컴포넌트를 UI 스레드가 아닌 다른 스레드에서 수정하려고 한다면 System.InvalidOperationException이 발생할 것입니다.


public void OnButtonClicked(object sender, RouteEventArgs e)
{
    var bynderContents = await DoCurlAsync();
    myTextBlock.text = bynderContents;
}


다시 우리의 예제 코드를 돌아와보면 , 우리의 async DoCurlAsync 호출은 개념적으로 아래 코드와 같다.

var currentContext = SynchronizationContext.Current;
var httpResponseTask = httpClient.GetAsync("https://www.bynder.com");
httpResponseTask.ContinueWith(delegate
{
    if (currentContext == null)
    {
        return await httpResonse.Content.ReadAsStringAsync();
    }   
    else
    {
        currentContext.Post(delegate {
            await httpResonse.Content.ReadAsStringAsync();
        }, null);
     }
}, TaskScheduler.Current);


NOTE: 이 snippet은 await 구문을 사용했을 때 발생하는 것과 비슷한 버젼의 코드다. 이것은 resources들은 사용하고 closing하는 부분은 다루지 않았다.

Post 요청은 UI 스레드 메시지 펌프에 처리 될 메시지들을 보내고, 그래서 DoCurlAsync를 끝내기 위해서는 UI Thread가  await httpResonse.Content.ReadAsStringAsync();를 실행하는 것이 필수적이다.

그러나 , 아래와 같은 시나리오에서는

public void OnButtonClicked(object sender, RoutedEventArgs e)
{
    var bynderContents = DoCurlAsync().Result;
}

UI 스레드가 막혀 있으므로 instruction을 수행할 수없다. DoCurlAsync는 결코 끝나지 않으므로 dead lock상태에 빠진다. ConfigureAwait(false)는 await 후의 코드를 호출자 컨텍스트에서 수행할 필요가 없게 해준다. 그러므로 어떠한 deadlock도 피할 수 있다. 



이 글은 왜 비동기 함수를 호출 할때 ConfigureAwait(fasle)를 호출하는 것이 

Best Practice 인지 설명해줍니다.


그 이유가 궁금하셨던 분들이 계셨다면 도움이 되면 좋겠습니다.


감사합니다.







+ Recent posts