꿈꾸는 개발자

시간 복잡도 - $ O(n\log(n)) $ 퀵 정렬 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미칠 수 있음.(최악의 경우 $ O(n^{2}) $) 피벗(pivot)을 설정해 부분 배열로 나누고 재귀적으로 정렬해가는 과정 #include using namespace std; void quick_sort(vector &A, int S, int E, int K); int partition(vector &A, int S, int E); void swap(vector &A, int S, int E); void quick_sort(vector &A, int start, int end, int K) { i..

버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 장점 : 구현이 쉽다. 단점 : 상대적으로 다른 정렬 알고리즘보다 시간이 오래 걸린다. 시간 복잡도 - $ O(n^{2}) $ 버블 정렬 코드 스니펫 #include #include using namespace std; int main() { int N = 1000; vector A(N, 0); bool change = false; for (int i = 1; i > N; vector A(N, {0, 0}); // 데이터 값, 각 배열의 인덱스를 저장 for (int i = 0; i > A.at(i).first; // 값 저장 A.at(i).second = i; // 값에 해당하는 인덱스..

시간 제한 : 2초 메모리 제한 : 256MB 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 문제 해설 두 개의 합 혹은 다른 두 수라는 내용이 문제에서 나올 경우 2 포인터 알고리즘이라고 생각하는 것이 중요! 해당 문제에서 시간 복잡도의 경우 최소 $ O(n\log(n)) $ 이어야 하기 때문에 정..

코딩 테스트를 공부할 때 미리 자신만의 스니펫을 구성해두는 것을 추천한다. 간단한 코딩테스트의 경우 쉽게 문제를 풀 수 있지만, 난이도가 높은 문제일수록 쉬운 알고리즘들을 미리 스니펫을 구성해둔 상태로 진행하는 것이 시간을 단축 시킬 수 있다. 이번 포스팅에는 특정 구간에 대한 값의 합을 구하고 싶을 때, 사용되는 구간 합 스니펫을 구현해보았다. 시간 복잡도는 $ O(n) $ 이다. 배열 A 가 존재할 때, 배열 A의 인덱스까지의 누적 합을 배열 S 로 표현한 것은 다음과 같다. S[i] = S[i-1] + A[i] #include #include int main() { vector A; vector S; A.push_back(1); A.push_back(2); A.push_back(3); A.push_..

C++ 기준에서 1억번의 연산 = 약 1초로 볼 수 있다. 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것 코딩 테스트에서는 빅-오 표기법($ O(n) $)을 기준으로 수행 시간을 계산하는 것이 좋다. 예를 들어보자. #include #include #include using namespace std; int main() { int findNumber; int N = 1000000; srand(time(NULL)); findNumber = rand() % 1000000; for (int i = 0; i < N; i++) { if (i == findNumber) { cout

OpenCV 라이브러리에는 여러 모듈들이 들어있다. 하지만 처음 시작하는 사람의 입장에선 모듈을 사용하고 싶지만 어떤 헤더파일에 존재하는지를 몰라 헤매는 경우가 많다. 이를 위해 책에서 나온 내용을 토대로 정리하려고 한다. 주요 모듈 리스트 calib3d core dnn features2d flann highgui imgcodecs imgproc ml objdetect photo stitching video videoio 이외에도 여러 모듈들이 있지만, 위 모듈들만 간단한 설명 및 해당하는 헤더 파일을 나열하도록 하겠습니다. calib3d #include camera calibration과 3D reconstruction을 위한 모듈 https://docs.opencv.org/3.4/d2/d28/cali..

작년 말부터 갑자기 연구실 과제에 대한 내용이 급격하게 많아지면서 너무 바쁜 일상을 보냈던 것 같다. 이번에 새해도 되었고(너무 많이 지났지만..) 새 마음으로 시작하고자 CMake와 OpenCV 및 SLAM에서 많이 사용되는 라이브러리들을 하나하나씩 익혀보면서 공부해나가는 1년을 보내려고 한다. 정말 기초부터 차근차근히 공부해보고 있다. 또한, C++ 언어에 대한 기량이 부족하기 때문에 같이 공부하면서 진행하려고 한다. https://github.com/ans2568/SLAM_Tutorial GitHub - ans2568/SLAM_Tutorial: 혼자서 Cmake 프로젝트를 관리하기 위해 처음부터 배워서 기록하는 문서 혼자서 Cmake 프로젝트를 관리하기 위해 처음부터 배워서 기록하는 문서. Cont..