본문 바로가기

분류 전체보기

 (158)
c++ Rabin-Kaap 알고리즘을 활용한 leetcode 796번 Rotate String (O(N)) RotateString 문제는 abcde 같은 문자열을 cdeab와 같이 표현 할 수 있다. 두 문자가 움직여 졌을 때 같은 문자열로 변환될 수 있는지 구하는 것이다. string 문제는 O(N)으로 풀어야 한다. 이중 for loop은 지양하도록 하자. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include #include // C++ Rabin-Kaap 알고리즘으로 쉽게 구현 using namespace std; class Solution { public: bool rotateString (string s, strin..
c++ 문자열 검색 O(N)으로 하기 with Rabin-Karp 알고리즘 문자열이 만약에 "dabcabkabcabd"라고 하자. 이 문자열 안에 "abcabd"라는 문자가 있는지 확인해보고자 한다. 만약 brute force로 검색한다면 복잡도는 O(N * M)이 될 것이다. 이것을 O(N + M)~~ O(N)으로 할 수가 있다. 사실 문자열 검색의 복잡도는 O(N)으로 끝내야 한다. 만약 두 문자열이 같다면 그 해쉬 값도 같다고 볼 수 있다. 슬라이딩 윈도우를 하면서, hash값만 비교하고(복잡도 O(N)) hash 값이 일치한다면 일치하는 hash값끼리만 문자열을 일일히 비교해보면 된다(복잡도 O(M)) 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33..
c++ O(N)으로 2D matrix 원소 찾기 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include #include std::vector findElementInArray(std::vector& nums, int target) { int size = (int)nums.size(); int pivot_x = size-1; int pivot_y = 0; std::vector array; while ((pivot_x >= 0) && (pivot_y
c++ 배열 image in-place로 rotate 하기 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 #include #include int xsize = 4; int ysize = 4; typedef struct { int x; int y; } coordXY; coordXY getcoordXY(coordXY BeforeXY) { coordXY newcoordXY; newcoordX..
c++ leetcode array find duplicate by O(N) 배열 { 1,2,3,3,5,} 에서 중복을 찾는 것은 쉽다. 그렇지만 O(N)으로 중복을 찾으려면? 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include #include #include // Find Duplicates by O(N) int FindDuplicates(std::vector& nums) { int k; for (int i = 0; i = 0) nums[k-1] = -nums[k-1]; else return nums[i]; } return -1; } int main() { std::vector nums = { 1,2,3,3,5,}; int ans =..
c++ leetcode 배열 Shorted Unsorted Continuous Subarray 이 문제는 만약 [2,6,4,8,10,9,15,22,3]과 같은 벡터가 있다면 정렬이 되기 위해 고쳐야 할 원소의 갯수를 구하는 문제이다. 정렬이 된다면 [2,3,4,6,8,9,10,15,22]일 것이다. 따라서 고쳐야 할 배열의 원소들은 [6,4,8,10,9,15,22,3]이고 그렇다면 이 원소의 갯수는 8이다. O(nLogN)의 복잡도로 푸는 것은 쉽다. 오른쪽 배열은 퀵 소트로 정렬하였다. [2,6,4,8,10,9,15,22,3] = [2,3,4,6,8,9,10,15,22] 다른 부분의 처음과 끝의 인덱스만 구하면 되기 때문이다. 하지만 O(N)으로 푸는 것은 꽤나 까다롭다. O(nLogn) case와 O(N)의 케이스를 적어 놓겠다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13..
캐글 SIIM-FISABIO-RSNA COVID-19 Detection -심화 전략 조사 결과 efficientNet-v2, Mask를 활용한 AuxLoss 사용이 주요한 전략인 듯 싶다. *mask 전략 32*32 mask *augmentation 전략 for fn in np.random.choice([ lambda image, mask : do_random_scale(image, mas, mag=0.2) -> random crop lambda image, mask : do_random_stretch_y(image, mask, mag=0.2) lambda image, mask : do_random_stretch_x(image, mask, mag=0.2) lambda image, mask : do_random_shift(image,mask,mag=int(0.2*image_size)) l..
c++ leet code medium merge_interval 구현 Merge interval은 {2,5}, {8,15}, {1,3}, {10,13}, {11,17} 과 같은 interval을 겹치는 구간은 병합하고, 분리된 부분은 분리하는 방법이다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #include #include #include // merge_intervals std::vector merge_intervals(std::vector& intervals) { std::sort(in..

티스토리툴바