알고리즘 문제만 무작정 푸는 것 같아 이번에 주요 개념들을 다시 정리하는 시간을 가지려한다
바킹독님, 큰돌님 강의와 다른 자료들을 바탕으로 복습을 진행해볼 예정!
< 정수 자료형 >
-- int --
int 형 1개는 4byte
< 실수 자료형 >
float - 유효숫자 6자리
double - 유효숫자 15자리
long long - 유효숫자 19자리
- double에 long long 타입 변수 담지 않기!!
- 실수 비교 시 '==' 사용하지 않기!!
< STL을 인자로 사용하는 경우>
- STL을 함수 인자로 보내는 경우 구조체와 동일하게 복사본을 만들게 되므로 함수내에서 새로운 값을 할당해도 변경되지 않음
ex> void function(vector< int > vec){...}
어떤 벡터 A를 인자로 보내서 위 함수를 호출해서 vec의 값을 변경해도 기존의 A에는 영향이 없다!!
bool cmp1(vector<int> v1, vector<int> v2, int idx){
return v1[idx] > v2[idx];
}- 놀랍게도 위 함수의 시간복잡도는 O(N) 이다
- STL이 인자로 전달될 시 복사를 하기 때문이다
- 벡터의 N개의 원소들을 하나하나 복사
매번 복사하는 것은 비효율, 아래와 같이 해결할 수 있다
bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
return v1[idx] > v2[idx];- 참조자를 사용!!
- cmp2는 호출될 시 복사본을 만들지 않고 참조 대상의 주소 정보만 넘기므로 O(1)의 시간복잡도를 가진다!!
< 표준 입출력 >
- c++ string 클래스 사용을 하고 이를 scanf, printf 사용하고 싶은 경우 char* 타입으로 입력을 받고 string으로 형변환을 해서 원하는 작업을 한 다음 c_str() 메소드를 활용하여 출력하면 된다!!
#include<bits/stdc++.h>
using namespace std;
int main() {
char a[10];
scanf("%s", a);
string s = a; // or string s(a);
printf("%s\n", s); // 오류
printf("%s\n", s.c_str());
return 0;
}
위 결과와 같이 hi를 입력했고 이를 char* 변수 a로 받았다
이 값을 string 변수 s에도 할당을 했고, printf로 출력 시 s에
c_str() 메서드를 사용해줘야 정상적으로 출력이 나온다!!
- scanf 와 cin 모두 공백 앞까지만 입력을 받는다
- < 해결책 >
- scanf 옵션
char ch1[10];
scanf("%[^\n]", ch1);- gets 함수(보안 이슈로 c++14 이상에서는 제거됨)
char ch2[10];
gets(ch2);
puts(ch2);- getline 함수
string s;
getline(cin, s);
cout << s; - cin/cout 사용하는 경우에는 입출력으로 인한 시간초과를 방지하기 위해 다음 명령어를 main함수 안에 작성해줘야 한다
-
ios::sync_with_stdio(0)
위를 명시한 경우 해당 코드에서 cout 과 printf 같이 사용하면 안됨!!!!! -> 이 경우 cin, cout만 사용하기
(이유 : https://www.youtube.com/watch?v=6lhVHP8bkPA&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=3 10:29) -
cin.tie(0)
일반적으로 출력 내용만 정답 검사과정을 거치므로 cin 명령을 수행하기 전 cout버퍼를 비울 필요가 없어서 위와 같이 cin.tie(0)을 해준다
< 입력 값들이 붙어있고 한 자리 씩 받아서 할당해야 하는 경우 >
- https://www.acmicpc.net/problem/2178
- 위 문제와 같이 붙어있는 형태로 입력이 주어지면 scanf("%1d", &a) 를 사용한다
- 이 경우에는 ios::sync_with_stdio(0), cin.tie(0) 사용 하지 않기!!
< 시간복잡도 >
- 문제를 풀때 다른 로직을 생각해야 하는지에 대한 기준점이 된다
- ex> N * N 크기의 맵에서 bfs를 하는 경우 시간복잡도는?? -> N^2
- ex> N N 크기의 맵에서 2 개의 지점을 고르고 각각 bfs 를 하는 경우 시간복잡도는? -> (N^2 C 2 ) N^2
< 주요 C++ 함수 시간복잡도 >
- sort : nlogn
- lower_bound, upper_bound : nlogn
- find : n
< 공간복잡도 >
- 배열 크기 1000만은 안된다
- -> 이분탐색 or 펜윅트리 생각하자
- 펜윅트리를 만드는데 배열 크기 10억이 필요하다면 이분탐색 고려해보자
< 구간합 >
- 정적배열 : 구간합
- 동적배열 : 트리 (세그먼트 트리 or 펜윅트리 )
매 순간 최선을 다하자