PS에서 자주 사용하는 코드들 모음(C++, Python)

  이 글은 PS연습을 위해 자주 쓰는 코드들을 정리한 글입니다. competetive coding 대회같은 경우는 team note에 이같은 코드들을 정리해서 갈 수 있지만, 취업을 위한 코딩 테스트는 그런 거 없이 모든 코드를 완전 암기해야 하기에 이 포스트를 작성하였습니다.

---

1. 입출력

CLI 환경에서 입력과 출력이 어떻게 들어가는지 그 원리만 알아도 PS 실력 향상에 큰 도움이 된다.

전공생의 경우 CLI 환경도 많이 다루고, 쉘 프로그래밍을 통해 터미널에서 입력받는 원리도 금방 알게 되지만, 비전공자의 경우 그렇지 못하다. CLI 환경에서 입출력을 이것저것 해보며 감을 잡아야 나중에 출력문을 이용한 임시 디버깅도 금방하고, 출력의 형태를 보고 코드에서 어떤 게 문제인지 쉽게 알 수 있다.

1-1. 빠른 입출력

코딩 테스트의 시간 제한은 구현한 알고리즘의 시간 복잡도를 작성자가 잘 최적화했는지 평가하기 위해 존재한다(메모리 제한은 공간복잡도).

그런데 그런 구현과 상관없이 언어 자체 환경 때문에 입력과 출력의 시간이 오래 걸려 시간을 잡아먹는다면 어떨까? 입출력은 언어 자체에서 구현된 입력/출력 함수를 써야 하는데, 이 함수들이 느려서 시간을 잡아먹는다면 굉장히 억울할 것이다.

때문에 시간 제한이 좀 빡빡하게 걸려 있는 문제들을 풀기 위해선 빠른 입출력 설정이 사실상 필수이다. 빠른 입출력이 필요없는 문제에서도, 이 짧은 코드를 추가하는데에 손해는 없으므로 코테나 CP 환경 상에서 빠른 입출력을 위해 항상 아래와 같이 주로 작성한다.

1. C Stream과 C++ Stream 동기화 끊기
2. C++의 입력과 출력이 묶여있는 부분 해제

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0); // 1
  cin.tie(0); cout.tie(0);      // 2

  /*
  여기에 문제를 푸는 코드를 작성합니다. 
  */

}

C++의 입출력 스트림은 기본적으로 C 스트림과 동기화되어 있다. 이를 해제하고, cin과 cout이 서로 묶여있는 걸 풀면 훨씬 빠른 입출력이 가능하다.

단, 이렇게 하면 반드시 모든 입출력을 cin, cout으로 처리해야 한다(scanf, printf 사용불가).

1. 기본 입력 객체(input)를 sys.stdin.readline으로 대체
2. 기본 출력 객체(print)를 sys.stdout.readline으로 대체

import sys

# 빠른 입력
input = sys.stdin.readline
data = input().rstrip()


# 빠른 출력
print = sys.stdout.write
print('hello')
print('안녕')

파이썬의 경우 설정을 바꾼다기보단 입출력에 사용하는 함수(객체)를 변경하는 식으로 진행된다.

이렇게 대체하면 입력받는 형태가 달라지므로, strip 등 문자열을 다루는 작업을 잘 수행해야 한다.

1-2. 입출력 형태 별 코드

주어지는 입력의 형태에 따라 어떻게 처리해야 하는지가 다 달라진다. 크게 아래처럼 구분이 가능하다.

1) 입력 1개 처리

int x;
cin >> x;

x = input()

2) 공백으로 구분 된 여러 입력 받기

int x, y;
cin >> x >> y;

data = list(map(int, input().split()))

3) 여러 줄로 구분된 입력 받기

int arr[10];
int N;
cin >> N;
for(int i = 0; i < N; i++) cin >> arr[i];

n = int(input())  # 첫 번째 줄에서 입력 받는 숫자 개수
data = [input() for _ in range(n)]

4) 배열 형태의 입력 받기(여러 줄, 여러 입력)

int arr[10][10];
int N;
for(int i = 0; i < N; i++) {
  for(int j = 0; j < N; j++) {
    cin >> arr[i][j];
  }
}

n = int(input())  # 첫 번째 줄에서 입력 받는 숫자 개수
data = [input() for _ in range(n)]

2. 자료구조

C++에서는 STL에서 구현된 자료구조 클래스를 이용해서 구현합니다.

1) Stack

#include <stack>
stack<int> st;

st.push()
st.pop()
st.top()

2) Queue

#include <queue>
queue<int> q;

q.push()
q.pop()
q.top()

3) Deque

#include <deque>
deque<int> dq;
dq.push_front();
dq.push_back();
dq.pop_front();
dq.pop_back();

3. 알고리즘