꿈꾸는 개발자

시간 복잡도 - $ 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