레이블이 algorithm인 게시물을 표시합니다. 모든 게시물 표시
레이블이 algorithm인 게시물을 표시합니다. 모든 게시물 표시

[컴][알고리즘] skyline problem

divide and conquer /


작성중...

skyline problem

merge sort 와 비슷한방법으로 해결한다.(divide & conquer)

merge sort 가 값을 만들어가는 모양처럼, array 가 있으면 일단 개개별로 분할될 때까지 내려가고, 그 개개의 값들을 merge 하면서 값을 처리한다.(Merge sort gif 참고)

이 문제에서는 x 를 다시 정렬할 필요가 있다. 아래 그림처럼 값을 새로운 모양으로 바꾸면서, 정렬이 안된 상태가 되기 때문이다. 그러므로 이런 merge sort 방식이 잘 어울린다.

merge 부분

들어온 input 에 대해서 length 가 1일때(base condition)
"merge 할때 최종적으로 표현하려는 모양"을 return 한다.

여기서는 [[left, height], [left2, hegith2], ...] 이런 모양이다.


핵심은 두개의 배열을 돌면서 하나의 배열이 끝날때까지만 돈다.
그러면서 필요한 처리를 하고, 그 이후의 배열의 원소는 전부 append 한다.
element 단위에서부터 이 작업을 하기에 남아서 뒤에 붙이게 되는 값들은 전부 정렬이 된 이후의 값들이다.

while i < len(arr1) and j < len(arr2):
  ...
  i++
  j++

res.extend(arr1[i:])
res.extend(arr2[j:])

  • 여기서 계속해서 x 를 움직이고, 
  • x 에 해당하는 height 를 비교한다. 
  • merge 가 되면서, x 는 정렬이 되어 간다. 
  • 그러면서 x 지점의 height 가 좋은지 더 높은지 확인한다.
빌딩이 끝나는 곳에 해당하는 x 에서는 height 가 0 이기 때문에, x 위치에서 가장높은 height 만 선택하면 된다.(max(h1, h2))



python code

source from : ref. 1

def skyline(buildings):
    # building = [[left, right, height], [2, 9, 10], ...]
    if not buildings:
        return []
    if len(buildings) == 1:
        # [[left, height], ...]
        return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

    mid = len(buildings) // 2
    left = skyline(buildings[:mid])
    right = skyline(buildings[mid:])
    return merge(left, right)

def merge(left, right):
    h1, h2, hcurrent = 0, 0, 0
    i, j = 0, 0
    result = []

    while i < len(left) and j < len(right):
        x0 = left[i][0]
        x1 = right[j][0]
        if left[i][0] < right[j][0]:
            # 현재의 x 에 해당하는 h 를 선택한다.
            h1 = left[i][1]
            curX = left[i][0]
            i += 1
        elif right[j][0] < left[i][0]:
            h2 = right[j][1]
            curX = right[j][0]
            j += 1
        else:
            h1 = left[i][1]
            h2 = right[j][1]
            curX = right[j][0]
            i += 1
            j += 1
        # 현재의 h 는 h1, h2 중 하나이다. 그중에 큰 값을 선택한다.
        # x 가 변하면, h 도 같이 변한다. 
        # 건물이 끝나는 x 에선 h가 0 이 된다.
        if max(h1, h2) != hcurrent:
            hcurrent = max(h1, h2)
            result.append([curX, hcurrent])
    result.extend(right[j:])
    result.extend(left[i:])
    return result


See Also

  1. [컴][알고리즘] Merge sort

Reference

  1. performance - Python program to solve the "skyline problem" - Code Review Stack Exchange

[컴][알고리즘] 알고리즘 코드 학습에 도움이 되는 사이트

알고리즘 / algorithm / learning /

알고리즘 코드 학습에 도움이 되는 사이트

ref. 1 에 좋은 내용이 있다. 자세한 내용은 ref.1 을 참고하자. 여기는 그저 개인적으로 필요한 내용만 정리했다.

GeeksforGeeks

알고리즘 사이트

Reference

  1. [Algorithm] 알고리즘 공부 시작 방법 및 순서

[컴][알고리즘] Backtracking

백트래킹 / 조합 / 순열 / combination / 알고리즘 /recursive / python

backtracking

Permutation

순열의 성질중 아래 같은 성질을 이용해서 코딩을 한다.

아래 성질을 말로 풀면, (n-1)개에 대한 조합들이 있고, 그 조합에서 1개를 그 사이에 집어넣을 수 있는데, 그 경우의 수가 n 개이다.


def perms(elements):
    if len(elements) ==1:
        # yield elements
        return [elements]
    else:
        ret = []
        for perm in perms(elements[1:]):
            for i in range(len(elements)):
                # 한개를 정하고, 그 한개 이외의 값들을 permutation 을 하고, 
                # 그 한개의 위치만 바꾼다.

                # nb elements[0:1] works in both string and list contexts
                # yield perm[:i] + elements[0:1] + perm[i:]
                ret.append(perm[:i] + elements[0:1] + perm[i:])
        return perm

perms([1,2,3])

return of perms() perm elements i elements[0:1] perm[:i] + elements[0:1] + perm[i:]
[[3]] [3] [2,3] 0 [2] [2,3]
[[3]] [3] [2,3] 1 [2] [3,2]
[[2, 3], [3, 2]] [2,3] [1,2,3] 0 [1] [1,2,3]
[[2, 3], [3, 2]] [2,3] [1,2,3] 1 [1] [2,1,3]
[[2, 3], [3, 2]] [2,3] [1,2,3] 2 [1] [2,3,1]
[[2, 3], [3, 2]] [3,2] [1,2,3] 0 [1] [1,3,2]
[[2, 3], [3, 2]] [3,2] [1,2,3] 1 [1] [3,1,2]
[[2, 3], [3, 2]] [3,2] [1,2,3] 2 [1] [3,2,1]

Combinations

순착적으로만 선택하면 된다.

먼저 조합(combination)의 성질을 조금 알 필요가 있다. combination은 1,3 / 3,1 을 같은 선택으로 본다. 그렇기 때문에 만약 다음처럼 elements 가 있다고 한다면,
elements = [1,2,3]
우리가 앞에서 부터 순차적으로 선택한다면, 마지막 element 인 3을 선택한 이후에, 그 이전 element 를 선택할 필요가 없다. 즉, 1,3 을 선택했다면, 그 다음 2 를 선택해서, 1,3,2 를 선택할 필요가 없다. 왜냐하면, 이것은 1,2,3 에서 이미 만들어진 조합이기 때문이다.

여기서 명심할 것은 다음에 나오는 코드의 주 내용은 가능한 모든 combination 을 찾아주는 방법이지, combination 이 몇개인지를 나타내는 것이 아니다.

recursive version

nCr
ans = []
def backtracking(path, elements, r):
    if r == 0:
        ans.append(list(path)) # copy is needed
        return

    for index, num in enumerate(elements):
        path.append(num) # choose, 선택
        backtracking(path, elements[index + 1:], r - 1)
        path.pop()       # unchoose, 선택해제


backtracking([], [1,2,3], 2)


combinations_with_replacement

ref. 2에 combination python source 가 있다.

`i` 가 현재보고 있는 '자리'가 된다.
각 '자리'에 index 를 써놓는다.
가장 뒷 '자리' 부터 거꾸로 보는데,
그 '자리' 에 있는 index 가 마지막 index가 될 때까지, 보고있는 '자리'를 옮기지 않는다.
마지막 index 가 되면, 보고있는 '자리'를 한자리 앞으로 옮긴다.


'자리' 변경시
현재 보고 있는 '자리' 부터 뒷자리를, 현재 보고있는 '자리'의 index 값보다 +1 한 index 값으로 채운다.
1,1
1,2
1,3
2,1 ==> 1,2와 같다
2,2
2,3
이렇게 순서대로 가야 하는데, 이것은 조합(combination) 이라서 1,2 == 2,1 이 같다. 그래서 새로운 '자리'에 값을 증가 시킬때는 이미 지나온 '자리'에는 새로운 '자리'의 값보다 작은 값을 넣을 필요가 없다.

그래서 아래같은 code 를 사용한다.
indices[i:] = [indices[i] + 1] * (r - i)

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    ret = []
    indices = [0] * r
    # yield tuple(pool[i] for i in indices)
    ret.append(tuple(pool[i] for i in indices))
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        # yield tuple(pool[i] for i in indices)
        ret.append(tuple(pool[i] for i in indices))

combinations_with_replacement([4,5,6,7], 3)

indices

indices r i r-i indices[i] n-1 indices[i:] [indices[i] + 1] * (r - i) return
[0, 0, 0] 3 i=2 1 0 3 [0] [1] [(4, 4, 4)]
[0, 0, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5)]
[0, 0, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6)]
[0, 0, 3] 3 i=1 2 0 3 [0, 3] [1, 1] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7)]
[0, 1, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5)]
[0, 1, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6)]
[0, 1, 3] 3 i=1 2 1 3 [1, 3] [2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7)]
[0, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6)]
[0, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7)]
[0, 3, 3] 3 i=0 3 0 3 [0, 3, 3] [1, 1, 1] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7)]
[1, 1, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5)]
[1, 1, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6)]
[1, 1, 3] 3 i=1 2 1 3 [1, 3] [2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7)]
[1, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6)]
[1, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7)]
[1, 3, 3] 3 i=0 3 1 3 [1, 3, 3] [2, 2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7)]
[2, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6)]
[2, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6), (6, 6, 7)]
[2, 3, 3] 3 i=0 3 2 3 [2, 3, 3] [3, 3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6), (6, 6, 7), (6, 7, 7)]

See Also

Reference

  1. `python - How to generate all permutations of a list? - Stack Overflow
  2. itertools — Functions creating iterators for efficient looping — Python 3.8.3 documentation  
  3. https://makefortune2.tistory.com/227
  4. Combinations and Permutations with an Intro to Backtracking 

[컴][알고리즘] BFS breadth-first search

너비 우선 탐색 / bfs /









BFS breadth-first search

vertex s 에서 출발한다.

s 의 adj 는 A, B 이니,
먼저, A 가 level 에 있는지 본다.
A가 level 에 없으니 A에 대한 level (level['A']) 를 set 한다.
그 다음 B 가 level 에 있는지 본다.
B도 level 에 없으니 B에 대한 level (level['B']) 를 set 한다.
그리고 방문했던 A, B는 next 에 저장해 놓는다.
그래서 그 다음에 loop 을 돌 frontier 를 만들게 된다.

frontier 의 각 adj vertex 들을 접근하면서,
각 vertex 가 방문했는지를 level 이 채워져 있는지로 확인한다.
이미 방문한 애들은 그냥 skip 한다.

prarent 는 각 vertex 가 어디서 부터 왔는지를 저장한다. 이것을 거꾸로 하면, path 가 된다.

level = {}
parent = {}

def bfs(s, adj):
    level = {"s": 0}
    parent = {"s": None}
    i = 1
    frontier = [s] # level i-1
    while frontier:
        next = [] # level i
        for u in frontier:
            for v in adj[u]:
                if v not in level:
                    level[v] = i
                    parent[v] = u
                    next.append(v)
        frontier = next
        i += 1     
이 bfs 를 한번 돌리면, 연결된 "하나의 연결된 그래프"의 vertex 들을 전부 visit 하게 된다. 그리고 현재의 연결된 그래프와 연결되지 않은, 나머지 vertex 의 방문을 위해서는 bfs 를 다시 실행해야 한다.

See Also

  1. [컴][알고리즘] Depth-First Search DFS, 깊이우선 탐색

References

  1. 13. Breadth-First Search (BFS) - YouTube


[컴][알고리즘] AES 암호화 설명






  •  key expansion 은  key 를 4-byte 씩 쪼개어서 array 에 담는것
  • 16-byte 씩 작업을 하게 된다. 4 x 4 의 matrix 이다. 이 하나의 matrix을 state 라 부른다. 아래그림 참조
  • 각 정해진 bit 마다 round 가 정해져 있다.(128bit 은 10round, 256bit 는 14 round)
    • 각 bit 의 암호마다 "key-length/block-size/rounds" 수가 정해져 있다.
  • 이 (round-1)수 만큼 loop 을 돈다. 그리고 마지막 round 만 따로 한다.
  • 마지막 round 는 mix-columns 작업을 하지 않는다.

AES encryption process

1. SubBytes

sub 가 substitute 라고 보면 된다. State 에 있는 각 위치의 byte 에 해당하는 값을 "특정 table" 의 값과 교환하게 된다. 이 table 은 아래처럼 정해져있다.

여기 를 보면 어떻게 SubBytes 를 하는지 알 수 있다.

S = [ 
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01,
0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d,
0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4,
0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 0x04, 0xc7,
0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2,
0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e,
0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb,
0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb,
0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c,
0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c,
0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d,
0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a,
0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3,
0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d,
0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a,
0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e,
0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9,
0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9,
0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99,
0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 ]
from: https://www.youtube.com/watch?v=gP4PqVGudtg

2. Shift Rows

아래처럼 각 row 를 shift 한다. 0번째 열은 '0'번, 1번째 열은 '1'번 ...
from: https://www.youtube.com/watch?v=2y_tidbY-Lw

3. MixColumns

여기 를 보면 animation 을 볼 수 있다.

state 의 각 column 을 Galois field 와 곱하기(matrix 곱하기) 를 하게 된다. 만약 GF(255) 라면 0~255 사이의 숫자로만 구성된 field(matrix) 가 만들어진다.



4. Add Round Key

"State 의 각 byte" 와 "Round key 의 각 byte" 을 XOR 한다.
from: https://www.youtube.com/watch?v=2y_tidbY-Lw



CTR mode 사용시 유의할 점

  • PHP data encryption primer > Encryption algorithm / mode of operation / nonce (initializing vector)
    • single key 를 사용하는 경우는 nonce 가 unique 해야만 안전함을 보장한다.
    • ...



[컴][알고리즘] KNN

machine-learning / 머신러닝 / 알고리즘 / machine learning / ai /



k nearest neighbors classification(KNN)


어떻게 분류하는가?

이 KNN 을 우리말로 번역하면, "K개의 가장 가까운 이웃들" 정도가 되겠다.  일단 claaification 이라는 것은 "분류"를 이야기한다. 그러니까 KNN 은 분류를 하는 방법중 하나이다.

어떤 input(입력) 이 있을 때 KNN 이 어떻게 분류를 하냐면, "input 에 대해서 거리가 가장 가까운 이웃 k개의 모습을 확인하고, 그중에 가장많은 모습으로 input 의 모습을 결정(classify)"하는 것이다. "끼리끼리 노는 느낌"이라고 보면된다.

아래 그림에서 input (녹색) 을 보자. k=3 이면, input 은 "빨강" 이 되는 것이고, k=5 이면 input 은 "파랑" 이 되는 것이다.

  • k=3 일 때:  "빨강 2개" , "파랑 1개" --> input 은 빨강
  • k=5 일 때:  "빨강 2개" , "파랑 3개" --> input 은 파랑

from : ref. 2



거리, distance

이제 대략적으로 KNN 이 무엇인지는 알았다. 그럼 이제 좀 더 자세하게 보자.

위에서
"input 이 들어왔을 때 input 에서 거리가 가장 가까운 녀석 k개를 보고 분류(claasify) 를 한다"
고 했다. 그럼 여기서 문제는 "거리가 가장 가까운 녀석" 에서 "거리" 이다.

이 "거리" 를 측정하는 방법에 따라서 input 에 대해 3번째로 가까울 수도 있고, 1번째로 가까운 녀석이 될 수도 있다.

ref. 1 에 보면 이런 거리를 측정하는 방법 몇가지를 소개해 주고 있다.
from : ref. 1

위의 거리를 측정하는 방법 3개는 "연속적인 변수들"(continuous variables) 에서만 유효하다고 한다. categorical variables 에서는 Hamming distance 를 사용해야 한다고 한다.

이것은 또한 data set 에 숫자형 변수(numerical variables)들과 범주형 변수(categorical variables)들이 섞여있을 때 0과 1사이의 숫자형 변수들에 대한 표준화문제를 가져온다. (얘기가 어려운데 이 부분은 아래 "distance 의 표준화" 부분을 보자.)

from : ref. 1



적절한 K 값

이제 거리에 대한 정의도 되었다. 그러면 이제 k 값을 정해서 그냥 사용하면 된다. 여기서 누군가는 그럼 k 값은 얼마로 정해야 하지? 라고 물을지 모르겠다.

사실 이것은 상황에 따라 다르다. 그렇지 않으면 왜 굳이 K개를 선택하게 했겠는가? 그냥 값을 정해서 알고리즘을 만들었을 것이다.

하지만 어느정도 사람들이 사용을 해보니, 어느정도의 결론이 나왔다. 그 이야기가 ref. 1에 있다. 대략적으로 정리를 하면,

  • K값이 클수록 평균적인 잡음(noise) 를 제거해 준다면, 일반적으로 큰 K 값이 좀 더 정확한 결과를 가져다 준다.
  • cross-validation 이 좋은 K 값을 결정하는 다른 방법이다. (?)
  • 역사적으로 대부분의 dataset 에서 가장 적절한 K(optimal K) 는 3~10 사이의 값이다. 이 것이 k=1 보다는 훨씬 좋은 결과를 보여준다.



distance 의 표준화, standardized distance

거리를 계산할 때를 한 번 봐보자. 아래처럼 input(녹색) 에 대해 거리를 계산하게 될 텐데, 이 때 위에서 나온 함수중에 Euclidean(유클리디안) 을 이용한다고 생각해보자.

from : ref. 1
그럼 아래처럼 계산할 수 있다.
그런데 이때 문제는 '나이' 와 '대출' 의 범위가 다르다는 것이다. 그래서 숫자의 크기가 다르다. 위의 예제에서는 대출은 2십만이 넘어가는 숫자이지만, 나이는 70살이하이다. 숫자의 크기가 다르니, 거리값이 숫자가 큰 '대출' 의 값에 의해 결정될 여지가 많아지는 것이다.

그래서 이 문제를 해결하기 위해 값을 표준화(standardization, normalization) 을 해야 한다. 표준화는 그리 어렵지 않다. 아래처럼 해주면 된다.
무슨 뜻이냐 하면, 값 x 를 전체 값 대비해서 어느 위치에 있는 값인지로 변경하는 것이다.
이러면, 값의 범위(scale) 이 0 ~ 1 로 같아지게 되고, 어느 한 변수가 더 큰 영향을 미치는 경우를 막을 수 있다.


  • scaling : x / (max-min) <--- 이것을 scaling 이라 한다.
  • mean normalization : x - min  <---- 이것을 mean normalization 이라 한다.






References

  1. KNN Classification
  2. k-nearest neighbors algorithm - Wikipedia

[컴][알고리즘] Raft 알고리즘



Raft 알고리즘에 대한 설명은 ref. 2 를 먼저보자. 간결하게 그림을 이용해서 설명해 주기 때문에 이해하기가 더 쉽다. 아래 자료를 이해하는데에도 ref. 2 를 한 번 보고 보면 이해가 잘 될 것이다.

여기의 내용은 필자가 이해하려고 정리한 내용이라 내용이 부실할 수 있다. 그러니 되도록 Reference 에 적어놓은 원본을 확인하자.


State machine replication

분산에서 사용되는 Replication models(복제모델) 이 몇개 있는데(참고) , 이중에 State machine replication 이 있다. 이 모델이 distributed consensus 를 이용해서 만들어 졌다. 이 모델도 transactional replication model 처럼 많이 쓰인다.

이 모델은 replicated process 가 deterministic finite automation 이고 모든 event 에 대해 atomic broadcast 가 가능하다 는 것을 가정한다.

  • 가정
    1. replicated process 가 deterministic finite automation
    2. 모든 event 에 대해 atomic broadcast 가 가능하다


이 state machine replication 은 어떤 node(state machine) 가 동일한 순서로 input 을 처리한다면 동일한 순서의 output 이 나오게 된다. 그렇기 때문에 동일한 순서의 input 을 결정해서 그것을 모든 node 에 뿌려주는 작업을 해야 한다.



Distributed Consensus 는 뭔가?[ref. 1, 2]

이 동의(consensus)에 대한 이야기는 ref. 2 의 slide 를 보는 것이 효과적인 듯 하다.

consensus 동작을 설명하기 위해 "분산으로 구성된 database "를 보자. 이 db 는 각 node 가 같은 data 를 가지고 있어야 한다고 가정하자.

이 때 client 가 한 node 랑 통신을 할 것인데, 이 때 db 에 "x 라는 값을 5로 변경하라" 고 query 를 날렸다고 하자. 그러면 x 가 5으로 바뀌면 명령은 완료된다. 그런데 문제는 distributed system 이다. 여러개의 node 가 가지고 있는 x 라는 값이 다 똑같이 5로 바뀌어야 한다.

이렇게 여러개의 node 가 같은 명령(command) 을 수행해서 같은 동작을 하도록 하기 위해 필요한 것이 consensus(동의) 이다.

이 부분에 대해서는 여기서도 설명을 하겠지만 ref. 2 를 보는 것이 이해하기 좋다.

여하튼 모든 node 들이 같은 행동을 하기 위해서
  1. 일단 한 node (node A 라고 하자.)가 command 를 받으면 
  2. 그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
  3. 그리고 다른 node 들에게 그 command 를 날려준다.
  4. 그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
  5. log 를 적었다고 node A 에게 응답을 준다.
  6. 그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
  7. node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
  8. 그리고 client 에게 응답을 준다.

    이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
  9. 그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
  10. 그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.



아래는 ref. 1 에서 이야기하는 Consensus 에 대한 설명이다.

----------------------------------------------------------------

동의(Consensus) 는 fault-tolerant distributed system(문제가 발생해도 계속 잘 동작하는 분산시스템이라고 보면된다.) 에 기본적인 문제이다.

consensus 는 여러개의 서버들이 값들(values)에 대해 동의하는 것을 포함한다. 그들이 어떤 값에 대한 결정에 도달하자마자, 그것은 최종결정이다. 일반적인 consensus algorithm 들은 다수의 서버들이 동작할 때 일을 진행한다. 예를 들면, 5개 서버로 된 cluster 는 심지어 2개의 서버에 문제가 생겨도 일을 계속해 나갈 수 있다.  만약 더 많은 서버에 문제가 생기면, 그들은 일을 진행하는 것을 멈춘다.(그러나 절대 틀린 결과를 return 하지는 않을 것이다.)

동의는 일반적으로 fault-tolerant system 들을 만드는 일반적인 방법인 replicated state machine들이 있는 상황안에서 발생한다.
각각의 서버들은
  1. state machine과
  2. log 

를 갖는다. state machine 은 우리가 fault-tolerant 하고 싶은 구성요소(component)다. 예를 들면 hash table 같은 것이 있다.

client 는 하나의 믿을 수(reliable) 있는 state machine 과 상호작용하게된다.

각 state machine 은 input command 들을 그들의 log 로 부터 받는다.
우리의 hash table 예제에서, log 는 'x 를 3으로 set 하라' 같은 command 들을 가지고 있을 것이다. 서버들의 log 가 갖고 있는 command 에 대해 동의하기 위해서 consensus algorithm 을 사용한다.
consensus algorithm 은 다음과 같은 것을 보장해야만 한다.
  • 만약 n번째 command 로 어떤 state machine 이  'x 를 3으로 set 하라' 는 명령을 적용한다면, 
  • 다른 state machine 은 항상 다른 n번째 command 를 적용해야 한다. 

결과적으로 각각의 state machine 은 같은 series of commands 를 처리한다. 그리고 그래서 같은 series of result 들을 생산하고 같은 series of states 에 도달하게 된다.

----------------------------------------------------------------



Raft algorithm[ref. 3]

제일 일반적인 동의알고리즘(consensus algorithm) 은 Paxos 인데 이녀석은 이해하기 어렵고, 정확히 구현하기도 어렵다고 알려져 있다.

Raft 는 새로운 동의알고리즘(consensus algorithm)
이해가능함을 위해 디자인됐다.

Raft 는
  1. 먼저 server 를 leader 로 선출한다.
  2. 그리고 모든 결정들을 leader 에게 모아준다.
이 2가지 과정이 상대적으로 독립적이며 Paxos 보다 나은 구조를 만들어준다.

Raft 는 아래 방법을 이용해서 리더를 선출한다.
  1. 투표(voting) 와
  2. 랜덤화한 타임아웃(randomized timeouts) 
선거(election)는 리더가 이미 필요한 모든 정보를 저장했다는 것을 보장 해 준다. 그래서 데이터는 오직 리더에서 다른 서버들로만 흘러간다.

다른 leader-based algorithm 들과 비교하면, 이것은 방법(mechanism) 을 줄이고 행동을 단순화한다. 리더가 선출되며, 리더는 복사된 log 를 관리한다.

Raft 는 로그들이 어떻게 커지는 지에 관한 간단한 불변(simple invariant)을 레버리지(leverage)해서 알고리즘의 state space 를 줄이고 적은 mechanism 으로 이 작업을 달성한다.

Raft 는 이전의 알고리즘들에 비해 실제 세계 구현에도 적합하다. 이것은 실질적인 배포(deployments) 에도 충분히 잘 동작한다.

이것은 "고객 상호작용을 어떻게 관리하는지", "cluster 의 membership 을 어떻게 바꾸는지", 그리고 "로그가 너무 커졌을 때 그것을 어떻게 컴팩트하게 하는지"를 포함한 모든 완전한 시스템을 만드는 모든 측면을 언급한다.

cluster membership 을 바꾸기 위해, Raft 는 한번에 하나의 서버를 더하거나 뺀다.
(복잡한 변경은 이 기본 과정들로 작성할 수 있다.)

그리고 cluster 는 변경을 하는 중에도 계속해서 request 들을 계속 처리할 수 있다.



리더 선출(leader election)

node 의 state

node 는 다음 3가지 state 를 갖는다.

  1. follower
  2. candidate
  3. leader
처음 시작할 때 node 는 모두 follower 이다. 만약 follower 가 leader 를 가지고 있지 않으면 그들은 candidate 가 될 수 있다.

또는, node 는 leader 로 부터 heartbeat 을 주기적으로 받는데, 이 heart beat 이 오지 않아서 heartbeat timeout 이 끝나면 leader 를 가지고 있던 node 이지만, 이 node 는 candidate 가 되는 것이다.


2개의 timout 세팅

node 는 다음 두종류의 timeout 을 갖게 된다. 
  1. election timeout:
    follower 가 candidate 가 되기까지 걸리는 시간이다. 150ms ~ 300ms 사이의 random 한 값으로 각 node 가 각자 setting 한다.

    그리고 만약 2개의 node 가 candidate 가 되는 경우에는 같은 election term 을 가진 2개의 election 이 발생한다. 이 경우 각 candidate 가 vote 를 해달라고 node 에게 message 를 보낸다.

    그러면 한 node 는 같은 election term 을 가진 vote request 를 2개 받을 것이다.
    이 경우에 node 는 먼저 온 vote request 에 대해서만 응답을 해주고, 나중에 온 vote request 에는 응답을 하지 않는다.(node 는 한 election term 에 대해서 한개의 vote 만 한다.)

    이 때 누군가 과반수를 얻는다면 그 candidate 가 leader 가 되지만, 과반수를 얻지 못하면 candidate 가 timeout 되고 새로운 election term 을 시작하게 된다.

    아래 "leader 선출 과정" 참고
  2. heartbeat timeout
    주기적으로 leader 가 message 를 보내는데 이 heartbeat timeout 시간안에 보내야 leader 가 살아있다고 판단한다. 만약 이 시간안에 message 가 오지 않으면 node 는 바로 candidate 가 된다.


초기상태

이제 막 node 들의 설치가 끝나고 node 들을 실행(run) 했다고 가정해보자.

각 node 는 각자 150ms ~ 300ms 사이의 random 한 값으로 election timeout 을 setting 하고, 그 시간이 끝나면 follower 에서 candidate 로 상태가 바뀐다.

각 node 가 random 하게 timeout 을 설정했기 때문에 각자 candidate 로 상태가 바뀌는 시간이 다를 것이다.


leader 선출 과정

일단 candidate 가 된 node 는,

  1. 새로운 선거기간(election term) 을 시작한다. (termCount: 1)
  2. 그리고 자기한테 vote 하고, (voteCount: 1)
  3. 다른 node 에게 vote 를 해달라고 request 를 보낸다.(Request Vote message)

    이 때 timeout 시작한다. 이 timeout 까지 과반의 vote 를 획득해야 한다.

    참고로 다른 node 가 leader 라면서 message 를 보낼 수 있는데 이때는 termCount 가  자신보다 높은지를 확인하고, 높다면 자신은 follower 가 된다.

    자세한 사항은  In Search of an Understandable Consensus Algorithm > 5.2 Leader election 을 참고하자.
  4. 그러면 request 를 받은 node 들 중에 이 선거기간(election term) 에 "vote 를 하지 않은 node" 들은 candidate 에게 vote 를 해준다. 
  5. 그리고 이 node 들은 자신들의 election timeout 을 reset한다. 
  6. 이렇게 해서 한 candidate 가 과반수의 vote(majority of votes) 를 얻으면 그 candidate 가 leader 가 된다. 이 과반수가 leader 가 단 하나만이 존재하도록 보장해 준다.

    여러개의 candidate 가 vote 를 해달라고 node 에게 message 를 보내게 되면, node 는 같은 termCount(election term) 을 가진 request 을 여러개 받게 된다. 이 경우에 node 는 먼저 온 request 에 vote 를 하고, 뒤이어 오는 다른 request 에는 vote 를 하지 않는다.(한 election term 에는 한개의 vote 만을 하는 것이다.)

    이래서 만약 어떤 candidate 도 '과반수' 를 얻지 못한다면, candidate 들은 timeout 되고, 새로운 election term 을 시작하게 된다.


leader 와 heart beat(Append Entries message)

node 가 leader 가 되면

  1. leader 는 Append Entries message 를 follower 들에게 보내기 시작한다.
  2. 이 message 들은 각 node 들이  가지고 있는 heart beat timeout 에 의해 정해진 시간(interval)안에 node 들에게 도착하게 된다.
  3. 이 message 를 받으면 node 들은 heart beat timeout 을 reset 하고 다시 시작한다.
  4. 그리고 leader 에게 응답을 보낸다.
  5. 이 상태가 유지되면 election term 은 계속 같은 id 를 유지하게 된다.
follower 가 heart beat 을 받는 것을 멈추고 candidate 가 될 때까지, 선거기간(election term) 은 계속 된다. 즉 새로운 candidate 가 생겨서 새로운 election term 이 시작되기 까지는 기존의 election term 이 유지되는 것이다.

만약 현재 leader node 가 어떤 이유로 멈추면, hear beat timeout  시간안에 Append Entries message 가 오지 않아서 heartbeat timeout 이 끝나게 된다. 그럼 node 는 바로 candidate 가 되고, "leader 선출 과정" 을 시작하게 된다.



Log Replication, 로그 복제

로그는 client 가 request 한 command 를 적어놓은 것이기 때문에 로그 복제는 command 의 복제라고 보면 된다. 즉 로그 복제를 한다는 것은 실제 동작을 복사해서 follower node 에게 전달하는 것이다. (이것은 state machine 이기 때문에, 같은 순서의 command 를 제공하기만 한다면, 같은 결과를 가져오기 때문에 가능한 것이다.)

이 log replication 은 리더에 의해서 시작된다. 이는 Raft 에서 client 가 leader 에만 접근가능하기 때문이다.

여하튼 leader 는 위에서 heartbeat 로 사용했던 Append Entries message 를 이용해서 변경사항을 node 들에 전달한다.

이것을 대략 정리하면 아래와 같다.
  1. 일단 leader node (node A 라고 하자.)가 command 를 받으면 
  2. 그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
  3. 그리고 다른 node 들에게 그 command 를 날려준다.
  4. 그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
  5. log 를 적었다고 node A 에게 응답을 준다.
  6. 그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
  7. node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
  8. 그리고 client 에게 응답을 준다.

    이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
  9. 그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
  10. 그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.

관련해서 자세한 사항은 ref. 2 를 참고하자. ref.2 에는 추가적으로 partition 이 나눠져서 log 가 2개가 생기는 경우에 대한 예제도 있다.



Client

client 가 처음에 cluster 에 접근하게 되거나 leader 가 crash 되었거나 하면, 여러 node 중에 아무 node 에나 접근하게 된다. 이 때 node 는 이 client 를 무조건 reject 하고 leader 정보를 준다. 그럼 client 가 이 정보를 가지고 다시 leader 로 접근하게 된다.

원래 node 가 leader node 로 부터 AppendEntries message 를 주기적으로 받는데, 이 녀석에 leader 의 network 주소도 같이 있어서 redirect 시켜주는 것은 어렵지 않다.


Read-only operation

Read-only 명령은 log 에 굳이 명령을 적지 않고 수행해도 문제가 없다. 다만 이 경우에 return 해주는 data 가 오래된 data(stale data) 가 아니어야만 한다. 

그런데 client 가 통신하고 있는 도중에 leader 가 교체된 상태라면, data 는 최신 data 를 보장할 수 없다. client 에게 return 하는 data 가 아직 leader 의 최신 data 로 update되지 않은 data 일 수 있다.


stale data 의 보장

log 를 이용하지 않고 stale data 가 아닌것을 보장하기 위해 Raft 에서 2가지 예방책이 필요하다.
  1. 리더가 최근 정보를 가져야만 한다. 이정보의 내용들은 당연히 commit 이 이미 된 내용(committed entries)이어야 한다.(Leader Completeness Property )

    그러나 term 의 시작시점에서는 log 에 적혀있는 entry 중에 어떤 녀석이 commit 된 내용인지 알 수 없다.(ref. 4 > figure 8 참고)

    이것을 알기 위해서 Raft 에서는 각 리더가 term 의 시작시점에 blank no-op entry 를 log 에 commit 한다. (그러니까 no-op entry 에 대한 commit 까지 완료하면, 이전의 entry 들은 commit 이 제대로 됐다고 볼 수 있다?)
  2. 두번째로 리더 노드는 read-only request 를 처리하기 전에 자신이 리더에서 물러난 상태인지 여부를 확인해야만 한다.

    Raft 는 read-only reqeust 에 응답하기 전에 리더가 heartbeat message 를 cluster 의 과반수의 node 와 교환하게해서 이것을 처리한다.



User-group

궁금한 점은 아래 user-group 을 이용하면 될 듯 하다.

See Also


  1. Introducing Runway, a distributed systems design tool : Runway system 을 소개해 준다. 분산시스템 디자인(distributed system design) 을 위한 tool 이다.
  2. GitHub - salesforce/runway-browser: Interactive visualization framework for Runway models of distributed systems : Github of Runway system 


References

  1. Raft Consensus Algorithm: raft 알고리즘과 관련된 자료들이 전부 모아져 있다. 동영상, library 들의 link 도 있다.
  2. The Secret Lives of Data : Raft 설명, 자세하게 예제를 slide 를 이용해서 설명해준다.
  3. Diego Ongaro's PhD dissertation, Consensus: Bridging Theory and Practice, published by Stanford University in 2014 > Abstract
  4. In Search of an Understandable Consensus Algorithm









[컴][알고리즘] 얼굴 인식, 안면인식




Face recognition

face recognition (안면인식)에 대한 글이 있어서 정리를 좀 해본다. 대부분의 내용은 번역이 될 듯 하고, 개인적으로 이해한 대로 좀 각색하게 될 듯 하다.

동작

컴퓨터가 얼굴을 인식할 때 아래 4가지 과정을 거치게 된다.
  1. 먼저, 사진을 보고, 그곳에 있는 모든 얼굴을 찾는다.
  2. 2번째로 각각의 얼굴에 집중하고, 얼굴이 이상한 방향으로 되어 있고, 조명이 좋지 않아도 그것은 여전히 같은 사람이라는 것을 이해할 수 있어야 한다.
  3. 3번째로 다른 사람과 다른 고유한 특징(unique features)들을 뽑아낼 수 있어야 한다. 예를 들면 눈이 얼마나 큰지, 얼굴이 얼마나 긴지 등의 요소들
  4. 마지막으로 이 고유한 특징을 당신이 이름을 알고 있는 모든 사람들과 비교한다.

Step 1. 얼굴 찾기

얼굴찾기 알고리즘

Paul Viola 와 Michael Jones 가 값싼 카메라에서도 충분히 빠르게 얼굴을 찾는 방법을 발명했다. 그 덕분에 2000년대초에 얼굴인식 이 주류가 될 수 있었다.

요새는 좀 더 신뢰성있는 알고리즘을 사용한다. 그 알고리즘이 Histogram of Oriented Gradients(HOG) 이다. 2005년 만들어졌다.

HOG

HOG 에서는 SIFT 방법을 사용해서 이미지의 윤곽을 인식한다.

SIFT

정확한 SIFT 방법은 여기 를 참고하자. 여기서는 대략적으로 어떤 식으로 동작하는지 알아보는 정도 수준이라는 것만 명심하자.


color 정보가 필요없으니, 이미지를 흑백으로 만든다.

이 이미지를 한 픽셀(pixel) 씩 보기 시작한다. 그러면서 이 pixel 의 위아래옆에 있는 8개의 pixel 도 같이 본다.

목표는 현재 보는 pixel 이 주위 8개의 pixel 보다 얼마나 어두운지를 알아내는 것이다.
그래서 어두워지는 방향으로 화살표를 그리는 것이다. 예를 들면, 현재 pixel 보다 위가 더 어두우면 up-arrow 를 사용하고, 위와 오른쪽이 더 어둡다면 up-right arrow 를 사용하는 것이다. 이렇게 되면 모든 pixel 은 화살표로 채워진다.

그리고 여기에 더해서 그 정도의 차이를 구한다. 그러니까 현재 pixel 에 비해 얼마나 진한가등의 정보를 구한다. 그래서 이 "방향 + 진한정도(magnitude)" 가 한개의 vector 가 되는 것이다. 이 화살표 vector 를 gradient 라고 부른다.
(실제로 구현은, 각 방향에 대한 gradient 값(histogram) 을 저장하는 형식으로 구현되는 듯 하다.)

이렇게 하면 어떤 방향으로 갈수록 더 어두워지는지를 알 수 있게 된다. 이 방법의 장점은 빛의 방향(?)을 알 수 있게 돼서 너무 밝은 사진에서도, 너무 어둡게 찍힌 사진에서도 사람의 형체를 알아보기가 수월해진다. 다시 말하면, 윤곽을 어두운 정도로 찾아내기 때문에 명확한 구분이 되는 선이 보이지 않아도 가능하다.

그런데 이 gradient 는 너무 세세한 level (그러니까 pixel level) 로 되어 있다. 그래서 오히려 형체를 알아보기가 어렵다. 장님이 코끼리 만지는 느낌이랄까. 그래서 좀 더 higher level 로 이 gradient 를 만들어야 한다. 그래서 이것을 16x16 pixcel 단위로 나눈다. 이 16x16 단위를 cell 이라고 부르자.( Histogram of Oriented Gradients(HOG)  에서는 16x16, 8x8 로 쪼개는 것이 효율적이라고 이야기한다. 자세한 내용은 원문을 참고하자.)

그래서 그 안에서 각 direction 에 해당하는 magnitude 의 합을 구하면, 어느 방향이 가장 큰 magnitude 를 가지는지 알 수 있다. 그 방향이 그  단위의 major direction (dominant direction)이 되는 것이다.

각 방향별로 vector 가 있다. 긴 화살표가 더 큰 magitude 를 나타낸다.

그 cell 을 major direction 을 표현하는 image 로 바꿔 놓는다. 그러면 이제 우리는 대략적인 윤곽을 보여주는 image 를 갖게 된다. 이것을 HOG image 라고 하자.

컴퓨터에게 A에 대한 여러 사진을 주면, 컴퓨터가 HOG image 들을 생성하고, 이 image 를 이용해서 A 에 대한 HOG pattern 을 만든다.

이것을 새롭게 올라온 사진의 HOG image 가 어떤 HOG image 와 비슷한지를 봐서 누구인지를 판단하는 것이다.(machine learning)

python 과 dlib 를 이용해서 구현할 수 있다.



작성중....


References

  1. Machine Learning is Fun! Part 4: Modern Face Recognition with Deep Learning — Medium
  2. http://www.scholarpedia.org/article/Scale_Invariant_Feature_Transform
  3. http://www.inf.fu-berlin.de/lehre/SS09/CV/uebungen/uebung09/SIFT.pdf



















[컴][알고리즘] liked list 에 cycle이 존재하는 지 판단 하는 방법

자바 알고리즘 / 링크드 리스트에 loop / linked list 에 loop 이 있는지 판단하는 방법 / circular linked list



liked list 에 cycle이 존재하는 지 판단 하는 방법

linked list 가 있을 때 이 linked list 가 loop 인지(즉, cycle) 아닌지를 판단하는 방법에 대한 알고리즘을 ref. 1 에서 설명하고 있다.

개인적으로는 내가 지나온 길을 기억하고 있다가, 내가 간 길이 지나온 길과 같으면 있다고 판단하려 했는데, 이 방법은 확실히 큰 linked list 에서 memory 가 많이 필요하게 된다.

ref. 1 에서는 훨씬 간단한 방법을 채용하고 있다. 방법은 이해하고 나면 쉽다. 이 방법을 이해하는데에는 역시 비유가 좋을 듯 하다.

토끼와 거북이가 운동장 트랙을 계속해서 도는 모습을 상상하면 된다. 그러면 둘의 속력이 다르기 때문에 둘은 언젠가 만난다. 이것을 코드로 옮긴 것이 ref. 1 이다.

만약 토끼가 어딘가 막다른 곳에 다다른다면, 그것은 운동장 트랙이 cycle 이 아니라는 이야기가 된다. cycle 이라면 계속해서 몇바퀴를 돌 게 될 테고, 결국 거북이를 만날테니까 말이다.

그래서 "토끼" 는 2개씩 node를 jump 해서 움직이고, "거북이" 는 1개씩 node 를 움직이다.

실질적인 코드는 ref. 1 을 확인하자.

Reference

  1. How to Find if Linked List contains Loops or Cycles in Java - Coding Question

[컴][알고리즘] Merge sort

Merge sort / 머지 소트 / 정렬 알고리즘

목차
  1. Insertion sort
  2. quick sort
  3. merge sort
  4. heap sort

Merge sort


머지는 말그대로 합치는 것이다. 근데 이렇게 합칠 때 two finger algo 를 이용해 정렬을 하면서 합친다.
얘는 quick sort 와의 차이는 이렇다.
퀵은 쪼개서 내려가면서 정렬을 한다.
머지는 쪼갠후에 다시 돌아오는 과정에서 머지를 한다.(top-down 과 bottom-up 방식이 있다.)

여기서는 top-down 방식을 이야기한다.

무엇을 합치느냐 하면 정렬하려는 리스트를 일단 낱개로 쪼갠다.
(이미 낱개니까 굳이 쪼개지 않아도 되지만 일단 쪼개진 상태라는 것을 잘 기억하자.)


이 쪼개진 녀석을 짝짓자.
처음에는 두개씩.
그리고 제자리를 찾아주자. 즉, 값이 큰 녀석을 오른쪽으로 두고, 작은 녀석을 왼쪽으로 두자.
그럼 이제 두개는 정렬이 끝났다. 그러면 이 "두개"를 다른 "두개"와 비교하자.
각각의 "두개"는 왼쪽에 가장 작은 값이 있다. 그래서 두 "두개"의 가장 왼쪽값을 비교한다.
"두개"중 더 작은 값을 왼쪽에 놓는다.
그리고 다시 남은 한개의 가장 작은 값과 나머지 "두개"의 가장 작은 값을 가지고 비교한다. 그리고 작은 값을 또 왼쪽에 놓는다.
이런식으로 반복해서 두 "두개"가 정렬돼서 합쳐진다.

그 다음은 당연히 8개를 가지고 한다.
그런데 그럴려면 당연히 다른 4개가 정렬되어 있어야 한다.
이렇기에 처음엔 두개, 다음엔 4개, 이런것을 구현하려면 거꾸로가 편하다

계속 나눠서 가장 작은 단위부터 merge sort 한다.
가장 작은 단위에 도달하면 Merge를 시작한다.
그리고 이 merge 한 결과를 return 해 준다.
그리고 이 return 한 결과 두개를 가지고 또 merge 한다.
이런식으로 최후에 merge 를 하면 된다.


Codes


from heapq import merge
 
def merge_sort(m):
    if len(m) <= 1:
        return m
 
    middle = len(m) / 2
    left = m[:middle]
    right = m[middle:]
 
    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

Source codes from : http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python


Reference

  1. http://en.wikipedia.org/wiki/Merge_sort

[컴][알고리즘] insertion sort

정렬 알고리즘 / insertion sort / 삽입 정렬

목차
  1. Insertion sort
  2. quick sort
  3. merge sort
  4. heap sort

insertion sort

이것은 중간에 끼어넣는 insertion 을 이용한다.

ref. 1 의 움직이는 예제를 보면 이해가 쉽다. ref. 1 의 그림을 보면서 이 글을 보도록 하자.

일렬로 놓은 숫자박스가 있다고 생각하고, 그 숫자박스들을 순서대로 들어서 앞쪽으로 숫자크기에 맞게 정렬한다고 생각하면 된다.

어디다 insertion 을 하는가 하면 앞쪽으로 한다.
이때 앞쪽은 당연히 정렬되어 있어야 한다.
뒤쪽으로 해도 상관없을 듯

큰 녀석이 뒤로 오도록 정렬하자.

앞쪽에 insertion 을 하려면 첫번째 녀석은 의미가 없어서 두번째 녀석으로 시작한다.
두번째 녀석을 선택하고 앞쪽 녀석과. 비교한다.
앞쪽 녀석(첫번째)이 더 크면 앞쪽 녀석과 두번째 녀석을 바꾼다.

그 다음, 세번째 녀석을 가지고 비교를 시작한다.
앞의 녀석이 이미 정렬되어있으니 그냥 자기보다 작은 녀석이 나올 때까지 바꿔치면 된다.
그래서 selection sort 보다 write 이 많은 이유가 된다.

이렇게 swap 을 하는 것이 조금 간단한 방법이다.

원래는 이렇다.

앞쪽녀석들은 정렬되어 있으니 이 세번째 녀석이 들어갈 자리를 일단 찾자.
앞쪽의 녀석과 하나씩비교해서 현재값보다 작은 녀석이 "최초로 있는 곳"을 찾는다.
그곳 바로 옆에 세번째 녀석을 insertion 하면 된다.

insertion 을 하는 것은 당연히 그 녀석이 들어가는 위치 뒤의 녀석들을 뒤로 미는 것이라서 shifting 을 한다.
내 현재값의 인덱스의 앞쪽 녀석을 순차적으로 뒤로 옮긴다.
그리고 원하는 insertion 시점이 시프트되면 그만 시프트하고 거기에 값을 넣는다.
근데 이것을 줄이기 위해 만나기 전까지 계속 스왑한다.


See Also

  1. Insertion Sort - GeeksforGeeks

Reference

  1. http://en.wikipedia.org/wiki/Insertion_sort


[컴][알고리즘] heap sort - 힙소트



개념

min heap 또는 max heap 을 이용한다.
이 두개의 힙은 complete binary tree 의 모양을 갖는다.
Max heap 이나 min heap 을 만들 수 있으면 힙정렬을 사용할 수 있다.

핵심은 heapify

정렬되지 않은 리스트를 일단 맥스힙(max heap)으로 만들자.
쭉 훑으며 내려가면서(traverse, 트래버싱)
가장 큰 값이 위로 올라오도록 한다.

맥스힙인 상태에서 기장 위의 값을 가장 뒤의 값과 바꾸고
나머지 녀석을 다시 맥스힙으로 만든다.
이때 처음부터 훑으면서 내려간다.

그러면서 큰 녀석과 스왑하고 그 다음 내려가서 또 두개의.차일드 중에서 큰.녀석과 스왑하고 해서 결국 스왑할 곳이 없는 상태에서 멈춘다.
그리고 다시 맥스값을 마지막녀석과 바꾼다.

min heap 인 경우
민힙(min heap)도 처음에 훑으면서 맨위 값을 차일드와 비교해서 차일드가 작으면 스왑하고 만약 둘다 작으면 더 작은 값과 스왑하고 쭉 내려간다.
근데 스왑한 녀석이랑 그 부모와 비교해서 스왑당한 녀석이 더 작으면 그녀석을 위로 올린다.



http://proneer.tistory.com/m/293
heap 정렬을 잘 설명해 준다.
동영상(?) 도 있어서 이해하기 쉽다.
heap 은 complete binary tree 이다. 는 전제를 알고 있어야 한다. 이 전제를 바탕으로 만들어 놓은 sort 이다.

heap sort

  • heap sort 에 걸리는 time complexity : O(nlogn)
    • n : n 개의 node
    • logn : binary tree 의 depth,
      min heap 을 만들려고 하는데, node 가 가장 작은 값이 가장 밑에 있는 경우 heapify 를 하는 데에 logn 번의 비교를 하고 올라와야 한다.

heap 정렬은 n/2 로부터 시작하는데
그런데 index 가 0 으로부터 시작하지 않고, 1로 부터 시작하는 경우
n/2 는 마지막 leaf node 의 부모node 가 된다.
  1. 즉 마지막 node 의 부모 node를 선택(이제 부터 1개씩 줄어들면, 자식node 를 가진 부모node 들을 역순으로 순차적으로 접근할 수 있다.)
    부모node 와 자식node 의 값을 비교해서
  2. min heap
    부모node 가 작으면 놔두고,
    부모node 가 크면 자식node 와 swap
    swap 이 돼서 내려갔는데, 그 node의 child node와 비교했는데, 여전히 크다면 다시 swap 한다.(즉, 조건을 만족하는 상태에서 가능한한 가장 밑으로 내려 보낸다.)
  3. min heap 이 되어 있는 상태에서는 root 에 가장 작은 값이 있다.
  4. 이제 root 를 가장 마지막 leaf node 와 swap 하자.
    그러면 가장 작은 값이 가장 밑으로 내려가게 된다.
  5. 이제 가장 작은 값을 제외한 나머지 부분을 다시 min heap 으로 만든다.

See Also

  1. [질문] 퀵 정렬과 힙 정렬의 비교에 관해 질문드립니다., 2009년 11월, KLDP

[컴][알고리즘] Quicksort 퀵소트 설명


목차
  1. Insertion sort
  2. quick sort
  3. merge sort
  4. heap sort


개략적인 개념

quicksort 는 partition 을 이용해서 정렬하는 것이다.

이 파티션은 분할이란 뜻.
이게 쪼개는 것은 맞는데 조건이 있다. 쪼개는 녀석을 중심으로 구분이 되어야 한다는 것이다.
무슨 구분이겠는가 뭐 당연히 크거나 작거나 이런 것들일 것이다.
그래서 이 파티션의 핵심은
기준을 정하고 큰 부분과 작은 부분으로 나누는 것이다.
그러고 이 중심을 알려준다. 이 중심이 pivot 이다.

결국 어떤 기준으로 나누는 것이다. 이 어떤기준을 중심으로 작은 녀석을 한쪽으로 몰고 큰 녀석들을 반대 편으로 모는 것이다.
그러면 이 기준을 중심으로 나눴다고 볼 수 있는 것이다.
이 기준은 우리가 임의로 정한다. 예를 들면 중간값 같은 것들.


만약 우리가 학생들을 키를 기준으로 4그룹으로 나눈다고 하자. 그러면 아래처럼 할 수 있다.

160 이상은 오른쪽으로 160미만은 왼쪽으로 모여라고 할 것이다.
이 후에 오른쪽 그룹에선 다시 175 를 기준으로 작은 사람은 왼쪽, 175 이상인 사람은 오른쪽으로 모이게 한다.
그리고 왼쪽 그룹에선 다시 145 이상은 오른쪽 145 미만은 왼쪽으로 모이라고 한다.
이렇게 그룹을 나누는 것이 퀵소트의 "파티션(partition)"이다.

근데 만약 이 학급의 학생이 4명이라고 하고, 143, 147, 165,  178 이라고 생각해보자.
그러면 이 학급의 학생들은 이렇게 모이라고 동작만으로 정렬이 완성된다.


QuickSort

quicksort 의 전체적인 내용은 ref. 1 을 참고하자. 여기서는 ref.1 의 내용 중에서 in-place version , 그러니까 storage space 를 별로 사용하지 않는 방법에 대해서만 얘기할 것이다.

partition 의 역할은 partition 함수를 실행하면, pivot 값을 중심으로 pivot 보다 작은 녀석들을 모두 왼쪽으로 옮기면, 자동으로 오른쪽에는 pivot 보다 큰 녀석이 남게 된다.

즉, 정렬이라는 것이 각 원소의 자리를 찾아주는 것이라고 한다면, partition 이 끝나면, pivot 의 자리가 정해진다고 보면 되겠다.

이 상황에서 마지막으로 pivot 값을 옮겨 놓으면, pivot 의 왼쪽에 pivot 보다 작은 값들이 있게 되고, 오른쪽에 pivot 보다 큰 값이 있게 된다. 아래에서 좀 더 자세하게 얘기하기로 하자.

Partition

여기서는 pivot 보다 작거나 같은 값들을 swap 하기로 하자.
value <= pivot

5를 pivot 으로 선택했다.
먼저 pivot 을 가장 오른쪽으로 옮긴다.
2, 3, 4, 5, 7, 5, 3
2, 3, 4, 3, 7, 5, 5
왼쪽에서 부터 pivot 보다 작은지 검사하고, 작으면 왼쪽으로 옮긴다.(왼쪽으로 옮기는 것을 enqueue 하는 것처럼 생각하면 된다.)
2, 3, 4, 3, 7, 5, 5


2 3, 4, 3, 7, 5, 5



2, 3  4, 3, 7, 5, 5



2, 3, 4 , 3, 7, 5, 5



2, 3, 4, 3 , 7, 5, 5


그러다가 pivot 보다 큰 값이 나오면 아무 일도 하지 않고, 그 다음 값을 검사한다.

2, 3, 4, 3 , 7, 5, 5


2, 3, 4, 3 , 7, 5, 5



2, 3, 4, 3, 5 , 7, 5

이제 pivot 바로 전까지 검사를 마쳤으면, 마지막으로 pivot 을 왼쪽으로 옮긴다.

2, 3, 4, 3, 5, 5  , 7

그러면, pivot 이 가장 오른쪽에 있는 list 가 하나 만들어진 것이다.

이 녀석을 남아있는 list 의 앞쪽으로 합치면, pivot 왼쪽에는 pivot 보다 작거나 같은 값들이 모여 있게 되고, 오른쪽에는 pivot 보다 큰 값만 남게 된다.

이 때의 pivot 이 가진 index 값이 중요하다.

pivot 을 중심으로 왼쪽을 partition 을 하고, 오른쪽을 partition 한다.

계속 partition 을 하면서 pivot 을 중심으로 계속 왼쪽에는 작은 수, 오른쪽에는 큰 수를 넣으면, 결국 모든 부분이 정렬되게 된다.

여기서 아래그림처럼 정확히 반으로 나뉘는 경우가 pivot 이 정확히 가운데값(mid) 을 가지는 경우이고, 그래서 partition 을 logn 번을 하게 되는 것이다.

반대로 최악의 경우는 pivot 이 한쪽 끝에 있는 값이어서 둘로 나눴을 때 한쪽이 0 이 되어서 결국 한쪽만 남는 경우다. 이렇게 계속해서 최소,최대값이 pivot 이 된다면, n-1 번의 partition 을 해야 돼서 최악의 시간(O(n2))이 소요될 것이다.

image



Pseudocode


ref. 1 에 보면 pseudocode 를 볼 수 있다.

그리고, 아래에는 python 으로 짠 간단한 코드를 볼 수 있다. 이해를 위해서 swap 과 enqueue 는 같은 역할을 하지만 구분해 놨다.

def swap(data, tail, b) :

    data[tail], data[b] = data[b], data[tail]



    

def enqueue(data, tail, b) :

    data[tail], data[b] = data[b], data[tail]
    

def partition(input, left, right, pidx) :
    pivot = input[pidx]

    # swap(pidx, right)
    swap(input, pidx, right)

    tailIndex = left
    for i in range(left, right) :
        # enqueue value equal or less than pivot into left side queue
        if input[i] <= pivot :
            # swap(i, tailIndex)
            enqueue(input, i, tailIndex)
            tailIndex += 1
    enqueue(input, tailIndex, right)

    return tailIndex


def quicksort(input, left, right) :


    if left < right :
        # select and remove a pivot value from input
        pivotIdx = (left+right)/2

        pivotNewIdx = partition(input, left, right, pivotIdx)
        
        print pivotNewIdx, input[left:pivotNewIdx], input[pivotNewIdx+1:right+1]
        
        quicksort(input, left, pivotNewIdx - 1)
        quicksort(input, pivotNewIdx + 1, right)



if __name__ == '__main__':
    str = '2345753'
    left = 0
    right = len(str)-1
    quicksort(list(str), left, right)

See Also




Reference

  1. http://en.wikipedia.org/wiki/Quicksort