알고리즘 하면서 공부해야 할 것들 & 고쳐야 할 것들 & 알면 좋은 것들 ** TODO

* 알고리즘/DB/AI/OS/아키 수업 들었던 과제 / ppt / 정리한 것 글로 작성해 보기
* 기하 - 신발끈 공식

* 작성중인 정렬 게시글(insertion sort, bubble sort, selection sort, count sort, radix sort, quick sort, merge sort, heap sort)
* sliding window, two pointer, meet in the middle

* dp + LIS + trackback

* backtrack

* DFS 코드 정립

* vector erase vs remove
* KMP 알고리즘

* euler tour, path, circuit

* 백준 단계별 위상정렬까지 끝나면 DP나 누적합, 시뮬레이션 등 문제별 풀이 하면서 해 보자.

* DP랑 시뮬레이션 좀 약한 것 같다... 연습하자

 

 

대목차 제목1, 3칸

중목차 제목2, 2칸

소목차 제목3, 1칸

내용 본문2

 

 

 

****** 문제를 잘 읽자. ******

전역변수 사용에 대해 거부감을 줄이자. 쓰면 편하다.

언제나 자료형 크기와 입력 데이터의 overflow가 발생하지 않는지 유의하자.

index가 내가 의도한 대로 잘 동작하는지 생각하고 적자.

함수를 하나 쓰면, 그 함수가 잘 동작하는지 확인을 해 보자!

brute-force로 풀리지 않는다면 parameteric search처럼 문제를 바꾸어 생각해 보자!

 

 

 

C++ 문법 관련

입/출력 속도조절

 C++의 cin, cout은 scanf, prinf보다 속도가 느리다.

 c++은 stdio와 iostream을 동기화시켜서 딜레이가 발생하는데, ios_base::sync_with_stdio(false);의 경우 동기화를 꺼서 성능향상을 도모하는 코드이다. stdio와 iostream의 동기화를 해제했기 때문에 stdio에 있는 scanf, printf 등등의 함수를 사용하면 엉뚱한 결과가 나오게 된다.

 cin.tie(null)은 원래는 묶여있는 cin과 cout의 묶음을 풀어주는 것이다. 그렇기 때문에 속도는 더 빨라지지만 cin과 cout의 순서가 바뀔 수도 있다(cout의 버퍼에 따라서)

 마지막으로 cout<<endl;의 경우에는 버퍼 처리까지 해 주기 때문에 시간이 오래 걸리므로 개행문자 \n를 더 사용하자.

cin.tie(0);
cout.tie(0);
std::ios_base::sync_with_stdio(0);
cout<<'\n';

 

 

Range-based for loop 값 변경

 충격적이다... range for문은 값을 변경해도 변경되지 않는다. 예를 들어 아래와 같은 코드를 실행해도 arr에서 값이 1인 element의 값은 그대로 1이다. 왜냐하면 range loop에서 값은 복사된 값이기 때문이다.

for(int elem : arr){
    if(elem == 1) elem = 0;
}

 

 이를 방지하기 위해 reference를 사용하면 된다.

for(int &elem : arr){
    if(elem == 1) elem = 0;
}

 

 

나눗셈

나눗셈 조금 특이하다. 내가 아는 상식과 조금 다르니, 구현 시 주의가 필요할 것이다.

 a / b에서 a, b가 음수든 양수든 상관없이 abs(a) / abs(b)가 몫이다. a, b의 부호가 다를 경우 부호는 음수, 같은 경우 양수이다. 이 몫을 q라고 하자.

 나머지는 a = qb + r이므로 r = a - qb를 통해 계산한다.

 

​	수식	몫	나머지
양수 / 양수	10 / 3	3	1 (= 10 - 3*3)
음수 / 양수	-10 / 3	-3	-1 (= -10 - (-3)*3)
양수 / 음수	10 / -3	-3	1 (= 10 - (-3)*(-3))
음수 / 음수	-10 / -3	3	-1 (= -10 - (-3) * 3)

 ex)

 

큰 수를 나눌 때(a/b라고 생각하자) 수가 크면 클수록 오차가 커진다. 그리고 순서도 중요하다. 예를 들어 a/b * x를 하면 a/b의 오차가 x배 되기 때문에 많은 오차가 생긴다. 따라서, 최대한 나눗셈 연산을 뒤에 하나. a*x / b처럼.

 

 

소수인지 판별하기

prime number가 아니라 decimal 소수다. 소수점이 붙는. 형변환을 통해 비교하면 된다.

double x = 3.14;
x == (int) x; // false

double x = 3;
x == (int) x; // true

 

 

 

문자열​ String

 string += s를 하고 reverse를 할 바에는 차라리 string = s + string을 해 보자.

 parsing해서 저장할 일이 있으면 sstream과 getline을 사용하고, 문자열 형태가 정해진 것을 입력해야 한다면 ss>>input을 이용해 보자.

 

 

 

​알고리즘

홀짝 판별

 홀짝 판별에서 %2를 하는 방법도 있지만 &1처럼 비트 연산도 할 수 있다.

 

 

​시간복잡도

 시간복잡도에 따른 입력 크기 : 1초에 1억 번 연산한다고 생각하자.
 - O(nlogn) : 최대 5백만,
 - O(n^2) : 최대 1만,
 - O(n^3) : 최대 500,
 - O(2^n) : 최대 20,
 - O(n!) : 최대 10.

 

 또, DFS의 경우 재귀가 4000번 이상 반복된다고 판단되면 다른 방법(BFS 등)으로 푸는 게 좋다.

 

 

소수 판별

 에라토스페티쉬 문제집도 참고해 보자.

 

 

정렬 시 Strict Weak Ordering

 정렬함수를 작성할 때는 조금 귀찮더라도, a와 b를 비교할 때 <, ==, >를 확실하게 표기하는 게 정확한 것 같다.

 추가적으로, comp 함수가 true이면 첫 번째 인자(a)가 두 번째 인자(b)보다 앞에 있다고 생각한다. 그래서 내림차순 정렬이면 a > b로, 오름차순 정렬이면 a < b로 하면 된다.

 

 

행렬 계산과 좌표평면 계산

 row, col(행렬)로 생각하면 row는 세로줄, col이 가로줄. 그러나 x, y(좌표평면)으로 생각하면 x는 가로줄, y가 세로줄이다. 행렬은 행렬인 걸 알아볼 수 있게 네이밍을 하자.

 

 

2차원 배열에서 상하좌우 이동 시

 좌표평면에서 상하좌우로 이동하는 경우, if나 case를 써서 나누지 말고 아래와 같은 방법을 쓰자. 좀 더 간단하게 이동을 표현할 수 있다.

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

for(int i = 0; i<4; i++){
    x += dx[i];
    y += dy[i];
}

 

 

행렬곱

 IJK 말고 KIJ 순으로 풀어보자.
 - i : arr1의 row idx
 - j : arr2의 col idx
 - k : arr1의 col, arr2의 row idx

 

 

Parametric Search

 정답에 해당하는 값의 범위는 long long으로 2^64 등 매우 큰 값으로 최적화는 가능하지만 시간 초과가 날 것 같을 때 결정 문제(가불 문제)로 바꾸어서 생각해 보자. 이 때 결정 문제로 바꾸었을 때 쉽게 풀릴 수 있으며, 가능한 답이 연속적(자연수)이기 때문에 long long을 이분탐색 시 64번만에 해결 가능하며, parametric search로 풀 수 있음을 유추할 수 있다.