문제를 풀다보면 때때로 기댓값을 묻는 문제들이 있습니다. 제목은 기댓값 알고리즘이지만 사실 거창한 알고리즘은 없고, 기댓값 문제의 접근방식과 대략적인 용어설명을 하려고 합니다. 사실 처음들었을때 기댓값이라는건 약간 생소할 수 있습니다. 하지만 대다수의 확률을묻는 문제들이 dp로해결하는것 과 같이, 기댓값문제들도 거진dp로 해결할 수 있습니다. 제일 쉬운 예제를 한번 보면, https://www.acmicpc.net/problem/13250 13250번: 주사위 게임 효빈이는 1부터 6까지 수가 적혀있는 6면 주사위를 가지고 있다. 매번 주사위를 던질 때마다 주사위의 윗 면에 적힌 수 만큼 사탕을 받게 된다. 효빈이가 적어도 N개의 사탕을 받기 위해 주사위를 던져야 하는 횟수의 기댓값을 구하는 프로그램을 ..
typedef long long ll; ll cache[MAX_N][MAX_N]; //use dp ll comb(int n,int r) { if(r==0||n==r)return 1; ll&ret=cache[n][r]; if(ret!=-1)return ret; return ret=comb(n-1,r-1)+comb(n-1,r); } //if n is small ll comb(int n,int r) { if(r==0||n==r)return 1; return comb(n-1,r-1)+comb(n-1,r); } nCr=(n-1)C(r-1)+(n-1)Cr 점화식을 이용한 간단한 재귀함수이다. 경우의 수의 특성상 수가 조금만 커져도 int범위를 간단히 넘어버리니 왠만한 경우에는 long long 을 선언해서 풀어주어..
본 포스팅은 구종만님의 블로그를 스크랩한 글임을 밝힙니다. http://theyearlyprophet.com/heavy-light-decomposition.html Heavy-Light Decomposition Heavy-Light Decomposition @jongman 팔로우하기 트윗하기 [처음으로] [모든 글 보기] [같은 카테고리의 글 보기: 알고리즘] 작년에 1년동안 쉬면서 한 여러 가지 일 중 하나가, 오랜만에 다시 프로그래밍 대회에 참가하는 것이었다. 비록 연습만 열심히 하고 대회에 제대로 참가하진 못했지만, 최근 나온 문제들을 풀어볼 기회가 되어서 좋았다. 최근 문제 출제 경향은 과거에 비해 꽤 바뀌었음을 느꼈는데, 기존에 출제되지 않았던 테크닉들 theyearlyprophet.com 1/..
https://www.acmicpc.net/problem/10590 10590번: Burrito King The first line contains three integers \(n\), \(A\), and \(B\) (1 ≤ \(n\) ≤ 100 000, 0 ≤ \(A\), \(B\) ≤ 109), the number of ingredients, the least amount of Albert’s joy and the maximal amount of Barney’s unhappiness. Each of the following \(n\) lines cont www.acmicpc.net 입력 The first line contains three integers n, A, and B (1 ≤ n ≤ 100..
void pick(int n,vector&picked,int toPick) { if(!toPick) { //do something with picked return ; } int smallest=picked.empty()?0:picked.back()+1; for(int next=smallest;next
int V,E,cnt=1; vectoradj[MAX_N],discoverd,finished; vectortreeEdge,forwardEdge,backEdge,crossEdge; int dfs(int u) { discoverd[u]=cnt++; for(auto v:adj[u]) { if(!discoverd[v]) { treeEdge[v]=true; dfs(v); } else if(discoverd[u]
int V,E,cnt=1; vectoradj[MAX_N],discoverd; vectorisCutVertex; int findCutVertex(int u,bool isRoot) { discoverd[u]=cnt++; int ret=discoverd[u],child=0; for(auto v:adj[u]) { if(!discoverd[v]) { child++; int subtree=findCutVertex(v,false); if(!isRoot&&subtree>=discoverd[u])isCutVertex[u]=true; ret=min(ret,subtree); } else ret=min(ret,discoverd[v]); } if(isRoot&&child>=2)isCutVertex[u]= true; return..
https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i >M; while(M--) { int type; cin>>type; if(type==1) { int a,b; cin>>a>>b; seg.update(a-1,b); } else { int l,r; //first Max,second Left Max,second Right Max pairfMax,sLMax,sRMax; cin>>l>>r; fMax=seg.query(l-1,r-1); sLMax=seg.qu..
https://www.acmicpc.net/problem/18118 18118번: 7-세그먼트 디스플레이 각 테스트 케이스마다 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 7-세그먼트 디스플레이란 아래와 같이 7개의 선분으로 글자를 표시할 수 있는 장치를 말한다. 최근 시프트는 디지털 회로에 관한 강의를 듣고 있다. 시프트가 이번 주에 받은 과제의 내용은 아래와 같다. 7-세그먼트 디스플레이 n개를 사용한 회로를 구성한다. 양의 정수 m을 입력받아, n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 표시하시오. 다행히도 입출력은 강의자료에 전부 나와 있어서 그대로 따라 하면 됐기 때문에 별로 문제가 ..
