[C++] 알고리즘에서 자주 사용되는 문법
※ 키 입력 받기
엔터에 의한 분리
while (true)
{
if (cin.get() == '\n')
break;
}
※ cout
소수점 고정
cout << fixed;
cout.precision(3); // 3자리 고정
※ 수학연산자
#include <math.h>
거듭제곱 : pow(n,r);
제곱근 : sqrt(n);
로그값 : log10(n);
log2(n);
직선의 각도 : atan2(y,x);
If no errors occur, the arc tangent of y/x (arctan(y/x)) in the range [-π ; +π] radians, is returned.
Principal arc tangent of y/x, in the interval [-pi,+pi] radians.
One radian is equivalent to 180/PI degrees.
double x, y, result;
x = -10.0;
y = 10.0;
result = atan2 (y,x) * 180 / PI;
printf ("The arc tangent for (x=%f, y=%f) is %f degrees\n", x, y, result );atan2() to range[0 ; +2π]
fmod(atan2(y,x)+2*PI, 2*PI);
※ 파일 쓰기 변환
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
※ 동적 배열 할당 및 자동 초기화
1차원 배열
int number;
cin >> number;
int * numbers = new int[number]{};
2차원 배열
int n1, n2;
cin >> n1 >> n2;
int ** numbers = new int*[n1];
for (int i = 0; i < n1; i++)
{
numbers[i] = new int[n2]{};
}
jagged 배열 선언 (vector를 이용하여 쉽게 선언하는 방법)
// jagged array
vector<int> swi[10]
{
{0,1,2},
{3,7,9,11},
{4,10,14,15},
{0,4,5,6,7},
{6,7,8,10,12},
{0,2,14,15},
{3,14,15},
{4,5,7,14,15},
{1,2,3,4,5},
{3,4,5,9,13}
};
// reference
for (int i = 0; i < 10; i++)
{
for (int data : swi[i])
{
cout << data << " ";
}
cout << endl;
}
※ enum의 문자열과 값 사이 변환
enum alphabet { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z };
const char Toalphabet[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
int main()
{
cout << (alphabet)C << alphabet(2); // number 2
cout << Toalphabet[2]; // C
}
※ Char 사용
#include <string.h>
메모리 복사 : void * memcpy ( void * destination, const void * source, size_t num );
문자열 비교 : int strcmp ( const char * str1, const char * str2 );
| return value | indicates |
|---|---|
<0 |
the first character that does not match has a lower value in ptr1 than in ptr2 |
0 |
the contents of both strings are equal |
>0 |
the first character that does not match has a greater value in ptr1 than in ptr2 |
※ String 사용
#include <string>
모든 함수 정보
http://www.cplusplus.com/reference/string/string/
|
length(), size() |
문자열 길이 반환 |
|
insert(index1,string) |
index1에 string 문자 삽입 |
|
erase(index1, index2) |
index1부터 index2만큼 삭제 |
|
substr(index1, index2) |
index1부터 index2만큼 문자열 반환 |
※ 문자열과 숫자 사이의 변환
#include <string>
// number to string
int num = 123;
string str = to_string(num);
// string to number
int sum = 0;
for (int i = 0; i < str.length(); i++)
{
sum += atoi(str.substr(i, 1).c_str());
}
※ 문자열 분리하기
문자 하나에 대한 분류
#include <string>
#include <vector>
string targetstring = "akboasodfjvaooa";
char token = 'a';
vector<string> vec;
int findindex = 0;
while (true)
{
// 다음 인덱스 탐색
int index = targetstring.find(token, findindex);
// 토큰이 스트링에 연달아 있을 경우
if (findindex == index)
{
findindex = index + 1;
continue;
}
// 탐색이 끝났을떄
if (index == -1)
{
if (targetstring.length() != findindex)
vec.push_back(targetstring.substr(findindex, targetstring.length() - findindex));
break;
}
else
{
vec.push_back(targetstring.substr(findindex, index - findindex));
findindex = index + 1;
}
}
// split into a string[]
for (string st : vec)
{
cout << st << endl;
}
※ Vector
동적배열로 정의된 함수 (가변길이 배열 STL)
장점: 요소가 인접한 위치에 있으므로 메모리가 적고 임의의 위치를 인덱스로 O(1)으로 접근할 수 있다.
단점: 삽입 삭제가 이루어질떄는 요소의 이동이 있으므로 삽입 삭제가 빈번할 경우는 list를 사용할 것.
vector도 insert()와 erase()로 삽입과 삭제가 가능하나 주로 사용하지는 않는다.
vector 순회
vector<int>::iterator ii;
for( ii=vector.begin(); ii!= vector.end(); ++ii)
printf("%d",(*ii));
vector 중간 부분 떼어내어 새로운 vector 만들기
// index st부터 en+1 까지..
vector<int> Split(vector<int>& vec, int st, int en)
{
// vector.end() == vector+begin()+vector.size()
return vector<int>(vec.begin() + st, vec.begin() + en);
}
※ Vector 에서 binary search
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
std::vector<int>::iterator low,up; // std::vector<int>::iterator ==> auto
low=std::lower_bound (v.begin(), v.end(), 20); // ^
up= std::upper_bound (v.begin(), v.end(), 20); // ^
std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; // 찾을 경우 해당 인덱스(중복데이터 일 경우 작은 인덱스
std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
// 찾을 경우 해당 인덱스(중복데이터 일경우 큰 인덱스+1)
// 못찾을 경우 들어갈 인덱스,15를 넣으면 lower uppper 모두 인덱스 3반환
return 0;
}
binary_search(begin , end, value) : 정렬된 배열[begin, end] 에서 value가 있는지 없는지 true / false
lower_bound(begin, end, value) : 정렬된 배열에서 value가 들어갈 수 있는 가장 앞쪽의 위치 iterator로
upper_bound(begin, end, value) 정렬된 배열에서 value가 들어갈 수 있는 가장 뒤쪽의 위치를 iterator로
※ Vector의 정렬
#include <algorithm>
#include <vector>
기본 데이터형 정렬
vector<int> vec;
for (int i = 0; i < 10; i++)
{
vec.push_back(rand());
}
sort(vec.begin(), vec.end()); // 기본 오름차순
사용자 정의형 정렬
/* 연산자 오버로딩을 이용한 정렬 */
struct MyClass
{
string name;
int number;
bool operator < (const MyClass &rhs) const
{
return rhs.number>number;
}
};
int main()
{
vector<MyClass> vec;
for (int i = 0; i < 10; i++)
{
vec.push_back({ "사용자" + to_string(i), rand() });
}
sort(vec.begin(), vec.end());
for (MyClass x : vec)
{
cout << x.name <<": "<<x.number << endl;
}
}
/* 일반 함수로 정렬*/
struct MyClass
{
string name;
int number;
};
bool Compare(MyClass& num1, MyClass& num2)
{
return num1.number < num2.number;
}
sort(vec.begin(), vec.end(), Compare); // 내림차순 정렬
/* reverse 이용 */
sort(vec.begin(),vec.end()); // 오름차순 정렬 후
reverse(vec.begin(),vec.end()); // 리버스
typedef bool (*comp)(int,int);
bool compare(int a, int b)
{
return (a>b);
}
int main()
{
std::priority_queue<int,std::vector<int>, comp> pq(compare);
return 0;
}※ List
이중 연결리스트로 구현된 array
인터페이스 자체도 vector와 비슷하다.
장점: 삽입과 삭제는 O(1) 시간 내에 가능하다.
단점: 특정 인덱스로 바로 접근은 불가하다.
#include <list>
list<int> li;
li.push_back(8); // 뒤에 추가
li.pubsh_front(3); // 앞에 추가
insert(위치, 데이터) 와 remove(데이터) 삭제와 삽입이 O(1)
※ Stack
#include <stack>
stack<int> s;
s.push(3);
- Test whether container is empty (public member function )
- size
- Return size (public member function )
- top
- Access next element (public member function )
- push
- Insert element (public member function )
- emplace
- Construct and insert element (public member function )
- pop
- Remove top element (public member function )
- swap
- Swap contents (public member function )
※ Queue
#include <queue>
queue<int> q;
q.push(3);
- Test whether container is empty (public member function )
- size
- Return size (public member function )
- front
- Access next element (public member function )
- back
- Access last element (public member function )
- push
- Insert element (public member function )
- emplace
- Construct and insert element (public member function )
- pop
- Remove next element (public member function )
- swap
- Swap contents (public member function )
※ pair , set, map
pair
순서쌍의 정보를 저장하는 경우 사용
#include <algorithm>
pair<char, int> p;
p = make_pair("철수", 20);
p.first // 철수
p.second // 20
set
동일한 타입의 데이터를 모아 놓은 것.
저장하는 데이터 자체가 키로 사용되어 값은 저장하지 않는다.
아무 위치에 저장되는 것이 아니라 정렬된 위치에 삽입하여 검색 속도가 매우빠르다.
어떤 값이 있는지 확인하는 배열을 만들어낼때 아주 큰 배열을 만들어야 한다면 사용하는 것이 좋다.
#include <set>
set<int> s;
s.insert(10);
s.insert(20); // 10 20
s.insert(10); // 동일한 데이터는 넣지 않음.
s.erase(30);
s.count(10)
s.find(10)==s.end() // true 면 set에 없다는 것
set<pair> ss; 로 할 경우 pair의 첫번째 요소에 대하여 정렬하고, 두개의 변수가 같을때만 같은요소라고 판단한다.
map
(key, value) 형태로 데이터들을 기억하고 key값으로 매칭되어 값을 저장한다.
#include <map>
map<int, int> m;
m[3] = m[1] * 100;
m[5] = 3;
m[2] = 3;
m[-2] = 3;
// (-2,3) , (1,0) , (2, 3), (3, 0), (5,3) 순으로 저장되어 앞에 것이 인덱싱으로 검색한다.
//map의 사용법
map<int, int> m;
for (int i = 0; i < n; i++)
{
int d; scanf("%d", &d);
m[d]++; // 요소가 없을 경우 자동으로 1이 저장되고..
}
// map의 값 순회하기
for (map<int,int>::iterator it = m.begin(); it != m.end(); it++)
{
int f = it->first; // 요소
int s = it->second; // 값
}
// map을 이용한 이진검색트리 활용
int main(void)
{
map<int, int> m;
m[1] = 5;
m[5] = 3;
m[7] = 2;
m[8] = 1;
m[55] = 3;
// 추가 연산 O(logN)
// m.lower_bound(1)-> first => 1
// m.lower_bound(1)-> second => 5
// m.lower_bound(3)-> first => 5
// m.lower_bound(3)-> second => 3
// map 구조에서 lowerbound(x)는 m[x]에 데이터를 넣게 될때 들어갈 자리의 매핑주소를 가져온다.
// 삭제연산 O(logN)
// m.erase(5) => m[5] 삭제
printf("%d\n", m.lower_bound(1)->second );
return 0;
}
