기본 PS문법

PS를 하는 데에 있어 기본 문법들을 소개한다.

Posted Jan 19, 2025 Updated Mar 26, 2025

By Teyn

23 min read

기본 PS문법

기본 코드 설정

  
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

줄별로 하나하나 알아가보자.

  
#include <bits/stdc++.h>

“왜 iostream이 아닌 처음 들어보는 헤더를 사용하지?”라는 의문이 들 수 있다. 우리가 이 헤더를 사용하는 이유는 이 헤더에 알고리즘 문제풀이에 필요한 모든 헤더가 Include 되어있기 때문이다. 예를 들어, Vector를 사용하려면 #include <vector>를 해야 했지만 위 헤더를 사용하면 이미 Vector헤더가 포함되어 있어 Include를 추가적으로 할 필요가 없다.

다만 단점또한 존재한다. 사용하지 않는 헤더까지 Include하게 되기 때문에 쓸데없는 메모리를 잡아먹기도 하며 현업에서는 좋은 습관이 아니다.

  
using namespace std;

이걸 사용하지 않는다면 간단한 입출력 명령어인 cin, cout을 사용할 때에 std::cin, std::cout과 같이 추가로 작성할 것이 많아진다. 왠만하면 사용하도록 하자.

이또한 현업에서는 좋은 습관이 아니다.

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

C++에서 이용하는 입출력인 cin, cout은 입출력이 상대적으로 느린편에 속한다. 따라서 입출력이 빡빡한 문제를 만나면 코드가 맞았는지의 여부에 관계없이 TLE(Time Limit Exceeded, 시간초과)를 받을 수도 있다. 이로 스트레스를 받기 전에 매번 코드를 짤때 위 코드를 넣는 습관을 길러보자.

다만 이 코드를 사용했다면 printf, scanf와 cin, cout을 혼동하여 사용해서는 안된다. 자세한 설명은 해당 블로그를 읽어보자.

입출력

기본 입출력 문법

  
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cout << "이름을 입력해주세요:";
    string s; cin >> s;
    cout << "환영합니다. " << s << "님!\n";
    int age, ID;
    cout << "나이와 학번을 띄어쓰기로 구분하여 입력해주세요:";
    cin >> age >> ID;
    return 0; 
}

C++에서의 입출력은 cin, cout을 사용한다. 이 때, 부등호 두개를 이용하여 입력과 출력을 받는데 필자는 cout의 경우 밖으로 내보내기에 좌측, cin의 경우 들어오기에 우측으로 외웠었다. 이는 많이 보다보면 익숙해질 것이다. 또한 연달아 출력을 하기 위해서는 << 기호로 끊고서 출력을 해주자. 띄어쓰기로 구분된 입력을 받을 때에도 각 변수별로 끊어서 받아주면 된다.

심화 입출력 문법

심화 입출력에 대해서 다룬다. 이런 유형에 해당하는 문제를 보고 나서 다시 읽어도 되니 어렵다면 그냥 이런게 있구나~ 생각하고 넘어가자.

EOF란?

문제를 풀다보면 백준 10951번 문제와 같이 입력의 제한을 두지 않는 문제가 있다. 이를 EOF라 하여 파일의 끝을 읽으면 자동으로 종료하게 하는 코드를 짜야하는 문제이다. EOF의 처리는 다음과 같이 하면 된다(문제 스포 주의)

  
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a, b;
    while(cin >> a >> b){
        cout << a + b << "\n";
    }
    return 0;
}

cin은 읽어올 파일이 더 이상 없다면, 즉 EOF에 도달하면 False를 반환한다. 이를 이용하여 코드를 짤 수 있다.

띄어쓰기를 포함한 입력 받아오기

문자열 문제를 풀 때 심심치않게 띄어쓰기를 포함하는 입력을 받아와야 할 때가 있다. 이는 getline 함수를 이용하여 처리한다.

  
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s; getline(cin, s);
    cout << s; 
    return 0;
}

이를 실행하면 띄어쓰기까지 포함하여 한 줄을 읽어오는 것을 볼 수 있다.

getline과 cin을 혼동하여 사용하면 약간의 오류가 발생할 수 있다. getline은 줄바꿈 문자를 기준으로 입력을 끊기 때문에 버퍼에는 맨 앞에 줄바꿈 문자만 남게 된다. cin또한 줄바꿈 문자가 입력되면 종료되기에 getline 후 바로 cin을 사용하면 cin은 아무 값도 가져오지 않는 것을 볼 수 있다. 그러니 둘을 혼동해서 사용한다면 그 사이에 cin.ignore();을 적어주는 것을 습관화하자.

소수점 정밀 출력

정답을 소숫점을 포함한 답으로 내야하는 문제는 절대오차 \(10^{-6}\)미만을 허용한다는 문구를 자주 볼 수 있다. C++에서의 소수점 오차는 다음과 같이 다룬다.

  
cout << fixed;
cout.precision(7);
cout << 3.141592 << "\n";

//한줄버전
cout << fixed << setprecision(7) << 3.141592 << "\n";
//참고 : https://blog.naver.com/dong_gas

자료형

PS에서 사용하는 자료형을 간단하게 소개한다.

int

매우 기본적인 정수를 표현하기 위한 자료형이다. 범위는 \(2^{31} - 1(\cong 2,100,000,000)\)이하로 어림잡아 하면 된다. 연산에 있어 Overflow가 나게 하는 주 원인이므로 최댓값을 계산해보고 int의 범위에 들어가는지 체크하는 것을 습관으로 만들자

double

float도 있는데 왜 double을 사용하냐?는 의문이 들 수도 있다. Float은 Double에 비해 오차가 매우 크기 때문에 PS에서 사용했다간 점수를 얻기 힘들다. 따라서 우리는 안전한 Double을 사용하도록 하자.

long long (int)

int의 overflow를 방지해주는 훌륭한 자료형이다. 범위는 \(2^{63}-1\)까지이므로 파이썬으로만 풀 수 있는 큰 연산이 아닌 한 왠만한 문제는 long long 선에서 처리가 가능하다. 여기서 이러면 int를 왜 사용하냐는 의문이 들 수도 있다. 대부분의 문제에서는 int 대신 long long을 사용해도 큰 문제는 되지 않는다. 다만 메모리 제한이 큰 문제에서 long long을 난사하면 피를 볼 수도 있기 때문에 일단은 int를 사용하자. 필자의 경우에는 매크로에 long long을 박아놓고 줄여서 사용하고 있다.

#define ll long long
//long long을 칠 필요 없이 ll만 쳐서 사용할 수 있다.

String

C++에서는 문자열을 다룰 때 string을 주로 이용한다. 단순히 char로 구성된 배열로 봐도 무방하다. 특이한 문법 또한 많은데 이는 공식 레퍼런스에서 문자열에 관한 기능과 함수를 살펴보자. 필자가 주로 사용하는 문법은 하단의 문법밖에 없긴 하다.

  
string name = "teyn";
cout << name.size() << "\n" //output: 4
name = name + "k";
cout << name //output: teynk

pair<type, type>

아마 이 자료형은 익숙하진 않을것이다. 페어는 두 자료를 묶어 한 칸에 넣을 수 있도록 포장해주는 역할을 한다. 예를 들어 A의 성적과 이름을 저장해야 하는데 이를 두 배열에 따로 저장하면 자료형을 이동할 때 매우 힘들어질 것이다. 이를 묶어서 저장할 수 있도록 돕는 것이 pair의 역할이다.

  
pair<string, int> grade = {"dlwocks1209", 80};

이렇게 쌍으로 묶어 저장이 가능하고, 타입에는 페어가 또 들어가 3개 이상의 자료형을 묶어서 저장할 수 있다. 페어는 나중에 정렬 파트에서 중요하게 사용된다. 페어의 접근은 다음과 같이 처리한다.

  
cout << grade.first << grade.second << "\n";

벡터

벡터란?

C에서의 array와 같은 기능을 하나 좀 더 많은 기능이 추가된 array로 봐도 무방하다. 속도는 array에 비해서 약간 느리긴 하나 우리가 신경 쓸 정도는 되지 않는다. 선언은 다음과 같이 한다.

  
vector<type> name(size, val);
//type: int, double과 같은 자료의 타입이 들어간다.
//name: 변수명이다. 본인이 맘대로 지어보자
//size: 벡터의 크기를 나타낸다.
//val: 벡터에 기본으로 값을 할당하는 것을 말한다. 아무것도 치지 않는다면 0이 들어간다.

//ex1
int n; cin >> n;
vector<int> v(n); //n의 길이를 가진 각 칸의 값이 0인 int배열을 선언한다.

//ex2
vector<double> a = {1.1, 3, 4.2}; //1.1, 3, 4,2 총 3개를 가진 벡터를 생성한다.

vector<pair<int,int>> tmp(10); //pair 자료형으로 10칸을 가진 벡터를 선언한다.

접근 또한 배열과 같이 하면 된다.

  
vector<int> v = {1, 2, 3, 4};
cout << v[2]; //output = 3

언제나 주소는 0부터 센다는 것을 잊지말자.

주로 사용하는 문법

begin(), end() (with front(), back())

벡터의 주소 시작과 끝을 반환한다. 주솟값 자체는 iterator 자료형이라 바로 사용을 못하니 적절히 주솟값끼리 빼서 int형으로 만들자. 또한 iterator에는 *를 붙여 해당 위치의 값을 반환할 수 있다는 것 또한 알아두자.

  
vector<int> v = {1, 2, 3, 4};
cout << v.end() - v.begin() << "\n"; //output = 4(벡터의 길이)
cout << *v.begin() + *v.end() << "\n" //output = 5, (==v.front() + v.back())

v.end()의 반환값은 마지막 값이 위치한 곳이 아닌 마지막값의 주소 + 1이다. 이런 STL문법에서는 주소를 보통 \([a, b)\)로 표현한다는 것도 알아두자.

.size()

벡터의 사이즈를 반환한다. 자세한 설명은 생략한다.

.push_back()

벡터 뒤에 원소를 추가한다.

  
vector<int> v = {1, 2, 3, 4};
v.push_back(5); //v = {1, 2, 3, 4, 5}

.clear()

벡터를 초기화한다. 자세한 설명은 생략한다.

정렬

우리는 더 이상 정렬을 구현할 필요가 없다! STL에서 기본적으로 제공해주는 퀵 정렬을 마음껏 사용하도록 하자

  
// 구성은 sort(startpoint, endpoint, cmp)로 이루어져 있다. cmp를 이용하지 않는다면 기본 오름차순 정렬, 내림차순을 원한다면 less<>()를 이용하자.  
vector<int> v = {3, 4, 2, 1};
sort(v.begin(), v.end()); //result = {1, 2, 3 ,4}
sort(v.begin(), v.end(), less<>()); //result = {4, 3, 2, 1}

여기서 페어를 넣고 정렬하면 사전식 정렬로 쭈욱 정렬하게 된다. 코드를 직접 짜보고 실행해보자. 이해가 될 것이다. 또한 cmp는 본인이 원하는대로 bool 함수를 만들어서 정렬도 가능하다. 정렬 연습문제를 많이 풀어보자.

sort의 시간복잡도는 \(O(nlogn)\)이다. 절대로 잊지말자.

이분 탐색

이분탐색도 더이상 구현할 필요가 없다! STL에서 제공해주는 upper_bound, lower_bound 함수를 애용하자.

  
//구성은 upper lower 동일하며 lower_bound(startpoint, endpoint, findvalue)로 작성한다.
//upperbound는 findvalue보다 큰 값중 최솟값의 위치를 반환한다.
//lowerbound는 findvalue 이상의 값 중 최솟값의 위치를 반환한다.
vector<int> v = {1,1,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5};
cout << upper_bound(v.begin(), v.end(), 2) - lower_bound(v.begin(), v.end(), 2) << "\n"; 
//output: 5

이분 탐색은 배열이 정렬되어있을때에만 사용 가능하다! 이 점을 잊지말자.

이분 탐색의 시간복잡도는 \(O(logn)\)이다. 절대로 잊지말자.

조건문과 반복문

조건문이란?

  
if(condition1){
    sentences1;
}else if(condition2){
    sentence2;
}else{
    sentence3;
}

condition이 참을 반환하면(== 0이 아닌 값을 반환하면) sentences1를 실행하고, 거짓이라면 다음 구문인 else if로 이동, 또 거짓이 나왔다면 sentence3를 실행한다.

condition은 참과 거짓을 반환하는 비교연산자 혹은 비트연산자를 이용하여 주로 정의한다. 예를 들어 condition에 들어갈 수식이 a == b라면, a와 b가 같을 때 True(1)을 반환하고 다르다면 False(0)을 반환한다. 만약 우리가 판단하고자 하는 condition이 복잡하다면, &&,

, !와 같은 연산자를 이용하여 복합 condition을 만들어 줄 수도 있다.

반복문이란?

반복문은 크게 두가지 종류가 있다.

  
for(val; condition; other){
    sentences;
}
while(condition){
    sentences;
}

첫번째론 For문이다. 주로 사용하는 반복문이며 변수를 내부에 선언하고 그 값을 증가시키며 조건에 맞는지 판단하고 맞다면 sentences를 반복한다. for문은 주로 두 방법으로 사용한다.

  
vector<int> v(n);
for(int i = 0; i < n; i++){
    cout << v[i] << "\n";
}
for(int x : v){
    cout << x << "\n";
}

첫번째 방법은 매우 스텐다드한 방법이다. 컴퓨터에서의 배열은 0부터 시작하기에, 0부터 n - 1까지 반복하며 배열에 있는 모든 값들을 출력하게 된다. 처음에 for문에서 i = 0이라 정의하여 for문에서만 사용하는 변수를 선언했다. 다음 문장은 i < n을 넣어 조건에 맞는지 판별하도록 한다. 조건에 맞다면 아래 cout문을 실행하게 된다. 내부에 있는 문장을 다 사용했다면 i++문을 실행하여 i값을 증가시킨다. 두번째 방법은 range based for loop라 하여, 기존에 배열에 접근하던 방법에서 벗어나 각 원소를 처음부터 순회하며 값을 변수에 집어넣고, 배열이 끝난다면 종료하는 반복문이다. 이 반복문은 나중에 pair 혹은 구조체 등을 사용하는 배열을 순회할 때 값을 손쉽게 불러올 수 있다는 장점이 있다.

시간복잡도

문제에는 항상 제한시간이 걸려있다. 제한시간이 없다면 모든 문제를 브루트포스로 풀 수 있으나 제한시간이 있기에 우리는 적절한 알고리즘을 찾아 문제를 풀어야 한다.

단순한 시간복잡도 계산

컴퓨터는 1초에 대강 1억번의 연산을 할 수 있다고 가정한다.
(극하지만 절대적인 수치는 아니고 극히 단순한 연산의 경우 가능한 연산의 범위가 늘어날 수 있다.)

반복문의 반복 횟수는 선형 반복(1부터 n까지 반복)시 \(O(n)\)을 가진다. 그리고 반복문 내에 있는 연산 횟수를 전부 곱한다. 다음 코드를 봐보자

  
for(int i = 0; i < n; i++){
    ...
    for(int j = 0; j < n; j++){
        ....
    }
}

해당 코드는 반복문 내에 반복문이 존재한다. 따라서 시간복잡도는 \(O(n \times n) = O(n^2)\)이 된다. 다음 코드를 봐보자

  
for(int i = 0; i < n; i++){
    ...
    for(int j = i + 1; j < n; j++){
        ...
    }
}

방금 전과 유사한 코드지만 반복 횟수를 계산해보면 \(\frac{n(n + 1)}{2}\)가 나온다. 따라서 시간복잡도는 \(O(n^2)\)이 된다. 마지막 코드를 읽어보자.

최고차항의 상수는 1로 취급하고 나머지는 다 버린다. 곱연산이 아닌 합연산은 최고차항을 제외하고 다 버린다.

  
for(int i = 0; i < n; i++){
    cout << upper_bound(v.begin(), v.end(), 1) << "\n";
}

반복문 내에 이분탐색 코드가 들어가있다. 따라서 해당 코드의 시간복잡도는 \(O(nlogn)\)이 된다.

값의 범위 별 가능한 알고리즘의 경우

값의 범위	시간복잡도	대표 알고리즘
\(n \leq 10\)	\(O(n!)\)	Bruteforce
\(n \leq 20\)	\(O(2^n, n^2\times 2^n)\)	Bitmask DP
\(n \leq 50\)	\(O(\sqrt{2}^n)\)	MITM
\(n \leq 500\)	\(O(n^3)\)	Floyd-Warshall
\(n \leq 5,000\)	\(O(n^2)\)
\(n \leq 100,000\)	\(O(n\sqrt{n}, nlog^2n)\)	Mo’s
\(n \leq 1,000,000\)	\(O(nlog n)\)	Sorting
\(n \leq 10,000,000\)	\(O(n)\)	DFS, Tree traversal
\(n \geq 10,000,000\)	\(O(log n), O(1)\)	Binary Search, Hashing

n의 범위를 확인하고 알고리즘 방향성을 잡고 가는 것 또한 좋다.

Problem Solving, Baekjoon

This post is licensed under CC BY 4.0 by the author.