꿈꾸는 개발자

버블 정렬 - 데이터의 인접 요소끼리 비교하고, 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; // 값에 해당하는 인덱스..

코딩 테스트를 공부할 때 미리 자신만의 스니펫을 구성해두는 것을 추천한다. 간단한 코딩테스트의 경우 쉽게 문제를 풀 수 있지만, 난이도가 높은 문제일수록 쉬운 알고리즘들을 미리 스니펫을 구성해둔 상태로 진행하는 것이 시간을 단축 시킬 수 있다. 이번 포스팅에는 특정 구간에 대한 값의 합을 구하고 싶을 때, 사용되는 구간 합 스니펫을 구현해보았다. 시간 복잡도는 $ 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_..