Algorithms site

29 Mar 2018 | Algorithms

Summary :

논리적으로 생각하고, 알고리즘 풀이를 한번씩 해봐야 감을 잃지 않을 것 같아서 어떤 사이트가 있는지 정리했다.

Algorithms site:

GeeksforGeeks

https://www.geeksforgeeks.org/

백준 온라인 저지

https://www.acmicpc.net

HackerRank

https://www.hackerrank.com/

InterviewBit

https://www.interviewbit.com/

오일러 프로젝트(Project Euler)

http://euler.synap.co.kr/

알고 스팟

https://algospot.com/

더블릿(Dovelet)

http://59.23.150.58/index.php

코딜리티(Codility)

https://codility.com/

코딩도장

http://codingdojang.com/

UVA, live archive

https://uva.onlinejudge.org/
https://icpcarchive.ecs.baylor.edu/

CodeForces, TopCoder

https://www.codeforces.com
https://www.topcoder.com

References :

http://ledgku.tistory.com/40
http://lifeignite.tistory.com/8

Algorithms

20 Feb 2018 | Algorithms Data_Structure

Summary :

포스팅 — 알고리즘 어떤 문제를 풀기 위한 절차나 방법 어떤 문제가 있을 때 주어진 ‘입력’ 정보를 원하는 ‘출력(답)’ 정보로 만드는 일련의 과정을 구체적이고 명료하게 적은 것.

ex) 절댓값 구하기 문제 : 어떤 숫자의 절댓값 구하기 입력 : 절댓값을 구할 실수 a 출력 : a의 절댓값

풀이 : 주어진 실수 a가 양수 혹은 0이면 a값이 그대로 절댓값이 된다. a가 음수이면 a에 마이너스(-)를 붙이면 절댓값이 된다.

1. a가 0보다 크거나 같은지 확인. 만약 그렇다면 a를 결과로 return
2. a가 0보다 작으면 -a를 결과로 돌려준다.

이 두문장이 ‘실수의 절댓값 구하는 알고리즘 ‘ 이다. 컴퓨터 프로그램을 만들기 위한 알고리즘은 계산 과정을 최대한 구체적이고 명료하게 적어야 한다.

어떤 문제를 푸는 방법이 꼭 한가지만 있는 것은 아니다. a를 제곱한 다음 그 값의 제곱근을 취하는 방법으로도 절댓값을 구할 수 있다. 여러 알고리즘 중에 상황에 맞는 적당한 알고리즘을 골라 쓰려면 어떤 알고리즘이 어떤 특징을 지니고 있으며 얼마나 계산이 빠르고 편한지 등을 알아야 한다.

‘알고리즘 분석’ - 알고리즘의 성능이나 특징을 분석하는 것

프로그램을 작성하기 전에 알고리즘을 ‘사람의 언어’로 최대한 자세히 적어두면, 알고리즘을 프로그램으로 옮기는 과정이 더 쉬워진다.

ex)

1. a를 제곱하여 변수 b에 저장한다.
2. b의 제곱근을 구해 결과로 돌려준다.

import math # 수학 모듈 사용
def abs_sign(a):
    if a>=0:
        return a
    else:
        return -a

def abs_square(a):
    b = a*a 
    return math.sqrt(b) # 수학 모듈의 제곱근 함수

print(abs_sign(5))
print(abs_sign(-3))
print()
print(abs_square(5))
print(abs_square(-3))

5.0 , 3.0으로 출력된 이유는 math.sqrt()가 소수점이 붙은 값을 돌려주기 때문

무인상점을 꿈꾸는 amazon go

24 Jan 2018 | interests amazon

Summary :

2018.01.22 Amazon GO 일반인에게 공개. 미국 워싱턴주 시애틀에 위치한 아마존 고는 ‘ 컴퓨터 비전’ ‘딥러닝’ 등 인공지능 기술과 첨단 센서 기술을 활용해 오프라인 상점을 혁신한 O2O(Online to Offline) 서비스의 대표적인 사례

고객은 원하는 물건을 고른 후 바로 나가면 된다. 구매한 물건은 아마존 계정을 통해 사용자에게 자동으로 청구된다.

아마존 고의 콘셉트는 ‘Just Walk Out Shopping ‘ 이라고 표현 ‘ 물건을 집어들고 그냥 나가라’ 물건을 구매하기 위해 기다릴 필요없이 원하는 물건을 구매해서 바로 나갈 수 있는 상점을 만드려는 아마존의 야심을 함축한 문장이다.

이용방법 아마존 고 앱을 내려받아 회원으로 가입. 앱을 설치한 후 결제용 신용카드 정보 입력, 개인식별용 QR코드가 생성.

아마존 고에서 판매하는 물건을 에코백에 담거나 손에 들면 아마존 고 앱의 결제 서랍에 자동으로 해당 물건이 담긴다. 만야게 물건을 꺼내 다시 원래 자리에 두면 아마존 고 앱 결제 서랍에 담겨있던 물건도 자동으로 사라진다.

그리고 그냥 나오면 10분 정도가 지나면 아마존 고 앱을 통해 물건의 결제가 완료되었다고 메시지가 날아온다.

무인상점의 원리와 한계 아마존 고는 인공지능 기술과 센서 기술을 활용해 무인상점을 구현 천장에 부착된 수백대의 카메라 QR코드를 찍고 아마존 고에 입장하면 카메라들이 고객의 움직임을 추적하기 시작하낟. 고객이 누구인지, 집어든 물건이 무엇인지 등을 파악한 후 고객이 물건을 들고 나가면 아마존 고 계정을 통해 자동으로 비용을 청구

아직 완성은 아니다. 고객이 어떤 물건을 얼마나 들고 나갔는지 인공지능의 눈만으로 확실히 파악하기 힘들다는 문제 이를 위해서는 물건의 선반에 무게를 감지하는 센서를 부착해 인공지능이 정확한 판단을 내릴 수 있도록 돕고 있다. 사용자가 작은 물품을 구매할 경우 몇 가지를 놓치고 이를 누락시키는 문제 발견되었다.

아마존 고의 서비스 일정이 1년 이상 미뤄진 것은 21명째 인원부터는 사용자 구분 및 동선 추적이 불가능했기 때문이다. 현재는 51평에 달하는 아마존 고 매장내의 모든 인원을 추적할 수 있게 되었다.

계산원은 무엇을 해야 하나? 아마존 고는 완벽한 무인상점이 아니다. 내부에는 시스템 관리를 위한 많은 직원이 상주 부족한 물건을 채우고, 고객의 claim 대응, 다양한 즉석 요리를 만들어 고객에게 제공 최선의 서비스를 제공하기 위해 같은 크기의 다른 상점보다 더 많은 직원이 일하고 있다.

아마존 고의 목표는 무인상점이 아니다. 단순히 인건비를 아끼기 위해 무인상점을 만들고자 했다면 자판기만 모아 놓은 무인상점 시스템이 훨씬 효율적일 것이다.

진정한 목표는 ‘끊김없는 쇼핑 경험(Seamless Shopping Experience)’이다. 고객에게 더 나은 쇼핑 경험을 향상시키기 위해 힘쓰고 있다. 인건비를 아끼는 것이 아니라 고객 경험을 향상시키는 전문가가 되도록 역할 변경을 추진하고 있다는 것이 아마존의 설명이다.

아마존 고는 아마존닷컴, 아마존웹서비스와는 별개의 서비스이다.

아마도 첫 interests tag 포스팅이 될것 같다. 관심있는 뉴스나 사람들의 SNS글을 요약하고, 내 생각을 덧붙이면서 어떤 세상이 펼쳐질지 상상하려고 interests 포스팅을 시작한다. 상업적인 용도는 절대 없으며, 출처를 반드시 밝히고 문제가 될 경우 삭제한다.

---

내생각

먼저 아마존 고는 대단하다. 아직 딥러닝 초보자인 내 입장에서 보면 정말 대단한 일이라 느껴진다. 이미지 처리하는 것도 힘들어하는 나랑 아마존이랑 비유하는 것조차 민망하지만, 그래도 어떤 기술이 어떻게 활용되고 있는지를 추측을 해보면 정말 대단한 시스템이라 생각한다. 아마존의 고객의 더 나은 경험을 위한다는 말은 표면적인 이유일 것 같다. 다양한 노동자들/인권을 외치는 사람들의 목소리를 막기위함? 진짜 목표는 무인상점이 맞을 것 같다는 생각이 든다. 왜냐하면 이제 센서와 딥러닝으로 사물인식을 처리한 것인데, 만약 음성인식이나 다른 기술들과 합쳐지면 더 완벽한 상점이 될것이기 때문이다. 궁금증이 생긴것은 물품을 채우는 부분인데, 이 부분은 어떻게 해야할지 아이디어를 내봐야 알것같다. 무인을 위한 상점인데 사람이 계속 상주하고 넣을수도 없으니 말이다. 마지막으로 아직 갈길이 먼 것같다. 만약 모든 기술의 집약, 협업으로 99.9% 무인상점 시스템을 개발했다고쳐도 무인상점을 차리려다가 웬만한 회사보다 비싼 시설비가 들것이다. 맨시티가 최고의 구단이 되었듯이, 결국 기술도 돈이 뒷받침 돼야 한다고 생각한다.

References :

글 / IT 동아 강일용(zero@itdonga.com)
인터비즈 임현석 정리(inter-biz@naver.com)
https://blog.naver.com/businessinsight/221191297591

Machine-learning 알고리즘 몇가지 둘러보기

06 Jan 2018 | Algorithms Machine-learning ML

Python으로 간단한 주소록 만들어보기

06 Jan 2018 | Project

이번 글에서는 그래프(Graph)라는 자료구조의 정의와 관련 용어들에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 먼저 밝힙니다. 그럼 시작하겠습니다.

graph

그래프란 일련의 노드(node, vertex, 정점, 꼭지점) 집합 $V$와 엣지(edge, 간선, 변) 집합 $E$로 구성된 자료구조의 일종입니다. 일반적으로 노드엔 데이터, 엣지엔 노드와 노드 사이의 관계 정보가 포함되어 있습니다. 이를 그림으로 나타내면 다음과 같습니다.

sparse/dense graph

sparse graph란 하단 좌측 그림처럼 노드의 수보다 엣지 수가 적은 그래프를 가리킵니다. 반대로 dense graph란 하단 우측 그림처럼 노드 수보다 엣지 수가 큰 그래프입니다.

incident/adjacent

임의의 두 노드가 하나의 엣지로 연결돼 있을 경우, 이 노드들은 서로 인접(adjacent)해 있다고 합니다. 같은 경우에 이 엣지는 두 노드에 부속(incident)한다고 합니다.

degree

한 노드의 차수(degree)란 해당 노드에 연결된 엣지의 수(혹은 엣지 가중치의 합)를 가리킵니다.

loop/isolated

다음 그림과 같이 한 엣지가 같은 노드에 부속해 있을 때 loop이라고 합니다.

이와 반대로 임의의 한 노드에 부속해 있는 엣지가 전혀 없을 때 해당 노드를 isolated vertex라고 합니다.

isomorphic

한 그래프의 두 노드를 연결하는 엣지가 하나이고, 다른 그래프에서 그에 대응하는 노드를 연결하는 엣지가 하나뿐일 때 두 그래프는 동형(同型, isomorphic)이라고 합니다. 쉽게 말해 두 그래프는 생김새만 다르게 생길 뿐 본질적으로는 구조가 같다는 이야기입니다. 다음 그림과 같습니다.

subgraph

임의의 그래프 $G=(V,E)$가 주어졌을 때 다음을 만족하는 $G’=(V’,E’)$는 $G$의 부분그래프(subgraph)라고 합니다.

• $E’$는 $V’$에만 부속(=$V’$에 속한 모든 엣지가 $G’$에 있어야 함)되어 있으며 $E$의 부분집합이다.
• $V’$는 $V$의 부분집합이다.

이 가운데 $V=V’$를 만족하는 부분그래프를 spanning subgraph라고 합니다. 쉽게 말해 원 그래프와 노드는 같고 일부 엣지만 포함된 부분그래프를 가리킵니다. 이 부분그래프가 트리을 만족할 경우 spanning tree라고 합니다. 하단 좌측과 우측의 그림이 원 그래프와 spanning subgraph를 예로 든 것입니다.

원 그래프를 spanning subgraph로 표현하면 노드 간 불필요한 관계 정보 처리를 생략할 수 있게 돼 효율성을 도모할 수 있다고 합니다.

complete graph/multigraph

모든 노드들이 엣지로 연결돼 있어, 엣지의 수가 최대인 그래프(하단 좌측)를 완전그래프(complete graph)라고 합니다. 노드 수가 4개라면 기호로 $K_4$라고 표시합니다. 반면 노드 사이를 잇는 엣지가 하나 이상일 경우 해당 엣지를 transitive하다고 하며, 이 그래프를 multigraph라고 합니다(하단 우측).

모든 노드들이 엣지로 연결된 부분그래프를 클리크(clique)라고 합니다. 아래 예시의 경우 클리크는 다음 여섯가지입니다.

• $a,b$
• $a,c,d$
• $b,g$
• $c,d,e,f$
• $c,f,h$
• $f,g$

이 가운데 노드의 수가 가장 많은 클리크($c,d,e,f$)를 maximum clique라고 합니다.

directed graph

방향그래프(directed graph, digraph)란 엣지가 순서가 있는 쌍으로 표현된 그래프의 일종입니다. 다시 말해 엣지가 방향성을 가집니다. 아래 그림처럼 $V_2$에서 $V_1$으로 향하는 엣지 $e_1$가 있다면, $V_2$를 predecessor/source, $V_1$을 successor/sink라고 부릅니다. 이 때 $e_1$을 $V_2$의 outgoing edge, $V_1$의 incoming edge라고 합니다.

방향그래프에서 한 노드의 차수(degree)는 incoming degree와 outgoing degree로 나뉩니다. 다시 말해 어떤 한 노드를 기준으로 들어오는 엣지 수(혹은 가중치의 합), 나가는 엣지 수(혹은 가중치의 합)이 바로 그것입니다. 아래 방향그래프에서 $V_1$의 incoming degree는 $e_1$, outgoing degree는 $e_2$, $e_3$가 됩니다.

$V_1$에서 $V_2$, $V_2$에서 $V_3$으로 각각 outgoing edge가 존재한다면, $V_1,V_2,V_3$를 체인(chain)이라고 합니다.

weighted graph

가중치그래프(weighted graph)란 엣지에 가중치 내지 우선순위 정보가 추가된 형태의 그래프입니다. 이 때 함수 $g$는 엣지를 가중치로 매핑하는 역할을 합니다.

물론 방향그래프 또한 가중치를 가질 수 있습니다. 이글 방향가중치그래프(directed weighted graph)라고 합니다.

path

그래프에서 경로(path)란 인접한 노드들로 구성된 시퀀스(1개 이상)를 가리킵니다. 엣지가 겹치지 않는 경로를 simple하다고 하고, 노드가 겹치지 않는 경로를 elementary하다고 합니다. 경로의 길이(length)는 경로 내 존재하는 엣지의 수를 나타냅니다. 다음과 같은 그래프의 노드 시퀀스가 있다고 칩시다.

• $[v_1, v_2, v_3, v_4, v_5, v_3, v_4, v_5]$
• $[v_1, v_2, v_3, v_4, v_5, v_8, v_6, v_4, v_7]$

위 예시에서 첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 그러나 엣지도, 노드도 겹치기 때문에 simple하지도, elementary하지도 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

cycle

사이클(cycle)이란 한 노드에서 시작해 해당 노드에서 끝나는 경로를 가리킵니다. 사이클(cycle) 또한 엣지가 겹치지 않는 경우 simple하다고 하고, 노드가 겹치지 않을 경우 elementary하다고 합니다. 위 그래프를 기준으로 아래의 두 개 노드 시퀀스를 보겠습니다.

• $[v_1, v_2, v_3, v_4, v_5, v_8, v_6, v_5, v_9, v_1]$
• $[v_1, v_2, v_3, v_4, v_5, v_9, v_1]$

첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 $v_1$으로 시작해 $v_1$으로 끝났으므로 사이클입니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 $v_1$으로 시작해 $v_1$으로 끝났으므로 사이클입니다. 엣지도, 노드도 겹치지 않기 때문에 각각 simple하고, elementary하다고 말할 수 있습니다.

만약 $n$개의 노드가 사이클을 이루고 있을 경우 이를 기호로 $C_n$이라고 표시합니다. 다음 그림과 같이 사이클이 없는 그래프를 acyclic하다고 합니다.

connected

임의의 두 노드가 연결되었다(connected)는 것은 두 노드 사이에 경로가 존재한다는 이야기입니다. 이와 관련해 다음과 같이 정의됩니다.

• 모든 노드쌍 사이에 경로가 존재하는 무방향그래프는 연결되었다고 말한다.
• 임의의 방향그래프에서 방향을 무시하고 보면 연결되어 있을 경우, 해당 방향 그래프는 연결되었다고 말한다.
• 방향그래프의 임의의 노드쌍 $a$, $b$에 대해 $a$에서 $b$로 가는 경로, $b$에서 $a$로 가는 경로가 존재한다면, 해당 방향그래프는 강연결(strongly connected)되었다고 말한다.

아래 방향그래프에서 방향을 무시하고 보면 이 그래프 내 임의의 노드쌍 사이에 모두 경로가 존재함을 알 수 있습니다. 따라서 아래 방향그래프는 connected graph입니다. 하지만 $v_1$에서 $v_3$로 가는 경로는 존재($v_1, v_2, v_3, v_9, v_3$)하나, 반대로 $v_3$에서 $v_1$으로 가는 경로는 존재하지 않는다는 점에서 strongly conntected graph는 아닙니다.

connected component

원 그래프 $G$에서 노드와 엣지가 서로 겹치지 않는(independent) 부그래프를 $G$의 요소(component)라고 합니다. 이들 요소 가운데 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 $S$를 $G$의 연결요소(connected component)라고 합니다. 그 정의상 연결그래프(connected graph)는 하나의 연결요소만을 가집니다.

원 그래프의 부분그래프들 사이에 겹치는 요소가 없고, 부분그래프의 합집합이 원 그래프를 이룰 때 이들 부분그래프를 파티션(partition)이라고 합니다. 아래 그림에서 15개 노드와 모든 엣지를 $G$로 본다면 $G$의 연결요소는 두 개이며, 이 연결요소는 $G$의 파티션입니다.

연결요소 가운데 노드 수가 가장 많은 연결요소를 최대연결요소(maximal connected component)라고 합니다.

Vertex/edge-cut

원그래프에서 어떤 노드를 제거해 부분그래프로 나누는 것을 vertex-cut이라고 합니다. 엣지를 제거해 부분그래프로 나누는 과정을 edge-cut이라고 합니다. 아래 예시에서 노드 $e$를 제거하면 vetex-cut, 노드 $e$와 노드 $x$를 잇는 엣지를 제거하면 원그래프가 두 개 부분그래프로 분리되면서 각각 vetex-cut, edge-cut이 됩니다.

가중치무방향그래프에서 제거 대상 엣지의 가중치가 최대가 되도록 하는 edge-cut 기법을 MaxCut, 최소로 하는 기법을 MinCut이라고 합니다.

Join

새로운 노드 $X$가 추가돼 기존 그래프 $V$의 모든 노드와 연결될 경우 조인(Join)이라고 합니다. 이때 기호로는 $V+X$라고 표기합니다.

edge complement

다음과 같은 관계를 지니는 두 그래프를 edge complement라고 합니다. 노드는 서로 같고 엣지 존재 양상이 정반대인 경우에 해당합니다.

releative complement

아래 그림과 같이 $H$는 $G$의 부그래프이고, $H$에 속한 모든 엣지를 제거한 그래프를 relative complement라고 합니다. 기호로는 $G-H$라고 씁니다.

graph representation

그래프를 컴퓨터가 처리하게 만드려면, 그래프를 적절한 자료구조로 변환해 주어야 합니다. 크게 두 가지 방식이 있는데요. 인접행렬(adjacency matrix)과 인접리스트(adjacency list)입니다. 각각 행렬과 연결리스트(linked list)로 구현합니다.

가중치가 없는 방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

가중치가 없는 방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

가중치가 있는 무방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같습니다. $∞$는 두 노드 사이에 엣지가 있고 가중치가 0인 경우와 대비하기 위해 만든 표지입니다.

가중치가 있는 무방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

시간복잡성

우선 전체 노드 수가 $V$개, 엣지 수가 $E$개일 때 시간복잡성을 따져보겠습니다. 분석 대상 연산은 (1) 임의의 두 노드($i, j$)가 주어졌을 때 인접해 있는지 여부(operation 1) (2) 임의의 한 노드($i$)가 주어졌을 때 인접해 있는 모든 노드를 찾기(operation 2) 등 두 가지입니다.

먼저 인접행렬의 경우입니다.

• operation 1 : 인접행렬에서 $i$행, $i$열을 참조하면 됩니다. 행렬의 한 원소를 액세스하는 데엔 $O(1)$의 시간복잡성이 듭니다.
• operation 2 : 인접행렬에서 $i$행 전체에 대해 조사하면 됩니다. 노드 전체를 따져봐야 하므로 $O($|$V$|$)$만큼의 시간복잡성이 듭니다.

인접리스트의 경우입니다.

• operation 1 : 인접리스트(연결리스트)에서 $i$번째 버킷에 속한 요소 가운데 $j$가 있는지 탐색(search)하려면 우선 전체 버킷 가운데 $i$번째 버킷을 찾은 뒤 이 버켓 내에 $j$가 있는지 따져야 합니다. $i$번째 노드의 차수를 $d$라고 할 때 $O(d)$의 시간복잡성이 듭니다. 참고로 전체 노드의 평균 차수는 |$E$|/|$V$|입니다.
• operation 2 : 인접리스트에서 $i$번째 버킷에 속한 모든 요소를 순회(traverse)하면서 출력합니다. 따라서 operation 1과 본질적으로 다르지 않습니다. $O(d)$만큼의 시간복잡성이 듭니다.

공간복잡성

이번엔 두 연산의 공간복잡성을 따져보겠습니다. 먼저 인접행렬의 경우입니다.

• operation 1 : 노드 수 × 노드 수만큼의 행렬이 필요합니다. 따라서 $O($|$V$|$^2)$만큼의 공간복잡성이 듭니다.
• operation 2 : 버킷은 전체 노드 수만큼 필요합니다. 각 노드를 잇는 포인터는 전체 엣지의 수만큼(무방향그래프의 경우 전체 엣지의 두 배) 필요합니다. 따라서 $O($|$V$|$+$|$E$|$)$만큼의 공간복잡성이 듭니다.

자료구조의 선택

‘노드와 엣지가 어떻게 구성되어 있는가’가 인접행렬 혹은 인접리스트를 택하는 데 중요한 요인이 됩니다. 예컨대 노드 수보다 엣지 수가 많은 dense graph의 경우 인접행렬을 쓰는 것이 좋습니다. 반대로 노드 수보다 엣지 수가 적은 sparse graph의 경우 인접리스트를 쓰는 것이 좋습니다.