일반적인 dp에서 진화한 형태이다. import numpy as npimport sysdef multiply_matrix(A, B, mod): A = np.array(A) B = np.array(B) result = np.dot(A, B) % mod return result.tolist()def power_matrix(A, p, mod): #빠른 거듭제곱 알고리즘 if p == 1: return A if p % 2: #n이 홀수라면, 기본 행렬을 n-1번 거듭제곱한 후, 그 결과에 기본 행렬을 한 번 더 곱한다. return multiply_matrix(A, power_matrix(A, p-1, mod), mod) half = power_m..
기본적으로 투 포인터는 대부분 구간의 길이가 유동적으로 변한다.그렇기에 최초로 최소가 되는 부분 문자열을 찾는다면 슬라이딩 윈도우 알고리즘이 더 효율적이다. [1, 2, 3], 4, 5, 6, 71, [2, 3, 4], 5, 6, 71, 2, [3, 4, 5], 6, 71, 2, 3, [4, 5, 6], 71, 2, 3, 4, [5, 6, 7] 최소한의 계산으로 다음 배열의 합을 구한다.그러려면 1+2+3과 2+3+4를 비교했을 때, 1은 빠지고 4가 들어오면 된다. import sysn= int(sys.stdin.readline())b = [int(i) for i in sys.stdin.readline().rstrip().split()]def max_bars_to_leave(n, bars): b..
[그래프-트리] RRT를 이용한 Sampling Methods for Motion Planning
https://www.youtube.com/watch?v=Ao7p_xiUu4s&t=4s 모션 플래너는 Rapidly Exploring Random Tree(RRT)를 기반으로 한다. 부분적으로 형성된 검색 트리 T부터 시작 x_start는 초기 상태이고, X는 상태 공간이며, X_goal의 모든 상태는 acceptable final state(로봇이 성공적으로 목표를 달성했다고 간주되는 상태 )이다. RRT planner는 x_samp라는 상태를 랜덤으로 정한다. 그리고 트리 안에서 가장 가까운 노드 x_nearest에서 collision-free motion을 하면서 x_new로 선을 긋는다. 이는 x_samp에는 닿지 않지만, 적어도 x_samp에 최단거리로 가는 길목을 차지한다. 최종적으로는 x_s..
[그래프-트리] A-star 알고리즘
https://www.youtube.com/watch?v=QpOuyqd6nnc&t=4s https://www.youtube.com/watch?v=ZI800-2jv38 Graphs and Trees 로봇의 C 공간은 연속적인 공간이지만, 모션 계획에서는 일반적으로 어떤 방식으로든 분리/범주화(discretize) 된다. 미로 속에 모바일 로봇이 있다고 하자. 몇 가지 갈림길에 우리는 점을 찍을 수 있고, 그 경로에서 선을 그려서 로봇이 움직일 수 있는 경로와, 그 여유 공간을 나타낼 수 있다. 그러면 그렇게 이어진 선은 graph로 표현할 수 있다. 이 그래프는 노드들과 간선의 세트로 구성된다. 예를 들어, 그냥 a~e의 노드가 있고, 각각 그냥 선으로만 연결되어 있다고 하자. 비가중 무방향 그래프이다. ..
LIS 문제는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다. 예를 들어, 수열 [10, 20, 30, 5, 15, 25, 35, 40]이 주어졌을 때, 최장 증가 부분 수열은 [10, 20, 30, 35, 40]이며 길이는 5입니다. 상어의 크기를 수열로 보면, 연속적으로 먹히는 관계를 가진 상어들의 최대 마리 수는 그 수열에서 최장 증가 부분 수열의 길이와 같습니다. 다만, 주어진 문제에서는 순서가 중요하므로 단순히 LIS 알고리즘을 적용하기는 어렵습니다. LIS 문제와 관련된 유명한 다른 문제들로는 다음과 같은 것들이 있습니다: 가장 긴 공통 부분 수열(Longest Common Subsequence, LCS) 문제 가장 큰 증가 부분 수열의 합(Maximum Sum ..
Early return 함수를 정의했을 때, 함수 끝까지 도달하기 전에 반환한다. def k(a,b): v = a/b if v > 200: #조건에 해당한다면 return v #조기 반환한다. return v 단점 : 함수의 반환이 여러 곳으로 흩어지게 되어 함수의 복잡도를 높이고 가독성을 떨어뜨릴 수 있는 가능성이 존재한다. Gaurd clauses 본문의 로직을 진행하기 전에 예외처리 코드들을 추가 조건문으로 검사하고 함수 종료 def k(a,b): v = a/b if v > 200: #조건에 해당한다면 return None #종료한다. if v ==list: #조건에 해당한다면 return None #종료한다. return v 예외를 줄일 수 있으므로 좋다. Composite method 2개 이상..