빵집
dfs와 그리디 알고리즘이 합쳐진 문제이다.왼쪽에서 오른쪽으로 이동을 하는데 왼쪽의 R개의 점에 대해서 다 탐색을 해봐야 한다.여기서 그리디를 적용해야 하는데 길이 겹치면 안되기 때문에 길 하나를 찾아도 최대한 나머지 길들에 영향을 주지 않아야 한다.즉, 위에서부터 (1,1)부터 (R,1)까지 R번의 dfs를 도는데 최대한 위로 가야 아래쪽에서 영향을 안 받는다.오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색을 해 나가면 된다.int main(){ scanf("%d %d",&R,&C); for(int i=1;iarr 배열 안에 건물의 상태를 담고, dfs를 왼쪽 시작점들에 대해서 탐색한다.int path[504];int wx[3]={-1,0,1},wy[3]={1,1,1};bool dfs(int ..
저울
저울들을 합쳐서 만들 수 없는 무게를 구하면 된다.간단하게 풀 수 있는데 그냥 무게들을 정렬해 놓고 작은 것부터 더해 나가다가 다음 무게가 이전까지의 모든 무게의 합보다 커버리면 무게의 합+1부터는 만들 수 없다고 판단하면 된다.좀 더 자세히 설명해보자면, 작은것부터 큰것까지 무게들을 정렬했을 때 1번째부터 n번째 무게까지의 합을 sum_n이라고 하자.그리고 1,2,3,...., sum_n은 전부 다 만들 수 있다고 가정하자.이 때 sum_n보다 n+1번째 무게가 작다면, sum_n과 n+1번째 무게의 합 즉, 1부터 sum_(n+1) 까지도 전부 다 만들 수 있다.(1,2,3,..., sum_n을 만들 수 있다고 가정했기 때문에 n+1번째 무게에 1,2,..., sum_n을 더하면 되기 때문)만약 su..
후위 표기식
후위 표기식은 꽤 유명한 문제인데 스택을 사용해야 한다.기호는 +,-,*,/,(,)만 등장한다.문제를 풀기 위한 스텝을 보면일단 문자 A,B같은게 나오면 그냥 출력한다.기호가 나오면 스택에 넣는데 넣기 전에 자기보다 우선순위가 높은 것들을 출력해야 한다.+,-는 자기보다 먼저 등장한 +나 -, 그리고 *,/가 전부 다 우선순위가 높기 때문에 (가 나오기 전까지 다 출력해야 한다.if(eq[i]=='+' || eq[i]=='-'){ while(!st.empty()){ if(st.top()=='(') break; printf("%c",st.top()); st.pop(); } st.push(eq[i]);}*,/는 자기보다 먼저 등장한 *,/만 출력하면 된다..
