memo.txt

#기본 코드 작성(c++)

1)표준 입출력
기본적으로 scanf/printf 또는 cin/cout를 사용.
scanf/printf        |    cin/cout
C style             |    C++ style
C 버퍼 사용          |    C++ 버퍼 사용
C++ string 처리 불가 |    C++ string 처리 가능
더 빠름              |    더 느림


2)스트림
https://uxicode.tistory.com/entry/스트림-stream-이란
데이터,패킷,비트 등의 일련의 연속성을 갖는 흐름을 의미한다.
즉 스트림의 정체는 데이터 자체이며, 
이 데이터를 주고받는 여러 장치들을 통일된 방식으로 다루기 위한 가상의 개념이다.

기본적으로 프로그램과 입출력을 담당하는 키보드, 모니터는 연결되어 있지 않음.
이를 단방향으로 연결해주고 둘 사이에서 중계하는 것이 표준 입출력 스트림.
단방향이므로 당연히 입력, 출력 스트림은 따로 있고, 프로그램 시작시 자동 생성.
주로 사용하는 stdin, stdout, stderr 등이 대표적인 표준 입출력 스트림.

스트림은 크게 텍스트 스트림, 이진 스트림 등으로 구별이 가능하다.
표준 입출력 스트림은 텍스트 스트림으로 문자열만을 처리한다.
텍스트 스트림은 공백 및 줄바꿈을 읽어 프로그램의 끝을 알리는데, 
이 때문에 C에서는 공백 문자를 읽어들이려면 추가적인 작업이 필요하다.


3)버퍼
http://tcpschool.com/c/c_io_console
완충기억기. 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 
일시적으로 그 데이터를 보관하는 메모리의 영역. 큐의 일종이다.
이 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 버퍼링이라 부른다.

일반적으로 키보드 입력을 받으면 즉시 이를 변수로 저장하는 것이 아니라,
버퍼가 가득 차거나 개행 등의 특정 상황이 발생하면 
버퍼에 남아있던 지금까지의 입력을 스트림을 통해 전부 넘겨준다.
전송 작업을 적게 할 수 있어 더 효율적이고 입력 과정에서 수정 역시 용이.


*ios_base::sync_with_stdio(false); cin.tie(null);
https://jaimemin.tistory.com/1521
C++와 C에는 각각의 버퍼가 따로 존재하는데, 기본적으로 이 둘은 자동으로 동기화된다.
따라서 cout, cin, scanf, printf를 어떤 식으로 사용하든
멀티 쓰레드 환경에서 출력 순서가 보장이 되게 된다.

그러나 버퍼를 계속 동기화할 경우 입력이 많아지면 부하가 발생해 프로그램이 느려진다.
그런데 printf/scanf 와 cin/cout 를 같이 사용하지 않는다면 동기화가 필요하지 않다.
따라서 이 경우 최적화를 위해 ios_base::sync_with_stdio(false);를 통해
동기화를 해제하여 성능 향상을 꾀하는 것이다.

C,C++에는 입력 또는 출력 버퍼를 강제로 비우는 함수가 있는데,
이에 해당하는 함수가 각각 fflush(), ignore()이다. 편의상 flush 함수로 부른다.
일반적으로 cout/cin을 사용할 때, cin과 cout이 tie가 된 상태인데,
두 stream이 tie 된 상태에서는 입력을 받기 전에 출력 버퍼를 flush하게 된다.
일반적으로 cout은 출력 버퍼가 꽉 차거나 수동으로 flush하지 않으면 출력을 안하는데,
tie가 되어있을 경우 cin이 호출되는 순간 출력 버퍼를 flush 하여
자연스럽게 입출력이 될 수 있도록 하는 것.
그러나 코딩 테스트에서는 한번에 전부 입력을 받으므로 굳이 flush할 필요가 없는데,
코딩 테스트는 입력을 반복적으로 사용하기 때문에 입력의 크기에 비례해 flush가 된다.
이렇게 쓸데없이 발생하는 flush를 줄이기 위해 cin.tie(0)를 사용한다.

동일한 이유로, endl를 코딩 테스트에서는 사용할 이유가 없다.
endl에는 개행뿐 아니라 버퍼를 flush하는 명령도 포함되어 있는데,
상술했듯 코딩 테스트에서는 flush를 할 필요가 없다.


4)printf/scanf

-기본 입출력
int a;
scanf("%d \n",&a); printf("%d \n", a/b);
double b;
scanf("%d %f \n",&a,&b); printf("%f \n", a/b);

-문자열 처리
char * c[100];
scanf("%s \n", c); printf("%s \n",c);//c는 이미 포인터이므로 주소 연산자 x

-공백 포함하여 받기
char * c[100];
scanf("%[^\n]s", c); printf("%s \n",c);
또는
fgets(c,1000,stdin);//1:포인터,2:문자열 최대 크기(마지막 \0 포함),3:파일(스트림)

-소수점 자리 조정
printf("%.9f",a/b);//소수점 9자리까지 표기, 기본은 6자리

-갯수가 정해지지 않은 문자열을 모두 입력받는 방법
char * c[100];
while (scanf("%[^\n]s", c) != EOF){...}
또는
char c[100];
while (fgets(c, 100, stdin)){...}
또는
while (cin >> s >> t){
    ...
}

*cin/cout

-기본 입출력 & 문자열 처리
int a;
cin>>a;cout<<a;
double b;
cin>>b;cout<<b;
string c;
cin>>c;cout<<c;

-공백 포함하여 받기
int a;
string temp;
cin>>a;
cin.ignore();//버퍼 비워서 이상한 값이 안 들어가도록 하기
getline(cin,temp);

-문자열을 배열로
vector<int> split(string s, char del){
    vector<int> res;
    stringstream ss(s);
    string tp;
    while(getline(ss,tp,del)){
        res.push_back(stoi(tp));
    }
    return res;
}

-소수점 자리 조정
cout << fixed;
cout.precision(6); //소수점 6자리까지 표기

-갯수가 정해지지 않은 문자열을 모두 입력받는 방법
string tree;
while(getline(cin,tree)){}


5)bits/stdc++.h
모든 표준 라이브러리를 포함하는 헤더. 하나만 include 하면 된다.
컴파일 시간이 늘어나긴 하나 실행 시간에는 큰 차이가 없으니 
타이핑 시간을 절약하도록 하자.



6)STL(Standard Template Library)
표준 템플릿 라이브러리.
컨테이너(Container, 자료구조) Class / 반복자 / 알고리즘간의 협력에 기반한 템플릿 라이브러리이다.

-regex
regex_replace : string str1 = regex_replace("aaa-bba-ccd-daf", regex("a"), "z");
문자열 내 모든 문자 치환.

https://boycoding.tistory.com/124







#시간복잡도, 공간복잡도
시간복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
공간복잡도 : 문제를 해결하는데 필요한 공간과 입력의 함수 관계.


1)점근 표기법
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법.
대표적으로 다섯가지 표기법이 쓰이나,
빅오 표기법이 압도적으로 많이 쓰인다.
빅오 표기법은 수식의 계수와 낮은 차수의 항을 제외시키는 방법이다.
기호로는 O(x)와 같이 표기하며 x는 한개 혹은 그 이상의 변수로 이루어진 식이다.
ex) O(5N^2+3N)=O(N^2)

크기 n이 커질수록 가장 계수가 높은 항을 제외한 나머지 항과 계수는 
전체 값에 영향을 주지 못한다. 따라서 이를 제외하고 비교하는 것이다.
식의 값에 따라 상수항이 나오면 상수 시간 알고리즘,
로그 함수로 표현되면 로그 시간 알고리즘,
1차항을 가지면 선형 시간 알고리즘,
2차 이상의 계수를 가지면 다항 시간 알고리즘,
지수함수로 표현되면 지수 시간 알고리즘 등으로 표현한다.


2)시간복잡도 수식화
단순 비교, 대입, 사칙 연산을 기본 단위(1)로 취급할 때,
이러한 계산이 입력의 크기 N에 대해 얼마나 실행되는지를 계산하고
이를 N에 대한 수식으로 표시한다.
ex)
while(int i=0;i<n;++i)a++;  =>  O(n)


3)공간복잡도 수식화
배열, 큐, 스택 등에 저장되는 최대 갯수만 계산한다.
이후 이 함수를 빅오표기법으로 표현한다.
각 변수형마다 필요한 바이트는 다음과 같다.
char        1byte
int         4byte
float       4byte
double      8byte
long long   8byte
long double 8byte


4)매직 넘버
https://blog.encrypted.gg/724?category=773649
프로그래밍 문제를 풀 때 어떤 알고리즘을 쓸지 정할 때 기준이 되는 숫자들이다.

1.1초=1억
위에 언급된 기본단위 계산이 1억번 발생하면 최대 1초가 걸린다.
즉 빅오 표기법으로 만든 함수에 입력의 최대 크기를 넣은 값이 1억이 넘으면
다른 알고리즘을 구상해봐야 한다.

2.128MB=3천만
128MB에는 3천만개의 int형 변수를 넣을 수 있다.
이를 통해 배열이나 자료구조를 고려할 때 최대 저장해야 하는 변수 수를 조정한다.





#정렬
일반적으로 오름차순으로 정렬만 할거면 sort함수를 사용한다.
정렬 알고리즘별 설명 및 비교는 아래 주소 참조.
https://ratsgo.github.io/data%20structure&algorithm/2017/10/19/sort/
stable : 중복된 값을 입력 순서와 동일하게 정렬하는 방식.
in-place : 리스트 내부에서 정렬이 진행되므로 추가 메모리가 필요하지 않은 방식.
comparison : 값을 직접 비교하여 정렬하는 방식. ex)radix sort, counting sort


1)sort 함수 사용법
sort(v.begin(),v.end(),functor)
순서대로 리스트 시작 주소, 끝 주소, 펑터가 들어간다.
배열로 입력할 경우 맨 앞 원소 주소에 리스트 길이만큼 더해주면 끝 주소가 나온다.
vector의 경우 begin, end를 사용. end는 맨 뒤의 원소 주소에 +1한 위치이다.

펑터의 경우 다음의 규칙을 따른다.
1.객체를 파라미터로 받을 경우 참조형 변수 &로 전달해야 한다.
2.a가 b보다 앞에 와야 하면 true, 그렇지 않으면 false를 반환한다.
3.a와 b의 우선 순위가 같다면 false를 출력해야 한다.

또한 이미 만들어진 것도 있다. 오름차순이나 내림차순은 각각 less, greater 사용.
템플릿으로 만들어져 자료형도 바꿀 수 있다.





#비트마스크
:정수의 이진수 표현을 자료 구조로 쓰는 기법

1)비트마스킹의 장점
-더 빠른 수행 시간 : 대부분 O(1)에 처리 가능
-더 적은 메모리 사용량
-더 간결한 코드 : 대부분 반복문 없이 쓸 수 있기 때문


2)비트 연산자
a&b : AND 연산(양쪽 비트 모두 켜졌을때만 1))
a|b : OR 연산(양쪽 비트 중 하나라도 켜지면 1)
a^b : XOR 연산(양쪽 비트 둘중 하나만 켜지면 1))
~a : NOT 연산(결과 반전)
a<<b : a를 b만큼 왼쪽으로 시프트 
a>>b : a를 b만큼 오른쪽으로 시프트

유의할 점
1.비트 연산자들은 등호 연산자보다 우선순위가 낮으므로, 반드시 괄호 사용.
2.일반적인 상수는 C++에서 32비트 정수로 취급한다.
64비트 정수와 같이 쓸 경우 상수 뒤에 점미사 ull을 붙여 64비트 정수임을 명시한다.


3)비트로 집합 표현
1.공집합
int a=0;

2.꽉 찬 집합(원소 개수 n)
int a=(1<<n)-1;

3.원소 추가(p번째 원소)
a |= (1<<p);

4.원소 포함여부 확인(p번째 원소)
if(a&(1<<p))...

5.원소 삭제(p번째 원소)
a &= ~(1<<p);

6.원소 토글(켜졌으면 끄고 꺼졌으면 켜기)
a ^= (1<<p);

7.두 집합 연산
-합집합 : a | b
-교집합 : a & b
-차집합 : a & ~b
-합집합-교집합 : a ^ b

8.집합의 크기
int bitCount(int x){
    if(x==0) return 0;
    return x%2 + bitCount(x/2);
}
컴파일러별로 이미 만들어진 함수가 있으니 해당 함수를 찾아 쓸 것.

9.최소 원소 탐색
int onlyfirst = (a & -a); //0000100 형식으로 나옴 

10.최소 원소 삭제
a &= (toppings -1);

11.모든 부분집합 순회
for(int subset = a; subset; subset= ((subset-1) & a)){
    //공집합은 방문 x.
}



4)응용 예제

1.DP
불린 배열을 비트마스크로 대체할 경우 메모리 사용량이 줄어들기 때문에 유리하다.

2.에라토스테네스의 체
더 많은 수를 판별할 수 있다.

3.15퍼즐 게임
https://en.wikipedia.org/wiki/15_puzzle
각 숫자를 4비트 정수로 두고 차례대로 쌓으면
4*16=64로 게임의 상태를 64비트 정수 하나에 저장이 가능하다.

4.비트마스킹 우선순위큐
https://beenpow.github.io/jongman/2019/12/16/Jongman-ch16-3/
1~140까지의 서로 다른 우선순위를 불린 배열로 대체할 경우,
비트마스킹을 이용해 최소 원소 탐색만으로 우선순위큐와 동일한 역할이 가능하다.
단, 범위가 제한되어 있고 작아야만 성립.




#오버플로우와 실수 연산

1)산술 오버플로우
:어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위에서 벗어나는 경우.
저장 가능한 수의 범위를 벗어나면 부호 비트가 바뀌거나 아예 일부가 날아간다.

1.발생하는 이유
-너무 큰 결과 : 단순히 계산 식의 값이 사용하는 자료형의 표현 범위를 넘어가는 경우
-너무 큰 중간 값 : 계산 과정의 중간 결과가 너무 커지는 경우.
-설정된 무한대 값의 설정 : 임시로 설정한 무한대 값이 의도되지 않게 계산될 경우

2.오버플로 방지
-최종 결과값으로 나올 수 있는 수의 크기를 예상한다.
보통 int는 20억까지 저장할 수 있으므로, 이보다 큰 정수는 long long 형에 저장한다.
-계산을 할 때 중간값이 커질 것 같으면 나눗셈을 곱셈보다 먼저 진행한다.
-만약 너무 큰 값을 다룰 경우 자동으로 큰 수를 알아서 처리해주는 python을 사용한다.


2)자료형의 프로모션
:서로 다른 자료형을 연산할 때 이들을 같은 자료형으로 변환하여 연산하는 것.

1.규칙
-정수 + 실수 = 실수 + 실수
-작은 정수형 + 큰 정수형 = 큰 정수형 + 큰 정수형 (실수일 경우에도 동일)
-매우 작은 정수형 + 매우 작은 정수형 = int + int (char, short 등)
-signed + unsigned = unsigned + unsigned
덧셈 뿐 아닌 모든 이항연산에 동일하게 적용된다.


3)실수

1.컴퓨터의 실수 표현
https://ko.wikipedia.org/wiki/IEEE_754

2.오차
실수를 비교할 때는 부등호 및 등호를 바로 쓰면 안되고 오차를 활용해야 한다.
예를 들어 (1/7)*3==(3/7)는 실제 현실에서는 맞는 식이지만 컴퓨터에서는 아니다.
1/7의 근사값과 3/7의 근사값을 비교하므로 오차가 발생할 수 있고,
발생 가능한 최대 오차를 따로 정하여 그보다 작은 오차의 경우 두 실수를 같다고 한다.
AbsoluteEqual(a,b)=> return |a-b| < 1e-8;
실수 절대값은 fabs(a) 활용. 

일반적으로 입력되는 수들의 범위에 따라 위와 같은 절대 오차를 정해도 되고,
입력되는 수들의 범위가 매우 넓다면 입력받는 수들의 상대 오차를 활용한다.
reletiveError(a,b)= 1e-8 * |a-b|/max(|a|,|b|)
AbsoluteEqual(a,b)=> return |a-b| < reletiveError(a,b);

단, 너무 작은 수들의 비교를 할 경우 상대 오차를 쓰면 비교가 불가능할수도 있다.
이런 경우 일정 수준 이하의 오차에 대해서는 절대 오차,
일정 수준 이상의 오차에 대해서는 상대 오차를 활용하는 것이 좋다.
AbsoluteEqual(a,b)=> 
diff=|a-b|;
if(diff<1e-8) return true; //절대 오차
else return |a-b| < reletiveError(a,b); //상대 오차

위는 등호를 사용하는 경우에 대한 내용이고,
부등호의 경우에도 두 수가 같은지는 다음과 같이 비교한 후 부등호 비교를 진행.

3.그외 실수형 사용시 주의 사항
https://www.acmicpc.net/blog/view/37

-float 보다는 double형 사용
:계산 속도 대비 정확도 상승률이 크다.

-실수형 변수 안에 정수를 넣는 경우 아무 처리 없이 다시 정수형 변수에 넣지 말것
:1을 double에 저장할 경우 0.9898...이 되고, 이를 다시 정수형에 넣으면 0이 된다.

-매우 큰 값을 사용할 때
:너무 큰 값을 사용할 경우 소수점 아래가 아닌 1의 자리에서도 오차가 발생할 수 있다.
매우 큰 실수를 비교할 때는 상대 오차를 활용해야 한다.
또한 매우 큰 수에 작은 수를 더할 경우 작은 수의 정밀한 부분이 무시될 수 있다.
여러 수를 더해야 한다면 크기순으로 더하는 것이 좋다.





#완전탐색
입력 범위가 작으면 바로 완전 탐색을 시도한다.(1억==1초)
구현은 크게 두 가지 방법을 사용한다.
1.재귀(일반적으로 더 직관적) 
2.반복문(일반적으로 더 빠름)



1) 유형
1.중복을 허용하는가? 2.순서가 고려되는가?
1-1.허용하면->처음부터 뽑는다.
1-2.허용 않으면->뽑혔던 것들을 전역 변수로 저장한다.(백트래킹)
2-1.고려되면->순열.
2-2.고려 안하면->조합. 순서를 고정한다.
특정 원소를 포함할지 말지 결정하는 문제(2^n 문제)도 완전탐색으로 풀 수 있다.



2)백트래킹
1.완전탐색으로 풀수 있는 문제 중 
2.모든 순열이나 조합을 사전순으로 만들어야 하는 문제에 사용.
재귀로 모든 답을 차례로 만들며, 답이 완성되면 재귀 스택을 빼내 바로 이전으로 돌린다.

완전탐색의 일부로, 재귀로만 푼다. 크게 두 유형으로 나뉜다.

1.N-Queen 문제
속도를 줄이는 법으로 미리 원소를 캐싱하는 방법이 있는데
특정 원소가 선택되었는지 여부를 저장해둔다.
좌표계의 위치를 따질 때도 가로, 세로 등등 겹치는 것이 있는지 따로 저장한다.
대부분 전체 원소 개수 n의 배수만큼 빨라진다. 대신 메모리 초과 항상 확인할 것.

2.순열 찾기
순열을 구하는 문제의 경우 next_permutation을 활용할 수 있다.
배열을 사전순으로 바로 다음에 해당하는 백트래킹 결과로 바꿔준다.
중복된 수도 잘 처리해주며, 
조합을 따질 때도 {0,0,0,1,1}과 같은 배열을 대신 사용하면 처리가 가능하다.






#분할정복
1.문제를 재귀함수로 분할이 용이하고,
2.분할된 문제가 원래 문제와 성격이 동일하고,
3.최소단위 문제를 쉽고 빠르게 풀 수 있는 경우 사용한다.



1) 접근법
다음의 순서로 진행된다.
분할(Divide) : 문제를 적절한 형태의 하위 문제로 더 이상 나눌 수 없을 때까지 나눈다.
정복(Conquer) : 최소 단위 문제의 해를 구한다.
결합(Combine) : 구한 해를 나눈 순서대로 결합해가며 전체 답을 구한다.



2) 머지 소트
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,
두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.
대표적인 분할정복 알고리즘이다.

분할 : 리스트를 크기가 같은 두 개의 부분 배열로 나눈다.
정복 : 최소 단위로 나눠진 배열을 정렬한다.
결합 : 부분 배열들을 합병한다.
실제 과정에서는 결합이 진행될 때 정렬을 하기 때문에 정복과 결합이 동시에 진행된다.

리스트가 아닌 고정 배열을 정렬할 경우 추가적인 공간이 필요하다.
단 연결 리스트를 활용하면 추가 공간이 없어도 구현이 가능하다.
이를 이용해 크기가 큰 리스트도 머지 소트를 활용하면 효율적으로 정렬할 수 있다.



3)Inversion counting
초기 배열 내 정렬된 상태와 비교하여 역순으로 되어 있는 쌍의 개수를 찾는 문제.
정렬된 Array는 inversion의 수가 0.

가장 단순한 방법은 버블 소트를 이용해 역전의 개수를 일일히 세는 것.
버블 소트는 직접 배열에 존재하는 모든 역전을 돌려놓는 방식이다.
그러나 버블소트 자체가 비효율적이므로 더 빠른 방법이 필요한데, 머지 소트를 활용한다.

버블 소트의 병합 과정에서 왼쪽과 오른쪽 배열은 각각 정렬된 상태이다.
따라서 여기서는 역전이 발생할 수 없고, 병합 과정에서만 역전이 일어난다.
왼쪽 부분이 선택될 경우 나누기 전 배열과 동일해지므로 역전이 일어나지 않는다.
오른쪽 부분의 수가 선택될 때, 역전된 부분이 정렬되므로 역전이 발생했다고 본다.
이 때 역전의 수는 왼쪽 부분의 남은 원소 수와 동일하다.
기존 합병 정렬에서 왼쪽 배열의 남은 원소 수를 세는 알고리즘만 추가하면
역전의 수를 빠르게 셀 수 있다.





#동적계획법

1)최적 부분 구조
전체 문제를 같은 부분 문제로 조각냈을 때,
어느 부분 문제에 도달할 때까지 있었던 모든 선택이 이후의 선택에 영향을 주지 못하며
따라서 남은 부분 문제는 항상 최적으로 풀어도 상관 없는 문제 구조
즉 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 구할 수 있는 문제 구조



2)일반 DP(탑-다운)
DP를 쓸 때는 최적 부분 구조가 성립해야 한다.
이전의 계산 결과가 현재의 해를 구할 때 영향을 준다면 이 방법은 사용할 수 없다.

판단 방법 : 비둘기집의 원리
n+1개의 물건을 n개의 상자에 담을 경우 
반드시 두 개 이상의 물건이 들어있는 상자가 존재한다.
특정 해를 구하기 위해 필요한 해의 개수보다
실행되어야 하는 총 계산수가 더 많으면, 중복되어 계산되는 것이 존재한다는 의미이다.
이 경우 동적 계획법을 사용할 수 있다.
실행되어야 하는 총 계산의 횟수는 수학적 귀납법을 통해 구한다.(점화식)

이러한 판단이 끝날 경우 다음과 같은 방식으로 문제를 해결한다.
1.테이블 정의 : 어떤 문제를 풀기 위해 문제를 정의한다.

2.점화식 : 해당 문제의 규칙을 통해 모든 수에 만족하는 점화식을 찾는다.
직접 테이블을 채워가면서 찾는게 가장 일반적이다.
일반적으로 점화식이 너무 복잡하면 잘못 구한거다.

3.초기값 정하기 : 문제의 조건을 통해 기초가 되는 초기값을 미리 입력한다.
동적계획법의 재귀적 특성을 이용하기 위해, 임의로 -1번째 인덱스를 설정한다.
최초의 비교값등을 설정해 맨 처음에 원소를 선택할때도 재귀문을 사용할 수 있는데
이때 0번째 인덱스를 -1번째로 두고 나머지 원소들의 저장 위치를 1씩 오른쪽으로 민다.
변경된 인덱스를 적용할 때 항상 끝점의 포함 여부등을 유의하면서 코드 작성.

01 배낭 문제 : 
쪼갤 수 없는 물건들이 나열되어 있을 때,
한정된 무게 안에서 최대한의 가치를 가져가야 하는 문제.

D(w,n)=n번째 물건들 중 전체 혹은 일부를 담아 남은 무게가 w일때 갖는 최대 가치를
D(w,n)=max(D(w-w[i],n-1)+c[i],D(w,n-1))
w<0, D=0;n==0,D=0

LIS : 
최장 증가 부분 수열.
지금까지 만든 LIS 길이만 알면 추후 만드는 LIS의 길이를 따로 구해서 더하면 된다.
이전의 결과가 이후의 선택에 영향을 주지 않음(최적 부분 구조)

D(last)=마지막에 고른 수가 last번째 원소일 때 만들 수 있는 LIS 길이.
D(last)=max(D(last+i)+1) (last<i<=n)
D(0)=0

이렇게 짤 경우 시간복잡도가 O(N^2)인데,
더 빠른 알고리즘(O(NlogN))) 이 필요하다면 이분탐색을 통해 짜면 된다.

위상 정렬 :
우선순위가 있는 작업들을 DAG로 표현했을 때,
DAG의 정점들을 일렬로 나열했을 때 모든 간선이 왼쪽에서 오른쪽으로 가도록 하는 정렬.

//



3)경로 추적
경로 복원용 테이블을 새로 만든다.
특정 값을 구할 때마다 이전 참조 테이블의 인덱스 등을 기록하고,
이후 모든 DP가 끝나면 이 테이블을 역추적하여 
최대/최소 등의 결과가 나온 경로를 출력한다.



4)반복적 동적 계획법(바텀-업)
탑 다운 방식은 점화식을 그대로 적용하기 쉽지만
바텀 업 방식보다 메모리 측면에서 비효율적이기 때문에
둘 모두를 구현할 수 있어야 하고 경우에 따라 잘 적용해야 한다.

1.일반적인 방법
점화식을 대입식으로 변형하여 가장 작은 조각부터 시작하여 모든 배열을 채워나간다.
반복문을 통해 대입식을 사용하며 초기값 설정을 꼭 해야 한다.

2.최소 편집 거리
https://blog.naver.com/ndb796/220870218783
두 문자열이 주어졌을 때, 두 문자열의 유사도를 나타내는 지표.
특정 문자를 추가, 삭제, 변환할 때마다 수정이 1회 되었다고 가정할 때,
두 문자열 A,B의 편집 거리는 A에서 B로 바꿀 때 필요한 수정의 최소 횟수가 된다.

두 문자열의 편집 거리를 계산할 때 테이블을 그려 계산한다.
초기 테이블의 0번 인덱스는 공집합이고, 인덱스와 값이 동일하다.

두 문자열의 부분 문자열을 먼저 비교하여 비교하는데,
예를 들어 abc 와 def를 비교할 때 ab와 de를 먼저 비교하는 식이다.
이때 ab와 de의 편집거리를 알면, ab와 def의 편집 거리는 바로 알 수 있다.
단 한글자가 추가된 것이기 때문에 편집 거리는 딱 1 증가하기 때문.
이런 식으로 테이블을 통해 얻을 수 있는 규칙들이 있다.

추가/삭제 - 양쪽 문자열 중 하나에만 문자 하나가 추가되면 편집 거리는 1 증가한다.
변경/복사 - 양쪽 문자열 모두 문자가 하나 추가됬을 때,
서로 다른 문자라면 편집 거리는 1 증가하고 같은 문자라면 편집 거리는 동일하다.

최소 편집 거리를 구하기 위해 테이블 기준 왼쪽, 위쪽, 왼쪽 위 대각선 칸을 본다.
왼쪽, 위쪽의 칸을 참고한다는 뜻은 추가/삭제 연산을 한다는 뜻으로
편집 거리가 1 증가해야 한다.
왼쪽 대각선 방향을 참고한다는 뜻은 변경/복사 연산을 한다는 뜻이고
만약 추가되는 문자가 같다면 편집 거리가 증가한다.
그 외 경우 편집 거리가 1 증가한다.

따라서 최소 거리를 구하기 위해서는 새로 추가된 문자가 서로 같은지만 확인하고,
만약 같다면, 복사가 일어났으므로 대각선 칸의 숫자를 그대로 가져온다.
다르다면, 어떤 식으로든 편집 거리가 정확히 1 증가했으므로
최소 편집 거리는 인접한 세 칸들 중 최소인 값에 1을 더한 값이다.

점화식 : 
if(A[i]==B[j]){
    D[i,j]=D[i-1,j-1]
}else{
    D[i,j]=min(D[i-1,j],D[i,j-1],D[i-1,j-1])+1
}

3.슬라이딩 윈도
특정 거리를 유지하는 무언가를 이동시키는 것.
일반적으로는 두 인덱스 사이 거리 등을 유지시키며 이동한다.

DP를 할 때 점화식을 보면 특정 칸은 계산이 끝난 후 
더 이상 저장할 필요가 없는 경우가 생긴다.
이 경우 어떤 칸을 계산할 때 필요한 범위를 살펴보고,
이것이 일정하면 메모리 선언을 줄이고 인덱스의 나머지를 새로운 인덱스로 설정해
필요한 공간에 저장하고 참조하는 것으로 공간복잡도를 줄일 수 있다.

//예시




4) 트리DP





#탐욕법
모든 경우에 지금 당장 최적인 답만을 선택하는 방법.
일반적인 완전 탐색에서 관찰을 통해 탐색 범위를 줄이는 방식이다.

탐욕법은 해당 문제가 최적 부분 구조이며, 탐욕적 선택 속성이 있어야 성립.
각 단계에서 탐욕법으로 선택한 부분 문제의 최적해들을 포함하는 전체 최적해가 
항상 존재하면 해당 문제는 탐욕적 선택 속성이 있는 문제.



1)증명
증명은 다음과 같이 진행한다.
1.탐욕법이 "속성 A를 갖는 원소를 포함하는 최적해가 반드시 존재한다"라면
2."속성 A를 갖지 않는 원소를 포함하는 최적해가 있다"고 가정
3.이후 둘을 비교하여 2.의 경우가 최적해라면 1.의 경우도 최적해가 되어야 함을 증명,
탐욕법을 적용할 때 선택에 있어 손해를 볼 일이 없음을 증명한다.

다만 실제 문제 풀이에서는 이런 증명이 시간이 너무 오래 걸리므로
테스트 케이스를 통해 어느정도 입증을 한 후 증명을 생략한다.
이 경우 정확도가 높은 방법이 아니므로 가장 마지막에 시도하거나,
해당 방법이 틀렸을 경우 빠르게 다른 방법을 찾는 것이 좋다.



2)일반적인 그리디 문제

3)스케줄링 문제




#투포인터




#이분탐색
정의 : 
1)기본 이분탐색
오버플로우 주의
최소값의 최댓값

1.LIS 

2)최대, 최소 문제 결정 문제로 변환





#스위핑 알고리즘





#배열
번호와 번호에 대응하는 원소들로 이루어진 자료구조.

1)배열의 특징
1.C++에서는 유한 개수의 원소를 받으며 메모리 상에서 원소를 연속으로 위치하게 한다.
2.O(1)에 모든 원소 접근/변경 가능하다.
3.O(N)에 원소를 임의 위치에 추가,제거가 가능하다.
4.O(1)에 맨 끝 원소를 추가하거나 제외할 수 있다.


2)배열 초기화 방법
https://blog.encrypted.gg/927
1.memset(cstring 헤더)
사용 방법 : 
int a[5]; int b[5][5];
memset(a,0,sizeof(a)); //1:초기화할 배열,2:초기화 값(0 또는 1),3:배열 크기
memset(b,-1,sizeof(b)); //이중배열도 가능
이 방법으로는 0 또는 -1만 쓸수 있으며 다른 수로 초기화하면 의도한 값이 안 들어간다.

2.for문 초기화
가장 투박하지만 귀찮은 방법.

3.fill(algorithm 헤더)
사용 방법:
int a[5]; int b[5][5];
fill(a,a+5,0);//1:시작지점,2:종료지점,3:초기화 값
for(int i=0;i<5;++i)fill(b[i],b[i]+5,0);//이중 배열은 바로 사용 불가
이 방법은 모든 수로 초기화가 가능하다.

4.전역, 지역변수
전역 변수로 배열을 선언할 경우, 자동으로 0으로 초기화가 된다.
단, 지역변수는 이에 해당하지 않으므로 반드시 따로 초기화를 진행해야 한다.


3)STL vector
위에 소개한 배열의 확장판.
일반적으로 무한개의 원소를 집어넣어야 하는 배열은 전부 vector를 활용한다.
만약 입력 범위가 가용 가능한 범위 안이라면 그 크기만한 배열을 선언해도 된다.





#연결 리스트
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 
데이터를 저장하는 자료 구조.


1)연결 리스트의 특징
1.연속된 공간에 데이터가 존재하지 않는다.
2.O(k)에 k번째 원소에 접근이 가능하다.
3.O(1)에 특정 원소 앞뒤에 원소를 추가하거나 제거할 수 있다.
4.O(N)의 공간을 배열보다 추가로 필요로 한다.
5.리스트의 길이나 마지막 원소 찾기는 원래대로라면 O(N)만큼의 시간이 걸리지만,
구조체에 tail을 추가하거나 길이를 따로 저장해두면 O(1)안에 수행할 수 있다.

연결 리스트는
1.모든 원소를 순회하나 
2.삽입, 삭제가 빈번히 일어나고
3.인덱스 접근이 적게 발생한다면 사용할 만한다.

2)STL List 
//



#스택/큐/덱
셋다 순차적으로 진행되는 문제에 주로 사용된다. ex) 초단위 계산, 절차대로 작업

1)스택
나중에 넣은것부터 변화를 줄 경우

1. 스택을 이용한 스위핑 알고리즘
2. 괄호 문제
3. 전위/중위/후위 표기식

2)큐
처음에 넣은것부터 변화를 줄 경우

3)덱





#맵, 힙

1)맵
문자-숫자 짝으로 자료를 저장해야 할 때 사용.
그외에도 너무 자료형이 복잡해지면 사용.
맵은 자동으로 오름차순 정렬을 지원한다. sort 쓰지 말것.
탐색 방법 :
map<~,~> m;
if(m.find(key)==m.end()){//찾는 게 없는가?
    m.insert(make_pair(clothes[i][1],1));//없으면 넣고
}else{
    m[clothes[i][1]]++; //있으면 숫자 증가
}
순회 방법 :
map<~, ~>::iterator it;
for (it = m.begin(); it != m.end(); it++) {
    ~
}



2)힙(우선순위 큐)
: 원소 추가시마다 정렬을 새로 해야 할 경우 사용

우선순위 큐를 반으로 쪼개 두개의 우선순위큐를 만들고 서로 정렬을 반대 규칙으로 하면,
언제나 중앙값을 찾을 수 있는 우선순위큐를 만들 수 있다.(크기가 큰 쪽의 top)
삽입시 양 쪽 탑을 비교해서 적절한 큐에 넣고, 최대값과 최소값은 루트를 탐색한다.





#트리

1)정의
1.노드가 0개이거나
2.노드가 1개 이상이고 방향 간선이 존재할 경우
2-1.들어오는 간선이 하나도 없는 단 하나의 노드가 존재하고(루트 노드)
2-2.루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재하며
2-3.루트에서 다른 노드로 가는 경로는 반드시 존재하며, 유일하다. 
이는 루트를 제외한 모든 노드에 성립해야 한다.



2)일반 트리
루트 노드 찾기 :
만약 루트 노드가 주어지지 않는다면 직접 찾아야 한다.
간선 목록이 주어질 때 노드의 등장 횟수를 세어 노드나 리프의 여부를 판별할 수 있다.
루트 노드는 자식 노드로 등장하지 않으며, 
리프 노드는 부모 노드로 등장하지 않고 등장 횟수가 단 한번이다.

트리는 자체적으로 반복되는 구조를 가지므로 재귀, 분할정복을 활용하기 용이하다.
또한 트리는 그래프이기 때문에 이 특성을 잘 이용하자.

트리에서 층을 나눠 작업을 할 때 큐를 사용한다.
깊이순으로 루트부터 노드를 추가하고 싶다면 부모가 될 노드를 큐에 넣고,
부모를 바꿀때마다 pop하는 식으로 트리를 생성한다.

만약 문제를 풀다 도저히 알고리즘이 떠오르지 않는다면,
해당 문제를 트리로 표현해보고 적용할 수 있는 트리 알고리즘이 있는지 찾아본다.
문제를 알고 있는 자료구조로 치환해봐야 한다.


3)전위/중위/후위 순회

4) 최소 공통 조상

5) 이진 탐색 트리

6) 누적 합

7) 구간 트리 (세그먼트 트리)

8) 문자열/트라이

1. KMC 알고리즘

2. 트라이

9) 상호 배타적 트리 (분리 집합 ,union-find)

집합 표현시 사용. 배열 하나 두고 해당 원소가 속한 원소의 집합의 대표 원소를 반환하는 배열 parent를 둬 해당 원소가 어디에 속하는지를 확인.
집합 표현할 때 쓰로 주로 최소 스패닝 트리 다룰 때 쓴다.

struct NaiveDisjointSet { 
    vector<int> parent; 
    NaiveDisjointSet(int n): parent(n) { 
        for (int i=0; i < n; i++) parent[i]=i; 
    } 
    int find (int u) { 
        if (u == parent[u]) return u;  
        return parent[u]=find(parent[u]); 
    } 
    bool merge (int u, int v){
        u = find(u); v = find(v); 
        if (u == v) return false; 
        parent[u] = v; 
        return true;
    } 
};

10)최소 스패닝 트리

1.크루스칼 최소 스패닝 트리
예시 : https://programmers.co.kr/learn/courses/30/lessons/42861
그리디 알고리즘의 대표 예시, 시간 복잡도 O(ElogE).
모든 정점이 연결된 경우가 아니라면 사용한다.
간선을 가중치 순으로 정렬하고, 간선을 n-1개만큼 선택한다.
이때 사이클이 발생하는 경우는 제외하고 선택해야 한다.
사이클을 판별할 때 유니온파인드 셋을 쓰면 간단하다.
각각의 정점이 하나의 집합이라고 생각하고, 간선으로 연결될 때마다 집합을 합친다.
만약 이미 합쳐진 두 정점을 선택할 경우 수를 세지 않는데,
이 과정이 유니온파인드의 merge 함수와 정확히 일치한다.

2.프림 최소 스패닝 트리
크루스칼과 비슷한 그리디 알고리즘.
모든 정점이 서로 연결된 경우에 크루스칼보다 빠르게 동작한다.
...추가바람

대표 유형 1) 유니온 파인드
대표 유형 2) 최소 스패닝 트리




#그래프 탐색
V=정점, E=간선

만약 문제를 풀다 도저히 알고리즘이 떠오르지 않는다면,
해당 문제를 그래프로 표현해보고 적용할 수 있는 그래프 알고리즘이 있는지 찾아본다.
문제를 알고 있는 자료구조로 치환해봐야 한다.


1)그래프 표현 방법
1.인접 행렬
int Graph[start][end]
이중 배열을 이용해 각 인수를 출발,도착 노드 번호로 사용.
모든 노드간 관계를 전부 표현하며 공간복잡도가 O(V^2)으로 큰편.
간선 수가 많은 밀집 그래프에 적합.

2.인접 리스트
vector<int> Graph[node]
각 노드와 이어진 정점을 노드별로 전부 리스트에 저장.
두 노드간 간선을 모두 탐색해야 해서 시간복잡도가 O(V)만큼 소요.
간선 수가 적을수록 빨리 동작하므로 간선이 적은 희소 그래프에 적합.

3.간선 리스트
vector<vector<int>> Graph
간선을 기준으로 저장하는 방식.


2)그래프 탐색 방식
1.DFS
모든 정점을 방문해야 할 때 사용(방문할 필요 없는 정점 많으면 사용 x)
백트레킹과 많은 부분 겹쳐서 왠만해선 어렵게 안 나온다.

2.BFS
다음과 같은 경우 사용
1-가중치 없는 그래프에서 A->B로 가는 임의 최단 경로 탐색시.
2-어떤 물체의 상태(위치)가 계속 변화하는 경우
3-1씩 증가하는 경우(BFS는 탐색 시 노드의 깊이가 증가수열을 이룬다.)
큐를 이용. 그 외 격자가 등장하며 그래프로 접근해야 하면 무조건 BFS.



3)위상 정렬





#최단경로
최단 경로 기법을 쓰기 전에, 그래프를 만들었을 때
1.상태 변화에 관련된 문제이거나
2.가중치가 0 혹은 1이거나
3.어떤 변화에 대한 확률 혹은 비용이 모두 같다면
BFS를 사용하면 최단 거리를 바로 구할 수 있다.

1)다익스트라(dijkstra)
어느 정점에서 가장 가까운 정점을 매 단계마다 찾아 
해당 정점을 거쳐 인접 정점들로 갔을 때 더 짧은 거리로 이동했는지 판별한다.
매 단계마다 선택되는 정점은 출발 지점에서 더 이상 짧은 경로를 발견할 수 없으므로,
이를 확정하고 기준으로 잡아 최단거리를 갱신해 다음 정점을 선택한다.

가중치가 모두 양수이고 모든 정점들의 관계를 구할 필요 없을 때 사용.
시간복잡도를 잘 고려하여 플로이드를 쓸 수 없으면 사용한다.

밀집 그래프가 아니면 무조건 힙으로 구현. 그래프는 인접 리스트 방식.
힙을 쓴 다익스트라의 시간복잡도는 O(VlogE)이므로 밀집 그래프가 아니라면
플로이드 한번 쓰는거보다 다익스트라를 정점 수만큼 쓰는 게 더 빠르다.

단순한 거리가 아닌 실제 최단 경로를 복원해야하는 문제가 있을 수 있다.
경로 복원시 pre 배열 선언 후 최단거리에서 직전에 방문한 정점 계속 업데이트한다.



2)플로이드
모든 정점에 대해 해당 정점을 다른 정점들이 거쳐서 갈 경우에
경로가 더 짧아지는지를 일일이 비교하는 방식.
모든 정점에 대해 다른 모든 정점을 거쳐가는 경우를 구하므로
반드시 가장 짧은 경로를 구할 수 있다.

가중치가 모두 양수이고 모든 정점에 대한 최단거리 필요 시 사용.
for문 순서는 중간->시작->끝. 인접 배열 방식 사용.
시간복잡도가 O(V^3)이라 E<400일때만 사용. 밀집 그래프일경우 고민 없이 플로이드.

경로 복원시 이중배열 선언 후 최단거리에서 바로 다음에 방문해야할 정점 계속 업데이트.
출발지->도착지의 직전 정점을 경유지->도착지의 직전 정점으로 업데이트한다.

1.우선순위 판별



3)벨만포드
다익스트라, 플로이드가 음수 간선이 안되는 이유:
매 단계에서 최단거리를 확정하지만, 확정된 최단 거리가 음수 가중치에 의해
확정이 되지 않는 순간 다익스트라 알고리즘의 전제가 깨지게 된다.

음수 간선이 존재할 경우 사이클이 발생하면 가중치가 무한히 작아질 수 있다.
따라서 벨만 포드에서 최단거리는 간선을 최대 |V|-1개까지만 선택할 수 있다. 

한 정점을 기준으로 한 최단거리를 구하고 싶을 때,
모든 정점들에 대해 각각의 인접한 정점으로 더 짧은 경로로 이동할 수 있는지 판별한다.
만약 정점의 최단거리가 아직 초기화되지 않았다면, 해당 정점은 해당 단계에서 무시한다.
이후 이를 |V|-1번 반복하면 가능한 모든 간선을 지나며 모든 최단거리를 알 수 있다.
그러나 만약 |V|번째에서 최단거리를 갱신했을때 값이 변경되었다면,
이는 그래프 안에 음수 사이클이 있다는 의미이므로 벨만 포드 알고리즘을 쓸 수 없다.

시간복잡도는 O(|V||E|), 밀집그래프일 경우 O(|V|^3)로,
가중치가 음수인 경우에만 사용한다. 인접 리스트 방식을 사용하는게 좋다.
또한 여러번 같은 계산을 수행하기 때문에 값이 기하급수적으로 커질 수 있으니,
자료형을 잘 선택하는 게 좋다.

또한 사이클 여부만을 확인하고 싶을 때는 시작 정점과 단절된 사이클까지 고려해야 한다.
이럴 경우 모든 정점을 직접 확인하면 시간 초과가 날 수 있으므로,
단절된 정점이 매우 큰 가중치로 이어져 있다고 가정하고 찾아야 한다.(INF 확인 없애기)





#최대 유량





#정수

1) 소수
정의 : 1과 자기 자신으로만 나누어지는 수
=> 약수가 2개인 수
합성수 : 1과 자기 자신을 제외한 약수가 존재하는 수

1은 소수도 합성수도 아님. 항상 예외.
2는 유일하게 짝수인 소수. 걸러낼 때 유의.

1.소수 분해법
//

2.에라토스테네스의 채
//https://www.acmicpc.net/problem/1929

3.소인수분해
//


2) 최대공약수(Greatest Common Divisor)
약수 : 어떤 수를 나누어떨어지게 하는 수
공약수 : 두 자연수의 공통된 약수
최대공약수 : 두 자연수의 공통된 약수 중 가장 큰 약수

1.유클리드 알고리즘
//

2.최소공배수(Least Common Multiple)
gcd(A,B)*lcm(A,B)=A*B
따라서 두 수의 최대공약수를 구할 수 있으면 최소공배수도 쉽게 구할 수 있다.


3) 연립합동방정식(중국인 나머지 정리)
//https://www.acmicpc.net/problem/6064


4) 모듈라 연산
:모듈로 M에 도달하면 다시 0으로 돌아가는 정수들을 가지고 하는 연산.(나머지 연산)

정수 a,b에 대해 다음이 항상 성립함.
- (a+b)%M=((a%M)+(b%M))%M
- (a-b)%M=((a%M)-(b%M))%M
- (a*b)%M=((a%M)*(b%M))%M
단 나눈셈은 이 방식이 성립하지 않는다.


#기하