-
Notifications
You must be signed in to change notification settings - Fork 0
Home
- 인풋값을 보고 시간측정을 예측하자
- 모든 경우의 수 다 해보기.( 2^30이하로 ) 2^20 = 100만 ex) 피보나치 입력이 50인데 재귀로 2^50이면 시간초과.
- 재귀함수
- 기저 사례 작성(끝 end 조건)
- 재귀 함수 호출
- 값을 반환 해야한다.
- gcd
- 부분집합 구하기
- 팀원구하기
- 완전탐색
int func(idx, sum){
if (idx == n){ //탐색을 완료 했을 때
if (T == sum) return 1; //sum과 목표값이 같으면 횟수 1을 반환
}
int x = func(idx+1, sum); //선택 안하고 넘어가기
int y = func(idx+1, sum+A[idx]); //선택 하고 넘어가기
return x+y; //선택안하고 넘어간거와 선택하고 넘어간 가지수를 모두 더함.
}- 문자열
문자는 아스키코드로 사전순은 대문자 ~소문자가 아니지만 아스키코드는 그 순서. 소문자에서 뺴면 대문자로 변환 (32) 아스키코드 차이 값.
문자열 , 숫자(1000자리 이런것도 문자로) 효율적으로 세기 위해서는 26개 분기문, 10개 분기문 x 'a', 'A', '0' 을 빼서 셀 수 있다. (배열 인덱스)
백준 온라인에서 [스페셜 저지] 표시가 있으면 답이 여러개가 될 수 있다. 후보 추천하기랑, 수열은 꼭 풀어보자.
9개 중에 7개를 선택하는 경우보다 2개를 제외하는 것이 더 빠르게 구할 수 있다. 시간 복잡도:가능한 경우 nC2 ( O(n^2))
root(n)으로 확인 할 수 있다. 완전제곱수는 약수의 개수는 홀수 이다. (1, 5, 25) 이러한 부분만 예외처리로 해주면 반 구한다음 * 2하면 개수를 쉽게 구할 수 있다.
문제 요약
- 수열이 어떻게 만들어지는가.
- F(N) = F(N-2) - F(N-1)
- F(N)이 음수가 되는 순간 수열 끝
- F(1) 주어지면 수열의 길이를 최대로 만드는 F(2)를 찾자.
문제 해결
- 수열의 길이를 구하는 것
- F(2)를 구하는 방법?
- 0~3만번까지 확인 (시간내에 들어 온다.)
- 5개 중 3개 완전탐색
- 최대값의 인덱스를 구하는 과정?
- 최대값이 두 개 이상이라면 큰 인덱스를 구하는 과정은?
- maxValue , idxMaxValue
- 같은 반이였던 친구 수 구하는 것은 단순 구현
- 가운데 median을 구하면 최소 값을 구할 수 있다.
- 아니면 그냥 모두 구하기
다 구하기에는 10만의 제곱이라서 10억이 넘는다. 부분합, 혹은 슬라이딩 윈도우(이전/이후 한 단계만 차이가 나기때문에)
스타트와 링크
- 우선 처음에 부분합 처럼 2^n 모든 경우의 수를 구한다. ( 링크/스타트 팀인지)
- 그 이후에 링크 팀원수 == 스타트 팀원수가 될 때만 조건으로 구한다.
func(int pos){
if(pos ==n){
return;
}
//A팀 선택
T[pos] = 0;
func(pos+1);
T[pos] = -1;
//B팀 선택
T[pos] = 1;
func(pos+1);
T[pos] = -1;
} func(int pos, list A, list B){
if(pos ==n){
return;
}
//A팀 선택
A.add(pos);
func(pos+1, a,b);
A.pop();
//B팀 선택
B.add(pos);
func(pos+1, a,b);
B.pop();
}const SWITCH = 10;
T[SWITCH]
void func(){
if(post ==SWITCH){
//배열 t는 각 스위치가 얼마나 눌렷는지 기록한 배열.
return;
}
// pos에서 선택할 수 있는 네 가지 경우의 수
// 0번, 1번, 2번, 3번 누른다.
for(int i=0;i<4; ++i){
T[pos] = i;
func(pos +1);
T[pos] = -1;
}
}- 반복문 / 재귀 테이블을 이용하여 계산했던 값은 가져다가 쓰기.
int func(int n){
if(n==1|| n==2)
return 1;
return func(n-2) + func(n-1);
}int func(int n){
if(n==1|| n==2)
return 1;
if(cache[n] != -1)
return cache[n];
return func(n-2) + func(n-1);
}완전탐색
int func(int money) {
if(money ==0) {
return 0;
}
int ret =INF;
FOR (INT I=0; I<N; i++){
const int coin = coins[i];
//F(N) => N원을 만드는데 사용한 최소 동전 수
//F(N-coin) => N-coin원을 만드는데 사용하는 최소 동전 수
//F(N) = F(N- coin) + 1(동전 수)
//여기서 코인이 여러가지이기 때문에
//F(N) = min(F(N-COIN) +1) COIN은 가능한 모든 coin 경우
// 비슷한 예
//F(N) => 1 ~ N 까지의 합.
//F(N-1) => 1 ~ N-1 까지의 합
//F(N) = F(N-1) + N (N을 더해야함)
if(money >= coin) {
ret = min(ret, func(money- coin)+1);
}
}
return ret;다이나믹
int func(int money) {
if(money ==0) {
return 0;
}
int ret =INF;
FOR (INT I=0; I<N; i++){
const int coin = coins[i];
if(cache[money] != -1){
return cache[money];
}
//F(N) => N원을 만드는데 사용한 최소 동전 수
cache[money] = INF;
for(int i=0; i< n; ++i){
const int cooin = coins[i];
if(money >= coin) {
cache[money] = min(cache[money], func(money- coin)+1);
}
}
}
return cache[money];- func(idx, color)는 재귀적으로 어떻게 정의?
- func(idx,color) = min(func(idx+1, c1), func(idx+1,c2)) + cost[idx][color]
- c1,c2,는 color와 달라야한다.
- Cache 테이블의 크기가 시간복잡도
- O(3*N) , 약 O(N)
경우의 수, 최소값, 최대값 최대한 많이 풀자.
나눠서 함수 , 캐쉬테이블 2개로
숫자 num을 만들때 몇개의 수를 선택해서 만드니. 1.0부터 n까지 정수 k개를 더해서 n을 만드는 경우의 수 완전탐색 func(cur, count) 현재 cur이란 숫자를 count개의 수를 이용해서 만듬 N까지 만드는 경우의 수
기저사례, 정확한 뜻, 인자를 정의.
func(cur, count) = 시그마[i=0..N] func(cur + i, count + 1) 현재의 합과 count 개수
memset은 0, -1은 다른 형에서도 사용할 수 있다. 1byte마다 0으로 채우는데 4byte에서도 0 1byte마다 -1으로 채운다. (2의 보수 는 11111111) 4byte (11111111 11111111 11111111 11111111) 재귀함수가 호출되는 경우의 수는 Cache 테이블들의 크기가 시간복잡도. 그런데 호출되는 횟수마다 for문을 돌기 때문에 for문의 수를 곱한다.
n*n
F(idx, count)
F(idx, count) = max) if cont < 1 F(idx-1, cont+1), F(idx-2,0) ) + cons[idx]
max ( F(x+1, y), F(x, y+1), if A[x] == B[y] : F(x+1, y+1) +1 )
Lower Bound, Upper Bound