전체 글107 [Stack] 백준 1935번 - 후위 표기식2 생각하기 문자를 숫자화하여서 index 삼아 배열에 숫자를 저장 A~Z사이면 stack에 넣고 연산자이면 stack에서 두개를 꺼내서(꺼낼때 변수 저장 거꾸로) 둘을 연산 후 다시 stack에 push #include #include #include #include #include #include using namespace std; #define endl '\n' #define MAX 1000000 int N; int alpha[26]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>N; string input; stack st; cin>>input; char letter = 'A'; double number; for(.. 2021. 2. 26. [Stack] 백준 9012번 - 괄호 생각해보기 열린괄호는 stack에 넣다가 닫힌 괄호가 나오면 stack에 열린괄호 있는지 없는지 확인 1. '('가 나타나면 모두 stack에 push로 넣어준다 2. ')'가 보이면 stack에 있는 '('을 Pop 시킨다 만약 이때 stack에 아무것도 없다면 바로 NO 3. input string의 모든 것을 다 보았다면 이때의 stack이 empty면 YES empty가 아니면 NO #include #include #include #include #include using namespace std; #define endl '\n' #define MAX 1000000 int T; // int numbers[1025][1025]; 사실상 필요가 없다 int main() { ios_base::sync_.. 2021. 2. 25. [Two Pointer] 백준 2003 - 수들의 합 2 만약 모든 경우의 수를 다 본다면 nC2가 걸리게 되어 O(n^2)이 걸린다! -> 0.5초 내에 해결해야 하기 때문에 너무 오래 걸린다 O(N)으로 풀어보자 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M, a, b, ans; // int numbers[1025][1025]; 사실상 필요가 없다 int number[10000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>N>>M; for(int i=0; i>number[i]; } int sum; while(b 2021. 2. 23. [prefix sum] 백준 11660번 - 구간 합 구하기 5 pre 배열을 (1,1)에서 (i,j)까지 정사각형 모양의 값들의 합이라고 한다면 (a, b) ~ (c, d)의 값을 구한다고 한다면 답 : pre[c][d] - pre[c][a-1] - pre[a-1][d] + pre[a-1][b-1] 그렇다면 pre 값들은 어떻게 구할 수 있을까 마찬가지로 i j 이중 for문을 돌리면서 값을 받을 때 이전의 값을 참조하면 된다 pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + input 시간 복잡도 : O(max(N^2, M)) #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M.. 2021. 2. 16. 이전 1 ··· 20 21 22 23 24 25 26 27 다음
