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. 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)의 동기화를 끊어준다.

ios::sync_with_stdio(false);

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

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

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

cin.tie

cin.tie(nullptr);

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

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

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

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

endl 대신 ‘\n’

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

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

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

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

🫧 C++ Templete

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

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

💫 메모

---

🫧 _

• 시간 복잡도
  • https://www.acmicpc.net/board/view/146565
• 최적해 : 최고 좋은 해답

🫧 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*

💫 TODO

---

• VS Release, execution time
• DFS vs BackTracking
• 백준/프로그래머스 문제집, 북마크