본문 바로가기
반응형

전체 글

10828번 10828번 - 스택 시뮬레이션 문제, 나는 vector 를 이용해서 스택을 구현했다. stack 은 마지막에 들어온게 처음에 나가는 LIFO 구조란 점만 기억해서 문제를 풀어주면 끝! ### push 1 이런식으로 숫자를 받는 경우, cin.clear() 를 해줘야 한다는 점 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include#include#includeusing namespace std; int main(){ int N; cin >> N; vector st; while (N--) { string s; cin >> s; ci.. 더보기
9012번 9012번 - 괄호 괄호는 stack을 이용해서 문제를 풀 수가 있다. stack 에 '(' 를 담으면서 ')' 나오면 하나씩 pop 해주면 되기 때문이다. 이런식으로 짝을 맞추는 경우에는 stack 이 유용하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include#include#includeusing namespace std; int main(){ int tc; cin >> tc; while (tc--) { bool chk = true; string ps; cin >> ps; stack st; for (int i = 0; i 더보기
1021번 1021번 - 회전하는 큐 처음에 문제를 잘못읽었다. 문제에서 주어진 순서대로 출력하는게 아닌, 세개를 출력하는 방법의 최솟값인 줄 알았다. 그래서 문제를 풀었더니 너무나 어려웠다.. 근데 문제를 다시 읽어보니 순서대로 출력하는 문제였다. 그래서 deque 를 써서 문제를 쉽게 풀 수 있었다. 목표로 하는 번호가 앞에서 가까운지, 뒤에서 가까운지를 파악한 후에 앞에서 가까우면 front 에서 pop 해서 back에서 push 를 해주면 되고, 뒤에서 가까우면 back 에서 pop 해서 front 에 push를 하면 된다. (해당하는 번호가 deque 의 0번 인덱스에 올 때까지) 그러면서 이러한 과정이 몇번 일어나는지 숫자를 세주면 된다. ##문제를 제대로 읽는 습관을 갖자 1234567891011121.. 더보기
9084번 9084번 - 동전 D[k][pre] = k 원을 만드는 방법중 이전에 coin[pre]를 쓴 경우의 수. 처음에 그냥 D[k] 로 하면 중복되는 값들이 너무 많이 나왔다. 그래서 pre를 추가 시켜서 문제를 풀 수 있었다. ▼▼▼▼부가설명 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include#includeusing namespace std;int n, m;int coin[21];long long D[10001][21]; long long go(int k, int pre){ if (k = 0) { return D[k][pre]; } if (D[k][pre] == -1) { .. 더보기
2688번 2688번 - 줄어들지 않아 처음에 완전탐색으로 풀었지만, 시간초과, 시간초과가 날 줄은 알고 있었다. 그래서 DP를 이용해서 풀었다. 처음에는 1차원 DP로 했더니 틀렸다.. 그래서 하나씩 써보면서 보니까 바로 오류가 있다는 것을 알아냈다. 그래서 2차원 DP를 이용했다. D[n][k] = n자리 숫자이고 이전에 사용한 숫자가 k 일때, 만들 수 있는 경우의 수 1234567891011121314151617181920212223242526272829303132333435363738394041#include using namespace std;int n;long long D[65][10];long long go(int k,int pre){ if (k == 0) { return 1; } if (D[k][p.. 더보기
2941번 2941번 - 크로아티아 알파벳 크로아티아 알파벳을 string 배열에 저장하고, 완전탐색을 통해서 string 배열안에 있는 값과 맞다면 그 만큼 pos 를 이동시킨다. 만약 string 배열안에 있는 값이 아니라면, pos를 1만 이동시킨다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include#includeusing namespace std; string croatia[8] = { "c=","c-","dz=","d-","lj","nj","s=","z=" };string str;int ans = 0;void dfs(int pos,int sum){ if (pos == str.size()) .. 더보기
1890번 1890번 - 점프 점프할 때마다 맵이 줄어들기 때문에, DP로 풀 수 있었다. 따라서 D[x][y] = x,y 에서 도착지에 갈 수 있는 경우의 수 라고 점화식을 세우고 문제를 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include#includeusing namespace std;long long D[101][101];int map[101][101];int n;long long go(int x, int y){ if (x >= n || y >= n) { return 0; } if (x == n - 1 && y == n - 1) { return 1; } if (.. 더보기
1541번 1541번 - 잃어버린 괄호 처음에 완전탐색을 할까 했지만, 생각보다 복잡할 것 같았다. 그런데 그리디적인 방법으로 생각해보면, - + + + - + + - + + 이 나오면 괄호를 씌워, 전부다 - 로 바꿀 수 있다. 즉 - ( + + + ) - (+ +) - (+ +) 이런식으로 전부 -로 바꾸면 최소값을 구할 수 있기 때문이다. 따라서 처음에만 +를 해주고, - 가 나온 이후로는 그냥 빼주기만 하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#include#includeusing namespace std; int main(){ string str; int cnt .. 더보기
반응형

티스토리툴바