#include #include using namespace std; int alpha[26]; int main(){ stack s; int N; string str; cin>>N; cin>>str; for(int i = 0; i >alpha[i]; } for(int i = 0; i < str.length(); i++){ if(str[i] == '+' || str[i] == '-' || str[i] == '/' || str[i] == '*'){ double a = s.top(); s.pop(); double b = s.top(); // 스택에 있는 피연산자 2개를 빼오는 행위 s.pop(); switch (str[i]) { case '+' : s.push(b+a); break;..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ※틀린 풀이 #include using namespace std; int cache[1000001]; int A[1000000]; int N; int Lis(int start){ int &ret = cache[start+1]; if(ret != -1){ return ret; } ret = 1; for(int next = start + 1; next < N; ++next){ if(start == -..
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include using namespace std; bool visited[10001]; bool visited2[10001][9]; vector a; int arr[9]; int N; int M; void combination(int cnt){ if(M == cnt){ for(int i = 0; i < M; i++){ coutarr[i]; } sort(arr,..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 유명한 0/1 knapsack problem 다이나믹 프로그래밍 문제입니다. 사실 저도 못 풀어서 결국에는 검색을 통해 알게 된 문제... https://gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. ..
#include #include #include #define INF 100000000; using namespace std; vector a[1001]; priority_queuepq; int d[1001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; int M; int start; int end; cin>>N>>M; for(int i = 1; i x>>y>>z; a[x].push_back({y, z}); } cin>>start>>end; pq.push(make_pair(0, start)); d[start] = 0; while(!pq.empty()){ int cost = pq.top().first; int cur =..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #include using namespace std; int prefixsum[1025][1025] ={0}; int dp[1025][1025]; int main(){ int x1; int x2; int y1; int y2; int N; int M; cin >> N >> M; for(int i = 1; i prefixsum[i][j]; dp[i][j] =..
