바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/
int형 변수 넘기면 값이 복사가 되므로 원본에 영향 x
int형 배열 넘기면 주소값이 복사가 되므로 원본에 영향
구조체 넘기면 int형 처럼 값이 복사가 되므로 원본에 영향 x
swap을 할때 파라미터로 포인터나 참조를 쓰지않으면 복사가 되지 않는다.
void swap1(int a, int b) // swap 안됨
{
int temp =a;
a = b;
b = temp;
}
void swap2(int *a, int *b) // swap 됨
{
int temp = *a;
*a = *b;
*b = temp;
}
void swap3(int &a, int &b) // swap 됨
{
int temp = a;
a = b;
b = temp;
}
vector
vector는 일정한 길이가 아닌 사용자의 필요에 따라 길이가 변하는 배열이다.
vector<int> v(100); // 크기가 100인 정수형 vector 선언STL도 구조체처럼 함수 인자로 보낼때 값을 복사해서 넘기는 것이므로 원본에 영향을 주지 않는다.
bool cmp1(vector<int> v1, vector<int> v2, int idx)
{
return v1[idx] > v2[idx];
}이 함수의 시간복잡도는 O(n)이다.
그 이유는 vector v1과 v2을 함수 인자로 실어서 보낼때 복사본을 만드는데 이때 v1, v2의 크기인 n만큼의 시간이 소요되므로 시간복잡도가 O(n)인 것이다.
이를 해결하기 위해서는
bool cmp1(vector<int> &v1, vector<int> &v2, int idx)
{
return v1[idx] > v2[idx];
}인자를 참조형으로 넘기면 된다. 이러면 복사본을 만들지 않고 v1, v2의 주소만 넘기므로 시간복잡도가 생각한대로 O(1)이 된다.
STL은 함수의 인자로 넘겨질때 원본을 보내는게 아니라 복사를 해서 보내므로 예상한대로 시간복잡도가 나오게 하기 위해서는 참조를 해서 주소 정보만 보내는 식으로 해야한다.
표준 입출력
scanf/printf와 cin/cout은 큰 차이는 없다. 물론 scanf/printf와 속도면에서는 조금 빠르다. 그러나 scanf/printf는 string을 처리할 수 없는 단점이 있다.
scanf, cin으로는 공백을 받을수는 없고 getline을 사용해야 한다.
char형이라면 cin.getline(), string형이라면 getline()을 사용하면 된다.
endl은 절대로 쓰면 안된다. 줄바꿈은 '\n'을 사용해야한다.
