Computer Vision 대학원생 기록지

https://github.com/recong/Boundless-in-Pytorch/tree/56e1c6c4a58daeab4b244223a9e92405af3e3331

CUDA 11.0

python 3.7

pytorch 1.71+

torchsummary

scipy

https://github.com/kdh4672/hgonet

설치 라이브러리:

python = 3.7, pytorch=1.110

pip install opencv-python
pip install pyyaml
pip install scipy
pip install scikit-image
pip install timm
pip install einops

코딩테스트 연습 - 빛의 경로 사이클 | 프로그래머스 (programmers.co.kr)

REVIEW

• graph와 경로의 길이를 보고 bfs 문제인가 싶지만 여러 대안 경로 중에서 나은 것을 선택하는 것이 아니라, 각 node 마다 주어진 S, R, L 명령구에 따라 경로가 정해지기 때문에 bfs로 풀 필요가 없다. 
• 같은 노드여도 어느 방향에서 들어왔는지에 따라 구분되기 때문에 visited를 만들 때 3차원으로 만들어 방향 정보를 추가하였다. 따라서 node b에서 북쪽으로 나아갔다면, 다음 번에 node b에서 남쪽으로 나아갈 때는 visited 여부가 False가 된다.
• 방문한 적 없는 노드에서 시작하여 방문한 적이 있는 노드에 방문하게 된 경우 사이클이 발생한 것이다.
• 이전 사이클에서 이미 방문한 노드가 이번 사이클에서 방문한 것으로 오인되는 것이 아닌가라고 생각할 수 있지만, 동일한 경로가 아닌 이상 동일한 노드에 대하여 동일한 방향으로 방문하는 일은 없다. (각 노드마다 변하지 않는 명령구가 있기 때문이다.) 
• 또한 이러한 특성 덕분에 중복되는 경로를 answer에 추가하는 경우를 피할 수 있었다.

# direction: north=0, east=1, south=2, west=3
from collections import deque


def direction(oper, d):
    
    if oper == 'L': 
        d = (d-1)%4
    elif oper == 'R': 
        d = (d+1)%4
    return d
    
def bfs(x, y, d, width, height, graph, grid):
    
    count = 0
    start = [x, y, d]
    while True:
        # add current node to Visited
        if graph[x][y][d]:
            ans = count
            count = 0
            return ans
        graph[x][y][d] = 1
        count += 1
        
        # Move
        # to North
        if d == 0:
            x = (x+1)%height
        # to East
        elif d == 1:
            y = (y+1)%width
        # to South
        elif d ==2:
            x = (x-1)%height
        # to West
        else:
            y = (y-1)%width
        
        # change direction
        d = direction(grid[x][y], d)
        
def solution(grid):
    graph = [[[0, 0, 0, 0] for _ in range(len(grid[0]))] for _ in range(len(grid))]
    answer = []
    
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if graph[i][j][k] != 1:
                    num = bfs(i, j, k, len(grid[0]), len(grid), graph, grid)
                    answer.append(num)
    answer.sort()
    return answer

9461번: 파도반 수열 (acmicpc.net)

REVIEW

• P(N)이 증가하는 패턴만 알아내면 어렵지 않게 풀 수 있는 문제이다.
• P(1), P(2), P(3)은 1이다. 
• P(4)부터는 패턴이 있는데 바로 P(N)은 P(N-2) + P(N-3)과 일치한다는 것이다.
• 예를 들어서 P(4)는 2로, P(2)의 1, P(3)의 1의 합과 동일하다. 
• 따라서 N > 3일 때, P(N) = P(N-2) + P(N-3)이다.

t = int(input())

for _ in range(t):
    n = int(input())
    dp = [1] * (n+1)
    if n > 3:
        for i in range(4, n+1):
            if t == 4:
                dp[4] = 2
            else:
                dp[i] = dp[i-3] + dp[i-2]
    print(dp[n])

[이론 스터디] 벡터와 행렬 기본 개념 :: DATA 분석 & 엔지니어링 스터디 기록 공간 (tistory.com)

백터 기본 개념은 위 포스트를 참고

Norm

• 원점에서부터의 벡터의 거리 
• L1, L2 두가지 방식으로 계산 가능
• norm의 종류에 따라 기하학적 성질이 달라진다. (L1과 L2에 따라 거리의 정의가 다르기 때문)

L1 (맨하탄 거리):

• 벡터의 각 성분의 변화량의 절대값(absolute value)를 모두 더하여 거리 계산
• 예를 들어 a = [2,3]인 2차원 벡터가 있다고 가정한다면, 빨간 선이 a의 norm이다.

• ((2,3)에 위치한 벡터의 원점에서부터 맨하탄 거리는 5가 될 것이다.

  

L2 (유클리드 거리):

• 벡터의 각 성분의 변화량의 제곱의 합에 루트를 씌워 계산한다.
• 똑같이  a = [2,3]인 2차원 벡터가 있다고 가정한다면, 빨간 선이 a의 norm이다.

• 피타고라스 정리를 사용하여 유클리드 거리를 계산할 수 있으며, ((2,3)에 위치한 벡터의 원점에서부터 유클리드 거리는 루트 13이 될 것이다.

두 벡터 사이의 거리

• L1, L2 norm으로 계산 가능
• 벡터의 뺄셈을 이용
• 그림에서처럼 2차원 공간에서는 보라색 선이 두 백터 사이의 거리가 된다.

두 백터 사이의 각도

• L2 norm으로만 계산 가능
• 제 2 코사인 법칙을 이용

• 두 벡터의 내적을 두 벡터의 L2 곱으로 나누어 thea의 코사인 값을 계산한다.
• 코사인의 역함수(아크코사인)을 계산하면 두 벡터 사이의 각도인 theta를 구할 수 있다.

정사영(orthogonal projection)

• 수직으로 빛을 비추어 투영되는 부분을 뜻한다.

• 벡터 a의 길이( |a| )에 theta의 코사인 값(cos theta)을 곱하면 a의 정사영된 길이(Proj(a))를 계산할 수 있다. 
• 벡터 b의 길이만큼 a의 정사영 길이를 조정한 값이 내적이다. (스칼라 곱 <- 벡터 길이 조정)
• 두 벡터의 유사도를 측정하는 데에 사용이 가능하다. 

벡터(vector)의 정의 

1) 숫자를 원소로 가지는 리스트 또는 배열

#리스트
x = [1,2,3]

#배열
x = np.array([1,2,3])

행 벡터:

열 벡터:

2) 공간에서의 한 점

3) 원점으로부터 상대적 위치

   0~1 사이의 값을 곱하면 방향은 그대로이고 길이만 변하며, 음수를 곱할 경우 반대 방향이 된다. (스칼라곱 = 각각의 구성 성분에 스칼라를 곱하는 것, 길이가 변하게 됨)

행렬(matrix)의 정의

1) 벡터를 원소로 가지는 2차원 배열

X = np.array([[1,2,3],
		[4,5,6],
              [7,8,9]])

2) 공간에서의 여러 점들 (데이터의 모임)

3) 벡터 공간에서 사용되는 연산자 (다른 데이터를 연결) -> 행렬곱을 통해 벡터를 다른 차원의 공간으로 보낼 수 있다. (행렬 곱셈 부분 참고)

덧셈/뺄셈

같은 모양을 가지면 계산 가능

벡터:

• 벡터는 원점으로부터 상대저 위치를 표현. 벡터의 덧셈/뺄셈은 다른 벡터로부터 상대적 위치이동을  표현

행렬:

성분곱(Hadamard product)

• 같은 모양을 가지면 계산 가능 

벡터:

행렬: 

내적 (inner product)

벡터: 

• 두 벡터의 성분곱의 합
• 두 벡터의 유사도 측정에 사용

행렬:

• i번째 행벡터와 j번째 행벡터 사이의 내적을 성분으로 가지는 행렬을 계산 
• X의 행(m)의 개수와 Y의 행(m)의 개수가 같아야 한다.
• numpy: inner(X, Y)

행렬 곱셈

• i 번째 행벡터와 j번째 열벡터 사이의 내적을 성분으로 가지는 행렬을 계산
• X의 열(n)의 개수와 Y의 행(m)의 개수가 같아야 한다.
• numpy: X @ Y 

• n x m 크기의 행렬에 m크기의 벡터를 곱할 경우 n크기의 벡터를 계산할 수 있다. 
• m은 곧 차원을 의미함으로 벡터를 m차원의 공간에서 n차원의 공간에 보낸다고 표현할 수 있다.

• 위 행렬곱에서 단지 p가 1로 바뀌었을 뿐이다.
• 행렬곱을 통해 패턴을 추출하거나 데이터를 압축할 수 있다. 
• 모든 선형변환은 행렬곱으로 계산할 수 있다.

역행렬

• 어떤 행렬의 연산을 거꾸로 되돌리는 행렬
• 1) 행(m)과 열(n)의 크기가 같고 2)행렬식(determinant)이 0이 아닌 경우에만 계산이 가능

• 그림의 예시에서 A의 크기는 2 x 2, A의 역행렬의 크기도 2 x 2로 동일
• numpy: np.linalg.inv( X )
• A 행렬과 A 역행렬을 곱할 경우 항등행렬이 계산된다.

• identity matrix(항등행렬, I) = 대각원소들이 1이면 나머지 원소들은 0인 정방행렬, 임의의 행렬 A를 항등행렬에 곱할 경우 output으로 A 행렬이 그대로 나온다.
• 넘파이로 계산할 경우 그림에서 보듯히 정확이 0은 아니지만 0에 매우 가까운 값이 표기될 수도 있다.

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)

REVIEW

• DB 캐시에 대한 배경지식이 있어야 문제 풀기가 수월하다. 
• DB 캐시는 트래픽으로 인한 서버 다운, 웹 또는 어플리케이션 서비스 이용 속도를 개선하기 위하여 임시 데이터를 캐시에 저장하여 정보가 필요할 경우 캐시에 access하는 방식이다. 
• 필요 정보가 캐시에 있을 경우를 cache hit이라고 하며, 그 반대의 경우를 cache miss라고 한다.
• 이러한 작동방식을 그대로 코드로 구현하였다. 
• 새로운 정보가 들어올 때는 cache의 가장 오른쪽에, 기존 정보가 cache에서 탈락할 때는 가장 왼쪽 것부터 탈락하게 만들어 LRU를 구현하였다. 왼쪽에서 pop을 효율적으로 수행하기 위해 deque를 사용하였다. 
• cache hit일 경우 answer에 1을 더하였다. 그리고 cache 안에 있던 해당 city를 삭제하고 새롭게 cache 오른쪽에 삽입하였다. (가장 최근에 사용된 데이터이기 때문)
• cache miss일 경우 항상 answer에 5을 더하였다. cache가 비어있을 수도 있기 때문에 에러를 방지하고자 우선 city를 추가한 후, cachesize 초과 여부에 따라 popleft( )를 수행하였다. 

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    cache = deque()
    for city in cities:
        city = city.upper()
        if city in cache:
            cache.remove(city)
            cache.append(city)
            answer += 1
        else:
            cache.append(city)
            if len(cache) > cacheSize:
                cache.popleft()
            answer += 5

    return answer

다른 사람들의 코드를 보니 굳이 cache 길이를 재며 popleft( ) 여부를 결정하는 것 대신, 이렇게 deque(maxlen=cacheSize) cache 자체에 최대 길이를 설정하여 자동적으로 cache 길이 관리하는 것이 더 나아보인다.

https://programmers.co.kr/learn/courses/30/lessons/49993/

REVIEW

• deque의 popleft()를 사용하여 pop(0)보다 더 효율적으로 앞선부터 element를 추출하였다. 
• 순서에 따라야 하는 스킬만 tree에 남게하였기 때문에 skill과 tree에서 차례대로 추출된 element는 동일하여야 한다. 동일하지 않을 경우 순서가 skill과 tree의 스킬 순서가 다르다고 해석할 수 있다. 
• popleft( )로 skill과 tree의 element를 차례대로 추출하여 비교하였다. 하지만 skill에 더 이상 남은 스킬이 없는데 tree에는 있는 경우, 또는 반대로 tree에 더 이상 남은 스킬이 없는데 skill에는 있는 경우가 있을 수 있기 때문에 skill과 tree 둘다 element가 있을 경우에만 추출-비교 작업을 수행하도록 하였다. 
• 비교 과정을 status에 기록하였다. 

from collections import deque

def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees:
        # skill에 있는 기술만 추출
        tree = deque([x for x in tree if x in skill])
        skill2 = deque(skill)

        status = True
        # skill과 tree에 element가 존재할 때만 반복하여 pop from empty list 에러 방지
        while skill2 and tree:
            if skill2.popleft() != tree.popleft():
                status = False
                break
		# element가 불일치한 적이 없고 tree에만 잔여 스킬이 있는 것이 아니라면 count
        if status and len(tree) == 0: answer += 1


    return answer

다시 코드를 리뷰하니 skill에 남은 스킬이 없는데 tree에는 스킬이 아직 남아있어서 pop from empty list 에러가 발생하지 않았을 것이라는 점을 깨닳았다.

tree에는 중복되는 스킬이 없다보니, skill에 포함된 스킬만 남아있는 tree의 길이는 항상 skill보다 짧거나 동일하기 때문이다. 

따라서 어차피 while문이 끝났을 때는 tree가 empty할 테니 len(tree) == 0을 count 조건에 지정할 필요가 없었다. 

이를 반영하여 개선한 코드는 다음과 같다:

from collections import deque

def solution(skill, skill_trees):
    answer = 0

    for tree in skill_trees:
        tree = deque([x for x in tree if x in skill])
        skill2 = deque(skill)

        status = True
        while tree:
            if skill2.popleft() != tree.popleft():
                status = False
                break

        if status: answer += 1


    return answer