LIS길이를 이분탐색으로 구해보자(python)
가장 긴 증가하는 부분수열(LIS)의 길이를 이분탐색을 이용해 구해보자 먼저 가장 긴 증가하는 부분 수열이 뭔지 이해해보자 수열: 숫자들의 나열 ex) [5,3,8,2] 부분수열: 수열안에서 몇몇 숫자들을 골라서 만든 새로운 수열 ex) [5,8,3,2] => [5,8,2] 따라서 수열 [10, 20, 10, 30, 20, 50]이 있을때 따라서 가장 긴 증가하는 부분 수열은 [10, 20, 10, 30, 20, 50]이고 길이는 4이다 이분탐색을 이용한 풀이 주어진 수열의 각 원소를 순회하면서 이분탐색을 적용해나간다 따라서 시간복잡도는 O(nlogn) 이된다 세부적인 이진탐색 과정은 아래와 같다 현재 원소를 이진 탐색을 통해 LIS 배열에 삽입할 위치를 찾는다 (LIS배열은 항상 정렬된 상태를 유지한다..
2023. 6. 6.
합성곱 연산(Convolution operation) 방법
입력값이 커널과의 연산과정을 거쳐 출력값이 된다 커널은 필터라고도 불린다n*m크기의 행렬로 n*m크기의 겹쳐지는 부분의 원소값을 곱한뒤 모두 더한값을 출력으로 갖는다input_=np.array([1,2,3,2,1,0,3,0,1])kernel=np.array([1,0,1,1,0,1,0,1,0])sum(input_*kernel)이미지의 가장 왼쪽 위부터 가장 오른쪽 순차적으로 위과정을 반복한후 마지막으로 편향(bias)를 더해 최종적인 출력(feature map)을 만든다또한 위의 예제에서는 커널의 이동범위가 한칸이었지만 이또한 사용자가 정할수있으며 이러한 이동범위를 stride라고 한다 RGB 3채널의 이미지 한장에서 최종적인 feature map을 얻는 과정은 다음과 같다(보통 rgb값을 permute를..
2023. 2. 21.
