[C++] string to int / vector iterator / merge sort

stoi / stof / stol / stod 함수

프로그래머스 - 동영상 재생기 문제를 풀며 string 을 int 로 변환하는 C++ 라이브러리 함수에 대해 찾아보았다.

[C++] stoi, stof, stol, stod 함수에 대해서 (string to int)

 

* <string> 라이브러리에 포함

* 지정한 타입(int, float, long, double 등)이 아닌 문자를 마주치면 변환 끝남. 그래서 문자로 시작하는 스트링의 경우 에러.

 

vector iterator

C++ 에서 벡터를 이터레이트하는 방법에 대해서도 강의를 통해 다시 한 번 복습하였다.

위의 문제로 예를 들면 아래와 같이 commands 벡터를 iterate 한다.

for (vector<string>::iterator com = commands.begin(); com != commands.end(); ++com) {
	if (*com == "prev") {

	}
}

당연한 이야기지만 iterator 는 주소를 가리키고 있으므로 *로 dereference 해 값에 접근한다.

 

아래에 조금 더 중요 내용 위주로 정리했다.

241224 vector, map / sort, find / reverse iterator and base iterator

 

 

merge sort algorithm

정렬 알고리즘 ... 학부 때 배웠던 것이 정말 기억이 하나도 안난다 ㅋ 하긴 벌써 10년 전이다...오엠쥐~

우선 정렬 알고리즘이 여러 가지 있는데 이것들의 복잡도를 찾아보았다.

(참고: https://www.enjoyalgorithms.com/blog/comparison-of-sorting-algorithms)

이 중에서 다음과 같은 이유로 merge sort 를 골라 공부했다.

- bubble / selection / insertion sort 는 정렬이 전혀 안 되어있는 랜덤한 케이스에서 n^2 로 오래 걸림

- heap sort 는 heap 데이터 스트럭쳐를 이해해야 해서... 나중에 찾아보기로...

- counting / radix sort는 작은 범위의 정수를 정렬, bucket sort 는 [0, 1) 범위에 균등하게 분포한 랜덤 요소를 정렬할 때 쓰인다고 한다. 

- 남은 것은 quick sort 와 merge sort 인데, 이 둘을 비교해보면

>> Merge sort is stable : quick sort 의 경우 A[i] == A[j] 인 경우 인덱스 순서에 관계 없이 배치하지만 merge sort 의 경우 i < j 인 경우 A[i] 가 A[j] 보다 먼저 배치된다. 

>> Quick sort is in-place : merge sort 는 배열을 복사해가며 정렬하기 때문에 메모리 공간을 요한다.

>> Quick sort runs in O(n^2) if the data is (nearly) sorted : 케이스에 관계 없이 O(n log n) 시간 복잡도를 보장해야 할 때 merge sort 또는 heap sort 를 보통 사용한다고 한다.

 

아래 유튜브를 보며 공부했다.

 

1. 배열을 절반으로, 절반을 절반으로 ... 나눈다. (재귀 recursion)

2. 언제까지? (base case) 배열 사이즈가 1이 될 때까지

- 위의 내용을 아래의 C++ 코드로 작성해 보았다. (영상은 Java 언어를 사용한다.)

void mergeSort(int arr[], int length) {
    if (length <= 1) return; // base case

    // divide the array into two halves
    int mid = length / 2;
    int leftSize = mid;
    int rightSize = length - mid;
    int* leftArray = new int[leftSize];
    int* rightArray = new int[rightSize];
    
    int j = 0; // index for the right array
    
    // for loop iterates the array
    for (int i = 0; i < length; i++) {
    	// left of middle --> copy arr[i] into left array
        if (i < mid) {
        	leftArray[i] = arr[i];
        }
        // right of middle --> copy arr[i] into right array
        else { 
        	rightArray[j] = arr[i];
            j++;
        }
    }
    
    // recursion on left and right arrays
    mergeSort(leftArray, leftSize);
    mergeSort(rightArray, rightSize);
    
    /*
    TO-DO: merge left and right arrays by comparing and sorting the elements
    */
    merge(leftArray, rightArray, leftSize, rightSize, arr);
    
    // delete the created arrays
    delete[] leftArray;
    delete[] rightArray;
}

 

3. 왼쪽 절반 배열과 오른쪽 절반 배열의 요소들을 비교해 순서에 맞게 원래 배열에 넣는다.

- 이렇게 작동할 merge 함수를 다음과 같이 구현했다.

void merge(int leftArray[], int rightArray[], int leftSize, int rightSize, int arr[]) {
	// left, right, array(copy destination) indices
    int left = 0, right = 0, i = 0;
    
    // compare elements in the left and right arrays and insert the smaller into arr[]
    while (left < leftSize && right < rightSize) {
    	if (leftArray[left] <= rightArray[right]) {
        	arr[i] = leftArray[left];
        	left++;
        }
        else {
        	arr[i] = rightArray[right];
            right++;
        }
        i++;
    }
    
    // copy the remaining elements into arr[]
    while (left < leftSize) {
    	arr[i] = leftArray[left];
        i++;
        left++;
    }
    
    while (right < rightSize) {
    	arr[i] = rightArray[right];
        i++;
        right++;
    }
}