포스트

PS Memo

게시 업데이트
Preview Image
By mascari4615
9 분읽는 시간
PS Memo

공부

  • 코테 -> CS의 기본

  • 더 빠른 코드, 힙/스택

  • 정답율 높은 문제 풀기 50% / 35%, 낮은건 본질에서 벗어나 꼼수/함정이 들어간 문제일 가능성 높음
  • 다른 사람 풀이 찾아보기, 정답이 없으니까
  • 반복해서 풀기
    • Like 내신 수학
    • 비슷한 문제를 풀기 (이전 문제와 연결짓기, 이후에도 응용하기)
      • 어떻게 풀었는지 기억하려면, 응용하려면 반복 학습이 중요하다
  • 시간복잡도
    • 1초에 몇 번 연산하는가?
    • 데이터 수를 보고 적절한 시간 복잡도의 알고리듬 떠올리기 (어떤 알고리듬을 쓸지보다도 거름망)
  • 손코딩 먼저 하기 (방법론을 먼저)
    • 시간복잡도 중심으로 알고리듬과 자료구조를 공부한다

Thinking

귀납적으로 푼다.

컴퓨터는 거짓말을 안한다.
내 코드가 틀렸거나, 엣지 케이스에서 틀렸거나.

코딩 테스트와 개발은 다르다
클린코드를 짜는게 아니라, 제한된 시간안에 내가 편한 방법으로 정답을 맞추는 게 더 중요하다.

C++

C++ 실수의 성질

  • 실수를 저장/연산 과정에서 반드시 오차가 발생한다.
    • 실수는 double을 쓸 것
    • 실수를 비교할 때 부호를 쓰지 말 것 (마찬가지로 오차)
  • 보통 실수를 써야하는 문제라면 오차범위를 알려주는데, 없으면 정수만으로 풀 수 있는 문제일 가능성이 높다.

  • if (abs(a-b) - 1e-12) (10-12)

  • double에 long long을 담지 말 것 (범위로 인한 오차)

C++ 공백을 포함한 문자열 입력 받기

C의 scanf, C++의 cin 둘 다 공백을 포함한 문자열을 입력 받기 어렵다.
대신 아래 3가지 방법을 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13

// 1. scanf의 옵션
char a1[10];
scanf("%[^\n]", a1);

// 2. gets 함수 (보안상의 이유로 C++14 이상에서는 제거됨)
char a2[10];
gets(a2);
puts(a2);

// 3. getline 함수
string s;
getline(cin, s);
cout << s;

C++ 최적화

sync_with_stdio

cin cout을 쓸 때 시간초과가 날 수 있다.
C Stream(scanf, printf)과 C++ Stream(cin, cout)의 동기화를 끊어준다.

1

ios::sync_with_stdio(false);

왜 Why?
C Stream과 C++ Stream을 섞어 쓴다면, 순서대로 실행 되는게 직관적이기 때문에 서로 동기화를 시켜주고 있다.
C++ Stream만 쓰는 거면 굳이 동기화 할 필요가 없으니, 시간적 이득을 얻기 위해 동기화를 끊어주는 것이 좋다.

Visual Studio 2017-2019 에서는 써도 강제적으로 동기화를 시켜버린다.
백준 채점 서버는 gcc라 차이가 있다.

1
2
3

cout << "1";
printf("2");
cout << "3";

cin.tie

1

cin.tie(nullptr);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 입출력 버퍼
// 버퍼에서 모았다가 입력/출력

for (~)
{
    cin >> a >> b;
    cout << a + b << '\n';
}

// 이것도 순서대로 나오는 게 직관적이니까
// 지본적으로는 cin 명령을 수행하기 전에 cout 버퍼를 비워준다 (출력을 한다)

// 근데 온라인 채점 서버는 그냥 출력값만 보고 채점을 한다
// 굳이 cin 명령을 수행하기 전에 cout을 비워주지 않아도 됨
// 그걸 끊어주는

endl 대신 ‘\n’

endl는 개행 문자(\n)를 출력하고 버퍼를 비워준다.
버퍼를 비워줄 이유가 없으니까 대신 직접 개행 문자(\n)을 출력하는 것이 좋다.

1
2
3

cout << endl;
// 대신
cout << '\n';

STL을 함수 인자로 넘길 때 참조로 넘기기

C++에서 STL을 함수 인자로 넘길 때, 기본적으로 복사해서 보낸다.
STL을 함수 인자로 넘기고자 할 때에는 참조로 넘기는 것이 좋다.

C++ Templete

1
2
3
4
5
6
7
8
9

#include <bits/stdc++.h>
using namespace std;

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

메모

_

Backjoon

출력 마지막에 공백, 줄바꿈이 추가로 있어도 상관이 없다

  • Baekjoon 18110 - ‘solved.ac’ (2023-12-13. 10:02)
    • 반올림 (int)(0.5 + n);
    • C++ 반올림, round() - <cmath>
    • C++ 우선순위큐, priority_queue - <queue>
  • Baekjoon 1439 - ‘뒤집기’ (2024-02-17. 20:27)
    • Replace, Split 0Count = Replace("0", " ").Split.Length
  • Baekjoon 1926 - ‘그림’ (2024-02-23. 04:11)
    • 폰트합자로 인한 =, == 실수를 조심하자
    • 아놔
  • Baekjoon 2178 - ‘미로 탐색’ (2024-02-23. 06:06)
    • char[]로 입력받을지, string으로 입력받을지
  • Baekjoon 7569 - ‘토마토’ (2024-02-24. 18:56)
    • C++ tuple
  • Baekjoon 15683 - ‘감시’ (2024-03-01. 23:19)
    • C++ #define x first
    • 오타!
    • 아놔!
    • 함수 네이밍 OOB: OutOfBounds, 배열 범위 초과하는지 확인하는
    • C++ tie(x, y) = somePair;
    • C++ 다차원 배열 복사 copy(&source[0][0], &source[0][0] + (n * m), &dest[0][0])
  • Baekjoon 18808 - ‘스티커 붙이기’ (2024-03-05. 04:54)
    • C++ Swap sawp(x, y)
    • C++ 배열/행렬 시계방향 회전 B[x][y] = A[xLen-1-y][x]
    • 함수 네이밍 ~able
  • BFS, 요소 넣을 때 visit = true 해주기

유형

  • 골드 3~4 안정적으로, 어떻게 푸는 지 바로 생각날 정도로, 외울 정도로, 어려운 게 있으면 더 풀어

  • 백준 Class 난이도 별로

  • 분야: 못해도 11강, 그리디, 탐색 (완전 탐색/BFS/DFS), 그래프, DP, 백트래킹/시뮬레이션, 좀 더? (크루스칼, 다익스트라/최소신장트리, 트라이)

  • 자료구조: 해싱, 파싱, 스택, 힙, 트리, 문자열

  • 프로그래머스: 42895, 기출

  • 코드포스 (블루)

  • 하
    • 문자열 조합
    • DFS/BFS
    • 시뮬레이션 (스택, 큐, 덱)
    • 투포인터
    • 이분탐색
  • 중
    • 위상정렬
    • MST / 크루스칼 + 프림
    • 그리디
    • 백트래킹
  • 상
    • DP (가끔 수학과 엮여서 출제)
    • 트라이 / KMP
    • 다익스트라
  • X
    • 라운드로빈 (스케쥴링)
    • 삼항트리
  • ?
    • 세그먼트 트리
    • A*

공부 주제

컴퓨터, 알고리즘, PS
PS CPP
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.