알고리즘 교안 학습 - 1 [Split, unique, lower_bound, Upper_bound,accumulate,max_element,min_element]

코딩테스트에 사용하기 위해 공부하고 있는 언어는 C++ 이다. 

제대로 처음 했을때 공부했던 언어가 다이렉트X를 다루기 위한 C++ 이기도 했고, 더 성장하기 위해선 Unity 도 좋지만 Unreal 도 충분히 매력적인 엔진이라고 생각하여 선택했다.

 

[Split]

-> C++ 에는 다른 많은 함수들이 제공된다고 들었으나, Split에 관해서는 커스텀으로 만들어야 한다는 강의 내용이 있어서 작성해보았다. 

초안 작성 후 버그나는 부분들은 참고했으니 거의 교안과 동일하다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

 class Functions
{
    public:	vector<string> Split(string s, string delimeter) {
        vector<string> ret;
        long long index = 0;
        while ((index = s.find(delimeter)) != string::npos)
        {
            string v = s.substr(0, index);
            ret.push_back(v);
            s.erase(0, index + delimeter.length());
        }
        ret.push_back(s);
        return ret;
    }
};

void main()
{
    string s = "ABCDEFG";
    Functions* f = new Functions();
    auto v = f->Split(s, "E");

    for (auto vv : v)
        cout << vv << '\n';
}

 

[unique]

-> 교안을 공부하면서 새로 알게된 함수이다. unique();

기능은 배열의 범위 안에 있는 값 중 중복되는 값을 뒤로 밀고 중복되지 않도록 앞으로 가져오는 것이다.

예를 들어 vector<int> v = {1,2,4,6,4,2,5,1,3,4}; 라고 할때, unique(a,a+10); 을 수행하면 { 1,2,3,4,5,6,4,4,5,6 } 이 나온다.

 

단, 여기서 주의할 점은 위에 나열된 vector 그대로 unique 를 돌리면 기능이 정상 작동하지않으므로, 반드시 sort 를 사용한 후에 unique 를 사용해야 한다. 

 

앞에서부터 값으로 비교하기때문에, 뒤죽박죽인 배열로 수행하면 당연히 계산식에 오류가 날 수 있다.

같이 쓰기에 좋은 함수는 sort(), erase() 이다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <string>

using namespace std;
vector<int> v = { 1,2,4,6,4,2,5,1,3,4 };

void main()
{
	sort(v.begin(), v.end());
	// 반드시 정렬 선 수행
	auto it = unique(v.begin(),v.end());
	auto index = it - v.begin();

	cout << index << '\n'; 
	// 중복 정리한 다음 인덱스 반환한다.

	for (auto value : v)
		cout << value << " ";

	return;
}

 

[lower_bound , upper_bound]

-> 새롭게 알게된 배열 관련 함수이다. lower_bound(); upper_bound();

정렬된 배열 내에서 내가 원하는 값의 시작지점, 내가 원하는 값을 벗어나는 초과지점을 인덱스로 알려준다.

 

만약, 1 1 1 2 2 2 3 3 3 3 이 있다고 가정하고 내가 2가 시작되는 인덱스와 초과되는 인덱스를 알고싶은 케이스라면   

lower_bound(begin(),end(),value => 2); 

=> 인덱스 3 반환

 

upper_bound(begin(),end(),value => 2); 

=> 인덱스 6 반환 => upper_bound 는 값의 초과지점을 인덱스로 넘기기 때문에 끝 인덱스 5가 아닌 그다음 인덱스를 반환한다.

 

응용한다면 여러 방법으로 사용할 수 있다.

1. 내가 찾는 값의 갯수가 몇개인지? 

-> upper_bound - lower_bound 로 (초과인덱스 - 시작인덱스) 를 수행하면 갯수에 대한 값이 나온다. 뭔가 블록 기준으로 감소를 하는 것으로 보니 부분쿼리 느낌이다.

 

2. 요소 출력 

-> 이터레이터를 반환하기때문에 포인터 값 참조를 수행하면 요소 값을 볼 수 있다.

 

여기서 만약, 내가 찾는 요소가 없다면 무엇을 반환할까?

그것또한, 응용 3번으로 넣어서 코드 작성해보았다.

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <string>

using namespace std;
vector<int> v = { 1,3,2,2,1,1,3,3,3,2,5,5};

void main()
{
	sort(v.begin(), v.end());
	// 반드시 정렬 선 수행

	cout << lower_bound(v.begin(), v.end(), 2) - v.begin() << "\n";
	// 3
	cout << upper_bound(v.begin(), v.end(), 2) - v.begin() << "\n";
	// 6

	cout << upper_bound(v.begin(), v.end(), 2) - lower_bound(v.begin(), v.end(), 2) << "\n";
	// 응용1. 값 :: 3

	cout << *lower_bound(v.begin(), v.end(), 2) << "\n";
	// 응용2-1. 값 :: 2

	cout << *lower_bound(v.begin(), v.end(), 3) << "\n";
	// 응용2-2. 값 :: 3

	cout << lower_bound(v.begin(), v.end(), 4) - v.begin() << "\n";
	// 응용3-1. 값 :: 10(A)
	// 최대값인 5보다 찾는 값인 4가 더 작다. 
	// 아래와 같이 있다고 했을때, A 라고 적힌 10 인덱스가 값으로 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B 

	cout << upper_bound(v.begin(), v.end(), 4) - v.begin() << "\n";
	// 응용3-2. 값 :: 10(A)
	// 최대값인 5보다 찾는 값인 4가 더 작다. 
	// 아래와 같이 있다고 했을때, A 라고 적힌 10 인덱스가 값으로 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B 

	cout << lower_bound(v.begin(), v.end(), 9) - v.begin() << "\n";
	// 응용3-3. 값 :: 13(C)
	// 최대값인 5보다 찾는 값인 8이 더 크다.
	// 아래와 같이 있다고 했을때, C 라고 적힌 13 인덱스가 값으로 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B C

	// => 13이라 생각되는데 12로 나와서 답을 찾아봐야한다.  ( 이 값은 신뢰하지 말 것 )

	cout << upper_bound(v.begin(), v.end(), 9) - v.begin() << "\n";
	// 응용3-4. 값 :: 13(C)
	// 최대값인 5보다 찾는 값인 8이 더 크다.
	// 아래와 같이 있다고 했을때, C 라고 적힌 13 인덱스가 값으로 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B C

	// => 13이라 생각되는데 12로 나와서 답을 찾아봐야한다.  ( 이 값은 신뢰하지 말 것 )

	cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << "\n";
	// 응용3-5. 값 :: 0
	// 3-1 와 같이 찾는 값이 존재하는 값보다 작기때문에 근방지점인 0 인덱스가 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B C

	cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << "\n";
	// 응용3-6. 값 :: 0
	// 3-1 와 같이 찾는 값이 존재하는 값보다 작기때문에 근방지점인 0 인덱스가 나온다.
	// 1 1 1 2 2 2 3 3 3 3 5 5 
	// 0 1 2 3 4 5 6 7 8 9 A B C

	return;
}

 

[accumulate] - include<numeric>

배열의 합을 계산해주는 함수.

vector<int> v = {1,2,3,4,5,6,7,8,9,10};
int ret = accumulate(v.begin(),v.end(),0);

int a[] = {1,2,3,4,5,6,7,8,9,10};
int ret2 = accumulate(v,v+10,0);

정적 배열 및 벡터 모두 사용할 수 있고, 시작과 끝을 설정한대로 합을 수행하여 리턴한다

 

세번째 인자는 초기 값 세팅 인자인데, 사용하고자 하는 범위의 값을 넘길때, 오버플로우가 발생하고 Warning도 발생하지 않으며 자동 캐스팅을 진행하기 때문에 큰 범위인 수를 사용하고자 할때, 주의해야한다.

약 21억 4천 정도의 양수를 포함할 수 있는 자료형에 배열의 합을 21억 4천 이상이 나오게 될때 오버플로우가 발생된다.

// Case.1
long a[] = { 1000000000, 2000000000 };
long long ret = accumulate(a, a + 2, 0);
// ret == -1294967296

// Case.2
long a[] = { 1000000000, 2000000000 };
long long ret = accumulate(a, a + 2, 0LL);
// ret == 3000000000

큰 범위 값을 사용하려거든, 0LL 로 초기 자료형값을 세팅하자!

 

[max_element , min_element]

각각 배열 중 가장 크고 작은 요소를 추출하는 함수.

Iterator 를 반환하여 최대값의 인덱스, 값을 뽑아낼 수 있다.

list 는 인덱스를 구하려했는데, 컴파일 단에서 에러라, 뭔가 Node 형 구조라 인덱스를 빼도 의미가 없는것인가 하는 의문이 생겼다.

int a[] = { 1,2,5,4,3,2,8,15,0 };
vector<int> vec = { 1,2,5,4,3,2,8,15,0 };
list<int> list	 = { 1,2,5,4,3,2,8,15,0 };

// a[] = 정적 배열
cout << "a [] max value :: " << *max_element(a, a + (sizeof(a) / sizeof(int))) << '\n';
cout << "a [] max value Index :: " << max_element(a, a + (sizeof(a) / sizeof(int))) - a << '\n';

cout << "a [] min value :: " << *min_element(a, a + (sizeof(a) / sizeof(int))) << '\n';
cout << "a [] min value Index :: " << min_element(a, a + (sizeof(a) / sizeof(int))) - a << '\n';

// vector
cout << "vec	 max value :: " << *max_element(vec.begin(), vec.end()) << '\n';
cout << "vec	 max value Index :: " << max_element(vec.begin(), vec.end()) - vec.begin() << '\n';

cout << "vec	 min value :: " << *min_element(vec.begin(), vec.end()) << '\n';
cout << "vec	 min value Index :: " << min_element(vec.begin(), vec.end()) - vec.begin() << '\n';

// list
cout << "list max value :: " << *max_element(list.begin(), list.end()) << '\n';
cout << "list max value :: " << *min_element(list.begin(), list.end()) << '\n';

//cout << "list min value :: " << max_element(list.begin(), list.end()) - list.begin() << '\n';
//cout << "list min value :: " << min_element(list.begin(), list.end()) - list.begin() << '\n';
// Q.Node 형식 구조라 인덱스는 구할 수 없는건가.?