굿

solution for Two City Scheduling

Problem)

Solution)

문제에서 각 cost간의 차이 값을 구했을 때, 차이 값이 작으면 A 도시로 차이값이 크면 B 도시로 가는 것이 비용상 더 효율적이다.

즉 문제에서 제공한 예제에 적용해서 4명의 각 비용의 차이 값을 계산하면 [-10, -170, 350, 10]이 되고 이를 오름차순으로 정렬하면 [-170, -10, 10, 350]이 된다. 여기서 우리는 정렬된 리스트를 기준으로 좌측에서 A로 우측에서 B로 한명씩 보내게되면 최소 비용으로 모든 사람들을 A, B 도시로 반반씩 보낼 수 있게 된다.

특별한 알고리즘에 대한 지식보다는 문제에 대한 이해와 해석 능력이 필요한 문제인 것 같다.

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        N = len(costs)
        diff = [c[0] - c[1] for c in costs]
        indices =  sorted(range(0,N), key=lambda k:diff[k])
        result = 0
        
        for i in range(int(N/2)):
            result += costs[indices[i]][0]
            result += costs[indices[N-i-1]][1]
        return result

좀 더 파이썬 다운 코드...

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key = lambda x: x[0]-x[1])
        return sum(i[0] for i in costs[:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:])

solution for Invert Binary Tree

Problem)

Invert a binary tree.

Example)

Solution)

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        else:
            return None

Reference)

Recursion (Recursive Function)

이번 포스트에서는 정말 간단하게 python에 pickle을 활용하여 데이터를 저장하고, 저장된 데이터를 불러오는 코드를 알아보겠습니다.

pickle은 파이썬의 모든 객체(object)에 대해서 있는 그대로 저장할 수 있는 모듈입니다. pickle은 객체를 바이너리 파일에 저장하기 때문에 아래와 같이 파일을 읽을 때 'wb', 'rb' 처럼 바이너리 형식을 사용해야 합니다.

pickle.dump / pickle.load

import pickle

temp_dict = {'name': 'S', 'id': 1}

# 데이터 저장
with open('filename.pkl', 'wb') as f:
	pickle.dump(temp_dict, f, protocol=pickle.HIGHEST_PROTOCOL)
    
# 데이터 로드
with open('filename.pkl', 'rb') as f:
	data = pickle.load(f)

위 코드를 활용하여 간단하게 dict 형태의 데이터를 'filename.pkl' 파일로 저장하고 불러올 수 있습니다.

여기서 한 주의할 점은 protocol 부분인데요, python 버전에 따라서 지원하는 protocol이 다릅니다.

따라서 본인이 사용하는 python 버전에 유의하여 파라미터를 사용해야 합니다. (python 2.x 버전에서는 protocol이 0~2까지만 지원된다고 합니다.)

추가적으로 pandas DataFrame도 아래의 코드를 활용해서 쉽게 데이터를 관리할 수 있습니다.

df.to_pickle / pd.read_pickle

import pickle
import pandas as pd

temp = pd.DataFrame({'a':[1], 'b':[2]})

# 데이터 저장
temp.to_pickle('filename.pkl')

# 데이터 로드
data = pd.read_pickle('filename.pkl')

프로그램의 실행 속도는 프로그래밍의 아주 중요한 요소입니다. Python에서 프로세스 기반의 병렬 처리를 통해 실행 속도를 향상 시킬 수 있는 방법에 대해서 알아보겠습니다.

Python에서는 병렬 처리를 위해 multiprocessing 패키지를 제공합니다. multiprocessing에는 대표적으로 Pool과 Process가 있지만 이번 글에서는 Process에 대해서만 다루도록 하겠습니다.

multiprocessing.process

Process는 미리 정의한 함수를 하나의 프로세스에 할당하여 실행합니다. 이때, 각 프로세스마다 적당한 인자값을 할당하여 실행할 수 있습니다.

[example code]

import os
from multiprocessing import Process

def add_one(num):
    p_id = os.getpid()
    print('({} + 1) done by ---> process {}'.format(num, p_id))
    num += 1
	
if __name__ == '__main__':
    nums = range(1, 10)
    procs = []

    for idx, num in enumerate(nums):
        proc = Process(target=add_one, args=(num,))
        procs.append(proc)
        proc.start()

    for proc in procs:
        proc.join()

[output]

(1 + 1) done by --> process 24696
(9 + 1) done by --> process 3624
(3 + 1) done by --> process 16288
(6 + 1) done by --> process 23852
(5 + 1) done by --> process 26036
(7 + 1) done by --> process 10276
(2 + 1) done by --> process 18812
(8 + 1) done by --> process 18928
(4 + 1) done by --> process 704

example code를 보시면 하나의 프로세스를 Process(target=add_one, args=(num,))으로 생성합니다. 여기서 target에는 함수를 args에는 인자를 할당하는 것을 확인할 수 있습니다.

multiprocessing.Manager()

Process를 쓰면서 변수를 공유해야 할 수도 있습니다. 이때 사용하는 것이 Manager()입니다. Manager()를 통해서 List 또는 Dict 등의 변수를 공유할 수 있습니다.

[example code]

import multiprocessing

manager = multiprocessing.Manager()
final_list = manager.list()

input_list_one = ['one', 'two', 'three', 'four', 'five']
input_list_two = ['six', 'seven', 'eight', 'nine', 'ten']

def worker(data):
    for item in data:
        final_list.append(item)

process1 = multiprocessing.Process(target=worker, args=[input_list_one])
process2 = multiprocessing.Process(target=worker, args=[input_list_two])

process1.start()
process2.start()

process1.join()
process2.join()

print(final_list)

[output]

['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten']

 위의 예제를 보시면 Manager()로 생성한 list인 final_list를 2개의 프로세서가 공유하여 각 리스트를 합친 결과를 확인할 수 있습니다. list뿐만 아니라 dict, array, value 등 다양한 변수를 선언하여 공유할 수 있습니다.

Reference

[python] Multiprocessing (Pool, Process, Queue)

Sharing Global Variables in Python Using Multiprocessing

프로그래밍에 자주 사용되는 대표적인 자료구조에는 "그래프"가 있습니다. 

오늘 포스팅에서는 그래프를 탐색하는 알고리즘 2가지 DFS와 BFS에 대해서 알아보도록 하겠습니다.

그래프는 정점과 간선으로 이루어져 있는데 간선을 통해서 모든 정점을 방문하는 것을 그래프를 탐색한다고 합니다.

위에서 언급했듯이 그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 있습니다. 각각의 알고리즘에 대해서 자세히 알아보도록 하겠습니다.

위 그림을 보시면 두 알고리즘의 차이에 대해서 직관적으로 이해하실 수 있습니다. 각 알고리즘의 명칭에서도 볼 수 있듯이 깊이(자식)를 우선으로 탐색하느냐 아니면 너비(형제)를 우선으로 탐색하느냐의 차이가 있습니다.

1. 깊이 우선 탐색

깊이 우선 탐색 (Depth First Search)은 트리 혹은 그래프에서 노드의 자식들을 우선으로 탐색하는, 즉 최대한 깊숙히 탐색한 후 다시 돌아가 다른 루트를 탐색하는 방법입니다. 여기서 한 노드에서 제일 마지막 자식까지 탐색을 마치고 돌아오는 과정을 백트리킹(Backtracking)이라고 합니다. 구현에는 주로 스택 자료구조를 사용합니다.

 
# Python implementation of DFS using stack
def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

#======================================#

# DFS using recursion
class Node:
    def __init__(self, data):
        self,data = data
        self.child = []
        self.visited = False

def dfs(A):
    if A.visited == True:
        return
    
    print(A.data)
    a.visited = True
    for child in node.childs:
        dfs(child)

2. 너비 우선 탐색

너비 우선 탐색 (Breadth First Search)은 트리 혹은 그래프에서 노드의 인접한 모든 정점들을 우선으로 탐색하는 방법입니다. 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장하는 방법입니다. 구현에는 주로 큐 자료구조를 사용합니다.

 
# Python implementation of BFS using queue
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

정말 쉽게 설명해주시는 유튜브 영상도 첨부하겠습니다. 포스팅 내용이 너무 빈약하기 때문에 아래 영상을 참조하시면 더욱 쉽고 더욱 깊은 내용을 공부할 수 있습니다.

출처

• http://ejklike.github.io/2018/01/05/bfs-and-dfs.html
• http://mishadoff.com/blog/dfs-on-binary-tree-array/
• https://m.blog.naver.com/PostView.nhn?blogId=complusblog&logNo=221155195082&proxyReferer=https%3A%2F%2Fwww.google.com%2F