💻 Programming (프로그래밍)/C++
-
⭐ 삽입 정렬 오름 차순으로 정렬을 한다고 할 시에, (1 -> lenght 순서로 가는 k) k번째 까지는 이미 정렬이 되어 있다고 생각을 하고, k+1 번째 값을 정렬된 곳에 삽입해주려는 정렬 방식입니다. k번째 까지는 이미 정렬이 되어 있기에 큰 값부터 비교해가며 딱 알맞은 곳에 삽입해줘야 합니다. #include using namespace std; void insertSort(int nums[], int length) { for (int i = 1; i = 0 && tmp < nums[Idx]) { nums[Idx + 1] = nums[Idx]; Idx--; } nums[Idx +..
[C++][구현] 삽입정렬 (Insertion Sort)⭐ 삽입 정렬 오름 차순으로 정렬을 한다고 할 시에, (1 -> lenght 순서로 가는 k) k번째 까지는 이미 정렬이 되어 있다고 생각을 하고, k+1 번째 값을 정렬된 곳에 삽입해주려는 정렬 방식입니다. k번째 까지는 이미 정렬이 되어 있기에 큰 값부터 비교해가며 딱 알맞은 곳에 삽입해줘야 합니다. #include using namespace std; void insertSort(int nums[], int length) { for (int i = 1; i = 0 && tmp < nums[Idx]) { nums[Idx + 1] = nums[Idx]; Idx--; } nums[Idx +..
2022.05.09 -
⭐ Sequence, Selection Sort 오름차순 정렬을 한다고 하였을 때, 가장 작은 수를 찾아서 교환해주는 정렬입니다. 첫번째, for문은 정렬 할 자리수 k를 정해주고 (오름차순이면 k가 0부터 length까지) 그 다음 두번째 for문 부터 k + 1 부터 length까지 nums[k]와 비교를 해가며 작으면 스왑해줍니다. #include using namespace std; // O(n^2) unstable void sequenceSort(int nums[], int length) { for (int i = 0; i nums[j]) { // Compare 조건 //..
[C++][구현] 순차,선택 정렬 (Sequence ,Selection Sort)⭐ Sequence, Selection Sort 오름차순 정렬을 한다고 하였을 때, 가장 작은 수를 찾아서 교환해주는 정렬입니다. 첫번째, for문은 정렬 할 자리수 k를 정해주고 (오름차순이면 k가 0부터 length까지) 그 다음 두번째 for문 부터 k + 1 부터 length까지 nums[k]와 비교를 해가며 작으면 스왑해줍니다. #include using namespace std; // O(n^2) unstable void sequenceSort(int nums[], int length) { for (int i = 0; i nums[j]) { // Compare 조건 //..
2022.05.09 -
이미 정렬된 Array1과, Array2가 있습니다. Array1에는 Array2이 들어갈 숫자만큼 0이란 숫자로 채워져 있는 공간이 있습니다. Array1과, Array2를 서로 비교해가며, Array1에 두 배열을 합친 값이 sorted된 배열을 만드는 문제입니다. Array3이란 따른 배열을 추가하여 처음부터 비교해가면서 구하는 방법 이외로 Array1에 그대로 넣는다는 점이 흥미롭습니다. void mergeSorted(int nums1[], int n, int nums2[], int m) { int num1Idx = n - 1; int num2Idx = m - 1; int wIdx = n + m - 1; if (num2Idx < 0) return; while (0
[C++][구현] Merge Sorted (배열 문제)이미 정렬된 Array1과, Array2가 있습니다. Array1에는 Array2이 들어갈 숫자만큼 0이란 숫자로 채워져 있는 공간이 있습니다. Array1과, Array2를 서로 비교해가며, Array1에 두 배열을 합친 값이 sorted된 배열을 만드는 문제입니다. Array3이란 따른 배열을 추가하여 처음부터 비교해가면서 구하는 방법 이외로 Array1에 그대로 넣는다는 점이 흥미롭습니다. void mergeSorted(int nums1[], int n, int nums2[], int m) { int num1Idx = n - 1; int num2Idx = m - 1; int wIdx = n + m - 1; if (num2Idx < 0) return; while (0
2022.04.26 -
배열안에는 {0, 1, 2}인 요소만 들어갈 수 있습니다. 이 배열을 O(n) 시간복잡도로 정렬을 하는 문제입니다. counting // 1. Counting O(n) void SortColors(int nums[], int length) { int zero(0), one(0), two(0); for (int i = 0; i < length; i++) { switch (nums[i]) { case 0: zero++; break; case 1: one++; break; case 2: two++; break; } } for (int i = 0; i < length; i++) { if (i < zero) nums[i] = 0; else if (i < zero + one) nums[i] = 1; else num..
[C++][구현] Sort Colors (배열 파티셔닝 문제)배열안에는 {0, 1, 2}인 요소만 들어갈 수 있습니다. 이 배열을 O(n) 시간복잡도로 정렬을 하는 문제입니다. counting // 1. Counting O(n) void SortColors(int nums[], int length) { int zero(0), one(0), two(0); for (int i = 0; i < length; i++) { switch (nums[i]) { case 0: zero++; break; case 1: one++; break; case 2: two++; break; } } for (int i = 0; i < length; i++) { if (i < zero) nums[i] = 0; else if (i < zero + one) nums[i] = 1; else num..
2022.04.26 -
시간복잡도에 대해서 생각해 볼 수 있는 좋은 문제였습니다. 배열에서 어느 한 지점(Pivot)을 기준으로 왼쪽의 배열의 합, 오른쪽의 배열의 합이 같으면 그 지점의 pivot index를 알아내는 문제입니다. 일단 기본적인 brutal 적인 생각으로는 기준점(pivot)을 정하고, 왼쪽의 합, 오른쪽의 합을 구한다면 시간 복잡도가 O(N^2)가 되어버립니다. 더 나은 차선책의 생각을 해본다면, 전체 배열 값을 더하고(O(N)), 기준점을 정하면서, 왼쪽의 배열값은 = 왼쪽 배열값 + 이전피봇값 오른쪽의 배열값은 = 전체배열값 - 이전피봇값 이런식으로 흘러간다면 O(N)의 시간복잡도를 구할 수 있습니다. 따라서, 전체배열의 합 O(N) + 기준점을 정하여, 좌우 배열의 합값을 비교하는 식 O(N) = O(..
[C++][구현] findPivotIndex (배열 슬라이딩 문제)시간복잡도에 대해서 생각해 볼 수 있는 좋은 문제였습니다. 배열에서 어느 한 지점(Pivot)을 기준으로 왼쪽의 배열의 합, 오른쪽의 배열의 합이 같으면 그 지점의 pivot index를 알아내는 문제입니다. 일단 기본적인 brutal 적인 생각으로는 기준점(pivot)을 정하고, 왼쪽의 합, 오른쪽의 합을 구한다면 시간 복잡도가 O(N^2)가 되어버립니다. 더 나은 차선책의 생각을 해본다면, 전체 배열 값을 더하고(O(N)), 기준점을 정하면서, 왼쪽의 배열값은 = 왼쪽 배열값 + 이전피봇값 오른쪽의 배열값은 = 전체배열값 - 이전피봇값 이런식으로 흘러간다면 O(N)의 시간복잡도를 구할 수 있습니다. 따라서, 전체배열의 합 O(N) + 기준점을 정하여, 좌우 배열의 합값을 비교하는 식 O(N) = O(..
2022.04.25 -
특정 숫자를 배열의 시작 혹은 끝으로 옮기는 문제입니다. 이때, 시간복잡도는 O(N) 시간을 사용하는 것을 목표로 합니다. void moveZeros(int nums[], int size) { int wIdx = 0; for (int idx = 0; idx < size; idx++) { if (nums[idx] != 0) { swap(nums[wIdx], nums[idx]); wIdx++; } } } moveZeors() 함수의 핵심은 wIdx, Idx를 구분을 잘 하는게 핵심인 듯 합니다.
[C++][구현] moveZeros (배열 문제)특정 숫자를 배열의 시작 혹은 끝으로 옮기는 문제입니다. 이때, 시간복잡도는 O(N) 시간을 사용하는 것을 목표로 합니다. void moveZeros(int nums[], int size) { int wIdx = 0; for (int idx = 0; idx < size; idx++) { if (nums[idx] != 0) { swap(nums[wIdx], nums[idx]); wIdx++; } } } moveZeors() 함수의 핵심은 wIdx, Idx를 구분을 잘 하는게 핵심인 듯 합니다.
2022.04.24 -
Vector란 컨테이너는 자동으로 사이즈를 바꿔주는 배열입니다. size 라는 실제로 사용하고 있는 사이즈값과 capacity 라는 size가 초과되려고 할 때, 여분의 공간값이 주어집니다. 즉 내가 사용하려는 벡터의 index == size이 되었을 때, resize()함수를 통하여 capacity를 공간을 늘려주고 실제 사용할 수 있는 메모리값이 동적으로 할당됩니다. 이를 통하여 저만의 size() capactiy() resize() push_back() operator[] 기능만 간단하게 가지도록 코드를 짜봅니다. #include using namespace std; template class VECTOR { private: T* mPtr; int mSize; int mCapacity; int mI..
[C++][구현] VectorVector란 컨테이너는 자동으로 사이즈를 바꿔주는 배열입니다. size 라는 실제로 사용하고 있는 사이즈값과 capacity 라는 size가 초과되려고 할 때, 여분의 공간값이 주어집니다. 즉 내가 사용하려는 벡터의 index == size이 되었을 때, resize()함수를 통하여 capacity를 공간을 늘려주고 실제 사용할 수 있는 메모리값이 동적으로 할당됩니다. 이를 통하여 저만의 size() capactiy() resize() push_back() operator[] 기능만 간단하게 가지도록 코드를 짜봅니다. #include using namespace std; template class VECTOR { private: T* mPtr; int mSize; int mCapacity; int mI..
2022.04.23 -
검색 할 때 쓰는 알고리즘으로 O(log n) 만큼의 시간 복잡도를 가지고 있습니다. 또한 사전 작업으로 정렬이 미리 돼어있어야지 사용할 수 있습니다. #include using namespace std; int search(int nums[], int length, int target) { int left = 0; int right = length -1; while (left target else { // nums[pivot] > target right = pivot - 1; } } return -1; } 주요 알고리즘은, left, right, pivot을 통하여, 지속적으로 갱신을 해주며 값을 찾아내는 알고리즘입니다.
[C++][구현] Binary Search검색 할 때 쓰는 알고리즘으로 O(log n) 만큼의 시간 복잡도를 가지고 있습니다. 또한 사전 작업으로 정렬이 미리 돼어있어야지 사용할 수 있습니다. #include using namespace std; int search(int nums[], int length, int target) { int left = 0; int right = length -1; while (left target else { // nums[pivot] > target right = pivot - 1; } } return -1; } 주요 알고리즘은, left, right, pivot을 통하여, 지속적으로 갱신을 해주며 값을 찾아내는 알고리즘입니다.
2022.04.22