PS Memo
공부
- 코테 -> CS의 기본
더 빠른 코드, 힙/스택
- 정답율 높은 문제 풀기 50% / 35%, 낮은건 본질에서 벗어나 꼼수/함정이 들어간 문제일 가능성 높음
- 다른 사람 풀이 찾아보기, 정답이 없으니까
- 반복해서 풀기
- Like 내신 수학
- 비슷한 문제를 풀기 (이전 문제와 연결짓기, 이후에도 응용하기)
- 어떻게 풀었는지 기억하려면, 응용하려면 반복 학습이 중요하다
- 시간복잡도
- 1초에 몇 번 연산하는가?
- 데이터 수를 보고 적절한 시간 복잡도의 알고리듬 떠올리기 (어떤 알고리듬을 쓸지보다도 거름망)
- 손코딩 먼저 하기 (방법론을 먼저)
- 시간복잡도 중심으로 알고리듬과 자료구조를 공부한다
생각
귀납적으로 푼다.
컴퓨터는 거짓말을 안한다.
내 코드가 틀렸거나, 엣지 케이스에서 틀렸거나.
코딩 테스트와 개발은 다르다
클린코드를 짜는게 아니라, 제한된 시간안에 내가 편한 방법으로 정답을 맞추는 게 더 중요하다.
나아가
특정 문제를 푸는 패턴이 보이고, 이전에는 몰랐던 방식으로 언어의 기능을 활용하는 방법을 이해하기 시작.
데이터 구조를 수반한 복잡한 문제를 풀기 위해 표준 라이브러리와 기능을 효과적으로 사용하는 방법을 배운다.
자신이 풀지 못하고 끙끙대는 문제를 다른 이들이 어떻게 푸는지도 반드시 살펴보길 바란다.
그 문제를 왜 그런 방식으로 풀었는지도 알아내라.
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
- Replace, Split
- 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
- C++
- Baekjoon 15683 - ‘감시’ (2024-03-01. 23:19)
- Baekjoon 18808 - ‘스티커 붙이기’ (2024-03-05. 04:54)
- C++ Swap
sawp(x, y)
- C++ 배열/행렬 시계방향 회전
B[x][y] = A[xLen-1-y][x]
- 함수 네이밍
~able
- C++ Swap
- BFS, 요소 넣을 때
visit = true
해주기
유형
- 골드 3~4 안정적으로, 어떻게 푸는 지 바로 생각날 정도로, 외울 정도로, 어려운 게 있으면 더 풀어
백준 Class 난이도 별로
- 분야: 못해도 11강, 그리디, 탐색 (완전 탐색/BFS/DFS), 그래프, DP, 백트래킹/시뮬레이션, 좀 더? (크루스칼, 다익스트라/최소신장트리, 트라이)
자료구조: 해싱, 파싱, 스택, 힙, 트리, 문자열
- 프로그래머스: 42895, 기출
코드포스 (블루)
- 하
- 문자열 조합
- DFS/BFS
- 시뮬레이션 (스택, 큐, 덱)
- 투포인터
- 이분탐색
- 중
- 위상정렬
- MST / 크루스칼 + 프림
- 그리디
- 백트래킹
- 상
- DP (가끔 수학과 엮여서 출제)
- 트라이 / KMP
- 다익스트라
- X
- 라운드로빈 (스케쥴링)
- 삼항트리
- ?
- 세그먼트 트리
- A*
공부 주제
- VS Release, execution time
- DFS vs BackTracking
- 백준/프로그래머스 문제집, 북마크
- Sweeping
- https://byeo.tistory.com/entry/스위핑-Sweeping
- 사실 새로운 알고리즘이라고 하기도 뭐한데 그냥 순차적으로 효율적인 탐색하는 알고리즘
- https://www.acmicpc.net/problem/2170 스위핑 알고리즘 문제 1
- https://www.acmicpc.net/problem/13334 스위핑 알고리즘 문제 2 (응용)
- https://www.acmicpc.net/problem/3015 재결합으로 갑자기 역주행한 문제, 난이도는 높은데 신박한 문제