Codeforces등 대회 전에 읽어보려고 두서 없이 쓴 글..
요즘 실수 하는 것들
문제를 정확히 안봄, O(n)계산으로 충분히 정확한 방법을 생각안함.
답이 long long인지 처음에 생각하기
헤더파일
#include <bits/stdc++.h> : 모든 헤더포함
vector, algorithm, stack, set, tuple, queue, map,
memset, memcpy 등 사용할때 컴파일 에러 주의
visual studio는 자동호출 하지만 cstring 호출 필요
string와 cstring, string.h의 차이점 인지
시간
입력속도 비교
https://www.acmicpc.net/blog/view/56
최대입력개수가 100만개 이상일 경우
- cin, cout, cout<<endl;은 자제
- endl은 개행문자를 출력할 뿐만 아니라 출력 버퍼를 비우는 역할까지 합니다. 그래서 출력한 뒤 화면에 바로 보이게 할 수 있는데, 그 버퍼를 비우는 작업이 매우 느립니다. 게다가 온라인 저지에서는 화면에 바로 보여지는 것은 중요하지 않고 무엇이 출력되는가가 중요하기 때문에 버퍼를 그렇게 자주 비울 필요가 없습니다. 그래서 endl을 '\n'으로 바꾸는 것만으로도 굉장한 시간 향상이 나타납니다.
- cin.tie(NULL)은 cin과 cout의 묶음을 풀어 줍니다. 기본적으로 cin으로 읽을 때 먼저 출력 버퍼를 비우는데, 마찬가지로 온라인 저지에서는 화면에 바로 보여지는 것이 중요하지 않습니다. 입력과 출력을 여러 번 번갈아서 반복해야 하는 경우 필수적입니다.
- ios_base::sync_with_stdio(false)는 C와 C++의 버퍼를 분리합니다. 이것을 사용하면 cin/cout이 더 이상 stdin/stdout과 맞춰 줄 필요가 없으므로 속도가 빨라집니다. 단, 버퍼가 분리되었으므로 cin과 scanf, gets, getchar 등을 같이 사용하면 안 되고, cout과 printf, puts, putchar 등을 같이 사용하면 안 됩니다.
- scanf, printf, ‘\n’으로 대처
- 결론적으로는 편리함 때문에 cin, cout을 쓰기 보다는 scanf와 printf를 사용하면 해결될 문제입니다. 그리고 좀 더 빠르게 하겠다면 글자 하나씩 입출력하는 함수들이 더 빠릅니다.(getchar, putchar 등등) // endl 약 10배 느림
- ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
- 을 쓰는경우 standard input output와 혼합할경우 버퍼가 꼬임, 싱글스레드만 가능 >> 실무불가능 >> 오로지 알고리즘
cin, cout,endl 등은 입력과 출력이 많을시에
속도가 많이 느려지므로 사용 주의, 십만건은 약1초
다른 방식 사용 좋음
알고리즘(싱글스레드) 환경에서는 아래 코드로 명시적으로 대처 가능
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
컴파일
런타임에러 경우
- 배열에 할당된 크기를 넘어서 접근했을 때
- 전역 배열의 크기가 메모리 제한을 초과할 때
- 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
- 0으로 나눌 떄
- 라이브러리에서 예외를 발생시켰을 때
- 재귀 호출이 너무 깊어질 때
- 이미 해제된 메모리를 또 참조할 때
- main함수가 0이 아닌 수를 반환했을 때
https://www.acmicpc.net/help/rte
런타임에러
STL함수
벡터 및 튜플
qsort 구조체
mutiset 등 STL 사용법
BST 등과 같은 자료구조와 STL의 사용법, 사용시기, 시간복잡도
순열
표준라이브러이인 STL에 포함된 next_permutation() 모든 순열을 순서대로 생성해줌.
itoa(a, arr, n) // 정수a를 n진수로 char arr[]에 저장
atoi는 표준이 아님.
>> 고로 sprintf로 대체
- sprintf(str,"%d",value) converts to decimal base.
- sprintf(str,"%x",value) converts to hexadecimal base.
- sprintf(str,"%o",value) converts to octal base.
문자열 나누기 = strtok
/* strtok example */
#include <stdio.h>
#include <string.h>
int main ()
{
char str[] ="- This, a sample string.";
char * pch;
printf ("Splitting string \"%s\" into tokens:\n",str);
pch = strtok (str," ,.-");
while (pch != NULL)
{
printf ("%s\n",pch);
pch = strtok (NULL, " ,.-");
}
return 0;
}
Union - Find
#include <cmath> abs(int num) 절대값
find union 개념
for (int i = 0; i < MAX_SIZE; i++)
root[i] = i;
int findset(int x) {
if (root[x] == x) {
return x;
}
else {
//경로압축! 근데 여기서 return 안하면 n=100,000에도 메모리초과
return root[x] = findset(root[x]);
}
}
void unionset(int p, int q) {
root[q] = p;
}
자료형
long long(:= __int64) 8byte -9*10^18 ~ 9*10^18
int 4byte -20억 ~ 20억
pair<int, int> // #include <iostream>
tuple<int, int> //#include <tuple>
upper_bound, STL, 하한선, 상향선을 이진탐색으로 찾음
tuple<int, int, int> res = make_tuple(1, 1, 1); // {1,1,1}
first = get<0>(res), second = get<1>(res), …
set은 모든 원소가 유일하다.
원소의 중복을 허용해야 한다면 multiset 을 사용해야 한다.
연관 컨테이너는 균형 이진 트리를 사용하므로 찾기 연산 (find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그 시간)을 보이며 insert() 멤버 함수를 이용한 삽입도 로그 시간 복잡도를 보인다.
x.lower_bound({first, -inf});
'비교 결과 주어진 값보다 먼저 나오지 않는(not compare less than) 첫 원소'의 iterator를 반환한다.
x.upper_bound({first, inf});
'비교 결과 주어진 값보다 나중에 나오는(compare greater than) 첫 원소'의 iterator를 반환한다.
In these implementations we only care about the first value.
pair<int,int> will compare the first int first, then the second int. We want ALL second integers to work
As for upperbound Na2a uses {first, inf} because we want the value to be greater than first, and {first, inf} is the highest pair with first as its first value. (again, we only care about the first value)
long double 입력 sacanf( "%Lf" &num);
pow반환형은 double..! 크기가 클경우 사용하지 말자.//그냥 쓰지 않는게 베스트
double은 수의 범위가 int정도일때만..
iterator 처럼 애매한 경우, auto 선언
매개변수가 2차원 배열인경우
배열을 포함한 포인터 인경우
포인터를 가리키는 포인터인경우
C++
지역변수와 전역변수 메모리 크기 차이
참고할 알고리즘
재귀함수 사용시에
1. 제한사항
2. 계속할경우
3. 호출인자
등 생각하기
어떤 정보를 재귀함수로 넘길것 인가!
동전의 위치만 바뀌므로 동전의 위치만 넘긴다.
-> 동전의 위치를 전역변수로 저장할 것인지, 인자로 넘길것인지 생각.
인자로 넘길 경우 : 재귀 앞에서만 동전의 위치를 수정
전역변수로 할 경우 : 재귀 앞과 뒤 모두 동전의 위치를 수정
재귀함수
0. 인자구성
1. 정답을 찾음
2. 불가능한 경우
3. 다음 경우 호출
이진탐색
예시1) 풍선공장
https://www.acmicpc.net/blog/view/55
숫자놀이
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cstdlib>
#include <iostream>
using namespace std;
long long dif = 0; //자료형 주의..넘칠수있
long long ans = 0;
long long n = 0;
int visited[10] = { 0, };
//n자리수 최대값
long long nMax(int num) {
long long ans = 0;
for (int i = 0, j=9; i < num; ++i, --j) {
ans *= 10;
ans += j;
}
return ans;
}
void dfs(int depth, int num, int sum) {
sum = 10 * sum + num;
if (depth == n) {
long long diff = num - sum;
if (diff < 0) dif *= -1;
if (dif > diff) {
dif = diff;
ans = sum;
}
}
for (int i = 0; i <= 9; ++i) {
if (visited[i] == 1) continue;
visited[i] = 1;
dfs(depth + 1, i, sum);
visited[i] = 0;
}
}
int main(void) {
__int64 num;
cin >> num;
if (num >= 9876543210) cout << "9876543210"; // 십억 = 십초 f(n)으로는 불가능.
else {
n = (long long)num;
int count = 1; //자릿수
while ((n /= 10) != 0) count++;
n = (long long)num;
if (count > 1) { //2자리수이상10의자리수이하일경우
dif = num - nMax(count - 1);
ans = nMax(count - 1);
for (int i = 1; i <= 9; ++i) {
visited[i] = 1;
dfs(1, i, 0);
visited[i] = 0;
}
cout << ans;
system("pause");
return 0;
}
else { //1의자리수일경우 걍출력
cout << num;
system("pause");
return 0;
}
}
//for (int i = 1; i < 11; ++i) cout << nMax(i)<<endl;
system("pause");
return 0;
}
/*
만들수 있는 경우의수
10자리수
9*9*8*7*6*5*4*3*2*1 = 3,265,920 삼백만!
9자리수
9*9*8*7*6*5*4*3*2
8자리수
9*9*8*7*6*5*4*3
7자리수
9*9*8*7*6*5*4
..
2자리수
9*9
1자리수
9
입력된 수가 n의자리 수일경우 n-1자리수의 최대값 또는 n자리수 조합에서 뽑음.
*/
dp문제 입첼린저 : https://www.acmicpc.net/problem/14628
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
int visited[101][101][101];
//int skilcount[101];
pair<int, int> skil[101];
/*피가 hp(0~100)일때 x(0~N-1)번째 스킬을 k(0~100)번썻을경우 최소 마나*/
int dp(int hp, int x, int k) {
int minMana = 1e9;
int usedMana = k*skil[x].first + K*k*(k - 1) / 2;
if (x >= N) return minMana;
if (visited[hp][x][k] != 0) return visited[hp][x][k];
hp -= skil[x].second*k;
if (hp < 0) return minMana;
if (hp == 0) return usedMana;
if (x >= N - 1) return minMana;
for (int i = 0; i <= hp / skil[x+1].second + 1; ++i) {
minMana = min(minMana, dp(hp, x + 1, i));
}
visited[hp][x][k] = minMana + usedMana;
return visited[hp][x][k];
}
int main(void) {
cin >> N >> M >> K;
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
skil[i] = make_pair(x, y);
}
int minMana = 1e9;
for (int i = 0; i <= M / skil[0].second + 1; ++i) {
minMana = min(minMana, dp(M, 0, i));
}
cout << minMana;
//system("pause");
}
dfs구조
void dfs() {
if(정답) {
연산
} else {
dfs()
}
void dfs() {
if(정답) {
연산
} else {
arr[] =
dfs()
arr[]==
}
void dfs() {
if(정답) {
연산
} else {
for() {
arr[] =
dfs()
arr[]==
}
}조합
int combination(n,r)
{
if( n == r ){
int i;
for(i=0;i<n;i++){
flag[i] = 1;
}
for(i=0;i<length;i++){
if( flag[i] == 1 ) printf("%d ",data[i]);
}
for(i=0;i<n;i++){
flag[i] = 0;
}
printf("\n");
return 0;
}
if( r==1 ){
int i,j;
for(i=0;i<n;i++){
flag[i] = 1;
for(j=0;j<length;j++){
if( flag[j] == 1 ) printf("%d ",data[j]);
}
flag[i] = 0;
printf("\n");
}
return 0;
}
flag[n-1]=1;
combination(n-1,r-1);
flag[n-1]=0;
combination(n-1,r);
}#include <cstdio>
#include <vector>
using namespace std;
char ch[10] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
void printPicked(vector<int>& v) {
printf( "(");
for (int i = 0; i < v.size(); ++i) printf("%c, ", ch[v[i]]);
printf(")\n");
}
// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
// 기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if (toPick == 0) { printPicked(picked); return; }
// 고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
// 이 단계에서 원소 하나를 고른다.
for (int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}
vector<int> vector1;
int main() {
pick(5, vector1, 3);
}
피사노 주기
int pisano_period(int num) {
int cnt = 0, a = 0, b = 1;
do {
int temp = b;
b = (a + b) % num;
a = temp;
cnt++;
} while (a != 0 || b != 1);
return cnt;
}유클리드 알고리즘>> 최소공배수(a,b) == (a,b%a)
for (;;) {
temp1 = max(a, b);
temp2 = min(a, b);
a = temp1;
b = temp2;
if (a%b == 0) break;
a %= b;
}
확장 유클리드 알고리즘 >> a/b == a*b^-1
ex) 31^-1 mod 576
ax + by = gcd(a, b)
31x + 576y = 1 >> x : 223, y : -12
역원의 필요성 >>
사소한팁
O(1)만에 자료를 찾는 방법
어떤 배열에서 크기가 매우 크지 않은 경우
모든 배열의 내용을 어딘가에 기록을 해놓는다면
O(N)이 아니라 O(1)만에 찾을 수 있다.
vector arr(n), position(n);
for(int i=0; i
k라는 수는 arr배열의 몇번째 에 있지? -> position[k]
-----------------------------------------
디버깅 시에 중간 씩 출력해보면서 상태 이해하기
-----------------------------------------
while(scanf("%d %d %d", &x, &y, &z) == 3)
으로 세개가 입력될 동안만 반복 표현 가능
-----------------------------------------
비쥬얼 C++ cmd 바로 꺼질떄, 프로젝트-속성-링커-시스템-하위시스템-콘솔
C/C++ - 일반 - SDL 검사
링커 - 시스템 - 하위시스템 - 콘솔
디버깅 - 명령인수 - <input.txt >output.txt
-----------------------------------------
vector<vector<int> > board; 이중 배열 대신
방법0. 내가 가장 편하게 생각하는 방법
n*m 이중 배열 만들기
#include<vector>
using namespace std;
vector<vector<int>> arr; // arr 이중 벡터 선언
arr.assign(n, vector<int>(n, 0)); // arr[n][n] 할당, 0으로 초기화
방법1.
n*n 이중 배열 만들기
#include<vector>
vector<vector<int>> arr;
for(int i=0; i<n; i++){
vector<int> element(n);
arr.push_back(element);
}
방법2.
행과 열 사이즈 다른 배열 만들기
#include<vector> //int arr[6][5] 배열 선언. 0으로 초기화
vector< vector<int>> arr(6, vector<int>(5,0));
실수할 수 있는 경우
코딩 환경
main 안에 int arr[백만]선언 했을때 비쥬얼스튜디오에서는 실패지만 저지사이트에서는 정답가능 // 메모리 크기가 다르므로
-----------------------------------------
입력
scanf(“%d”, &num);
scanf(“%c”, &ch);
이때 숫자를 받은후 엔터나 NULL문자가 나오므로 중간에 getchar()필요
scanf(“%d”, &num);
getchar();
scanf(“%c”, &ch);
문자열을 포문으로 받을때 한줄씩 끊어지면 이때도 getchar필요!
-----------------------------------------
연산자 우선순위 및 결합방향
if (board[ny][nx] += delta > 1) istrue = false;
틀린코드가 될 수 있음.
if ((board[ny][nx] += delta) > 1) istrue = false;
명시적으로 괄호에 연산자 넣기.
-----------------------------------------
변수 이름
세로 가로 변수를 받는 경우, m n등으로 정의하지 않고
세로 h, y, 가로 w, x 로 정의하기 //m, n등으로 정의 할 시에 햇갈림. 순서도 중요.
1. 세로, 가로로 주어질때 : h, w
2. y축, x축으로 주어질때 : y, x
------------------------------------------
char atoi에 대해서 :
string atoi(string.c_str());
int num = ch - '0'; // 좋지 않은 방법
// 이 방법으로 문자를 수로 변환하는 건 0~9만 가능하며, 이외의 수가 들어갈 경우, 디버깅이 쉽지 않음.
ex) for (int i = 2; i < q.size(); i++) { x = x * 10 + q[i] - '0'; }
int num = stoi(string.substr(n)); // 좋은 방법.
substr(pos, count) [pos, pos+count) 까지 추출하는 함수, O(n)의 시간이 걸림.
------------------------------------------
실행환경 :
일반적으로 로컬 콘솔 창 실행시간보다 솔루션 서버의 실행시간이 더 빠르다. //성능차이
로컬에서 4~10초 여도 2초제한 통과 가능
------------------------------------------
<cstdlib> qsort 함수 : 최악의 경우 시간복잡도 O(N^2)
<algorithm> sort 함수 : 최악의 경우 시간복잡도 O(NlogN)
고로 sort함수를 쓰면 된다. qsort는 함수포인터를 사용해야 하므로, 비교함수 사용을 주의
int compareMyType (const void * a, const void * b) {
if ( *(MyType*)a < *(MyType*)b ) return -1;
if ( *(MyType*)a == *(MyType*)b ) return 0;
if ( *(MyType*)a > *(MyType*)b ) return 1;
}
/* qsort example */
#include <stdio.h> /* printf */
#include <stdlib.h> /* qsort */
int compare (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int main () {
int values[] = { 40, 10, 100, 90, 20, 25 };
qsort (values, 6, sizeof(int), compare);
for (int n=0; n<6; n++)
printf ("%d ",values[n]);
return 0;
}
int compare_string(const void *first, const void *second) {
// return (strcmp((char*)first, (char*)second));
// qsort의 비교 함수에는 배열의 원소가 아니라
// 배열 원소를 가리키는 포인터가 들어옵니다.
// 이중 포인터를 쓸 때는 정말 조심.
return (strcmp(*(char**)first, *(char**)second));
}
이외 참고
코드포스 사이트
C++ 유용한 문법
https://velog.io/@hgmhc/CC-STL-%EB%AA%A8%EC%9D%8C%EC%A7%91
자주 틀리는 요인
https://www.acmicpc.net/blog/view/70
백준 채점
https://www.acmicpc.net/blog/view/55
주요 대회 정리
https://haeulnam.github.io/algorithm/2019/02/01/03-소개-3/
환경설정 꿀팁
https://bloodstrawberry.tistory.com/5
'Algorithm > Basic' 카테고리의 다른 글
| 프로그래머스 레벨 1 ALL SOLVED, 오답정리 (0) | 2022.06.01 |
|---|---|
| 다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제) (0) | 2022.04.17 |
| 트리(Tree) (0) | 2021.02.14 |
| 그래프(Graph) (0) | 2021.02.05 |
| 정렬(Sorting), Stable_Sorting (0) | 2021.01.31 |
