언어/C++
[C++] ICPC 25W 1회차 - 알고리즘과 시간복잡도
rngPwns
2025. 1. 25. 07:39
1. 알고리즘이란?
- 수학과 computer science에서
- 유한열
- 수학적으로 엄격한 지침
- 특정 종류의 문제 해결 or 연산수행에 사용
2. C++
- int a; a=3 / int b=5; / int c=a+b;
- 자료형
1. 정수형: int, long long, unsigned int, unsigned long long
2. 실수형: float, double, long double (float보다 double이, double보다 long double이 더 정확(저장값과 실제값의 오차가 더 작음)
3. 문자 및 문자열
#include <iostream>
#include <string>
int main(){
char a='a';//char은 작은따옴표로 감싸기
std::string hello="ICPC Sinchon 25W";//string은 큰 따옴표로 감싸기, string 헤더파일을 include 해줘야 사용가능
}
4. 자료형
- boolean: 참 또는 거짓
- bool t=true;
- bool f=false;
5. 입출력
#include <iostream> //헤더포함
using namespace std; //namespace를 std로 지정->함수나 객체가 정의된 공간지정 의미
//같은이름을 가진 함수나 객체가 동일한 공간에 있을 경우 서로 충돌할 수 있기 때문에 namespace를 통해 구분
//해당 줄이 없을 경우 내장함수를 사용할 때 반드시 앞에std:: 붙여줘야함(std::cin, std::cout 등)
int main() {
int a, b;
cin >> a >> b; // 3 5 //입력은 cin, 출력은 cout 사용
//cin >> n : 값이 n으로 들어온다. cout << n: 값이 n에서 나간다.
cout << a << ' ' << b << '\n';
// 출력:3 5
cout << "Hello ICPC Sinchon\n";
// 출력:Hello ICPC Sinchon
cout << "Hello ICPC";
cout << " Sinchon 25W";
// 출력:Hello ICPC Sinchon 25W
//return 0; -명시적으로 종료위치에 작성가능(코드실행 중간에 멈출때도)
}- std::endl도 줄바꿈에 해당하지만 버퍼를 비우는 작업 추가진행 -> 입출력 느려지고 시간초과 발생 원인이 될 수 있음
6. 빠른 입출력
#include <iostream>
using namespace std;
int main(){
ios::sync_with_studio(0);
cin.tie(0);
//code goes here
}- cin을 사용하는 경우 입력받기 전 위 코드 두 줄 추가해야 입력 빨라짐
- C처럼 C++도 scanf, printf 사용가능. 이 두 함수도 빠른입출력 해당
- cin/cout과 scanf/printf 섞어 쓸 경우 ios::sync_with_stdio(0); 적용하면 안됨(애초에 섞어쓰지 마세여)
7. 산술연산자
#include <iostream>
using namespace std;
int main(){
int a=3, b=5;
cout << a+b << '\n';
cout << a-b << '\n';
cout << a*b << '\n';
cout << a/b << '\n';
cout << a%b << '\n';
}#include <iostream>
using namespace std;
int main(){
int a=3, b=3;
cout <<a<<'\n'; //3
cout <<+a<<'\n'; //3
cout <<-a<<'\n'; //-3
a+=b;
cout << a << '\n'; //6
b*=a; b-=a; b\=a; b%=a;
cout << b << '\n'; //?
cout << a++ << '\n'; \\6
cout << a << '\n'; \\7
cout << ++a << '\n'; \\8
}
8. 비교연산자 - C랑 똑같음
9. 논리연산자 - C랑 똑같음
- 반환되는 값은 연산결과에 따라 true 또는 false
#include <iostream>
using namespace std;
int main(){
int a=3, b=5, c=3, d=4;
cout <<((a==c)&&(b>=d))<<'\n'; //1
cout <<((a==c)||(b>=d))<<'\n'; //1
cout <<!(a>0);<<'\n'; //0
}
10. 조건문 - C랑 똑같음
11. 반복문 - C랑 똑같음
12. 배열
#include <iostream>
using namespace std;
int arr1[5];
int arr2[5]= {1,2,3,4,5};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0; i<5; i++){
cin >> arr1[i];
}
arr2[2]=6;
for(int i=0; i<5; i++){
cout << arr2[i] << ' ';
}// 1 2 3 4 5
13. 함수
void fun1(int x, int y){ //반환값 없는 함수
cout << x * y << '\n';
}
int fun2(int x, int y){
return x*y;
}
int fun3(int x, int y){
fun1(x,y); // 함수 안에서 함수 호출 가능
return fun2(x,y);
}
3. 시간복잡도
시간복잡도 분석
- 코드의 i번째 줄을 한 번 실행하는 시간/비용 = Ci라 한다.
- 각 줄이 코드가 실행되는 동안 몇 번 실행되는지 계산
- 2.의 결과와 해당하는 Ci값을 곱한 후 전부 더해준다. -> f(n)이 나옴
- 상수 계수를 무시하고 적은 결과 -> big-O natation
#include <iostream>
using namespace std;
int main() {
int n; // 1
cin >> n; // 2
int sum3 = 0; // 3
for(int i = 1; i <= n; i++) {
// 4
for(int j = 1; j <= n; j++)
{ // 5
sum3 += i ∗ j; // 6
}
}
}- 1,2,3번 줄은 한 번만 실행
- 4번줄은 n번 반복되는 for문 -> n번 실행
- 5번줄은 n번 반복되는 for문, 4번줄에 있는 for문 안에 있어서 n*n=n^2번 실행
- 6번줄도 n^2번 실행
- f(n) = C1 +C2 +C3+C4n+C5n^2+C6n^2 ----> f(n) =O(n^2)
실행시간 예측하기
- 시간복잡도는 프로그램의 실행시간 결정하는 절대적 기준 x
- 연산의 종류에 따라 소요시간 달라짐, 캐싱 등의 요인으로 인해 더 나은 시간 복잡도를 가진 알고리즘도 실제로 특정 데이터크기에서는 더 느릴 수 있음
- big-O notation에서 무시하는 상수계수를 포함하면 더 자명
- C++ 기준으로 10^8개의 연산을 1초에 처리할 수 있다고 가정하면 계산 편리
- 가벼운 연산만 포함하면 이보다 더 많은 연산도 시간 내 실행 가능-> 그냥 코드가 통과할지, 시간 초과 판정을 받을지 예측하는 참고값 정도로 활용하자~!