[알고리즘 트레이닝] 2장. 프로그래밍 기법 (1)

[알고리즘 트레이닝] 2장. 프로그래밍 기법

2.1언어적 특성

// 표준 라이브러리 전체를 포함시키는 g++ 컴파일러 기능
#inlcude <bits/stdc++.h> 

// 표준 라이브러리의 클래스 및 함수를 바로 사용하기 위한 선언문
using namespace std; 

int main(){
    // 풀이 작성 부분
}

컴파일 명령어

>> g++ -std=c++11 -02 -Wall -o test

c++11 표준을 따름(-std=c++11)

코드 최적화(-02)

발생 가능한 오류에 대한 경고(-Wall)

---

2.1.1 입력과 출력

C++

입력을 수성하는 각 원소 사이에 적어도 한 개의 공백 문자나 개행 문가 존재하는 경우

int a, b;
string x;
cin >> a >> b >> x;

공백 문자만 존재 / 공백 문자와 개행 문자가 모두 존재하는 경우

 /* 
 예시 1. 
 123 456 monkey

 예시 2.
 123 456
 monkey
 */

 int a=123, b = 456;
 string x = "monkey";
 cout << a << " " << b << " " << x << "\n";

입력과 출력이 프로그램의 병목이 되는 경우

ios::sync_with_stdio(0);
cin.tie(0);

개행 문자 "\n" 이endl 보다 빠르다

endl 을 사용하면 명시적으로 flush(출력버퍼 비우기)가 일어나기 때문이다

C언어

scanf, printf사용가능

스트림보다 약간 더 빠르지만, 사용법이 어렵다.

두개의 정수를 입력받는 코드

int a, b;
scanf("%d %d", &a, &b);

두개의 정수를 출력하는 코드

int a = 123, b = 456;
printf("%d %d\n", a, b);

입력을 공백 포함 한줄로 읽어들이는 경우

string s;
getline(cin, s);

while(cin >> x){
 //코드
}

파일을 이용하는 경우

표준 스트림을 사용하는 코드 작성 후, 코드 시작 부분에 아래 두줄추가

freopen("input.txt", "r", stdin);
freopne("output.txt", "w", stdout);

---

2.1.2 수를 처리하는 방법

정수

가장 많이 사용되는 자료형 : int

int는 32bit 자료형이며 범위는 -2^31 ~ 2^31-1(대략 -2x10^9 ... 2x10^9)

int로 부족할 경우 사용하는 자료형 : long long

long long x = 123456789123456789LL;

접미사 LL은 long long 을 의미한다.

나머지 연산

답을 m(모듈로) 으로 나눈 나머지를 구하여 출력하는 것이다.

답이 매우 크더라도 int 나 long long 같은 자료형으로 충분히 해결할 수 있다.

매번 연산을 수행할 때마다 나머지를 취해 주면 되고, 그렇게 하면 값이 매우 커지는 경우가 절대 발생하지 않는다.

long long x = 1;
for (int i = 0; i <= n; i++){
    x = (x*i)%m;
}
cout << x << "\n";

나머지 값이 통상적으로는 0 ... m-1 범위에 있다.

하지만 C++ 및 그 밖의 언어 중에서 음수의 나머지를 0이나 음수로 처리하는 경우가 있다.

나머지가 음수가 되지 않도록 하는 간단한 방법

x = x%m;
if (x < 0) x += m;

평소대로 나머지 연산을 한 후에 그 결과가 음수라면 m을 더해준다.

코드에 뺄샘이 포함되어 있고, 그 결과가 음수가 될 수 있는 경우에만 필요하다.

부동 소수점 실수

c++ 부동 소수점 자료형 : double (64bit)

대부분의 문제는 어느 정도의 정밀도로 답을 구해야 하는 지 나와 있다.

double x = 0.3 * 3 + 1;
print("%.20f\n", x); //0.999999...88898

부동 소수점 실수를 == 연산자를 이용하여 비교하는 것은 위험하다.

정밀도 오류로 인해 다른 결과가 나온다.

비교 방법

if(abs(a-b)) < 1e-9{
// a와 가 일치한다.
}