📊알고리즘112 BOJ 3015] 오아시스 재결합 [ 1차 시도 ] - stack에 하나씩 push하다 top()와 해당 숫자를 비교한다. - 만약 (stack.top() > n; for (int i = 0; i > arr[i]; if(!s.empty() && arr[i] >= s.top()) { for (int j = idx; j num; while (!s.empty() && s.top().first < num) { total += (s.top().second); s.pop(); } if (!s.empty()) { /* 일단 top의 연속 명수를 total에 더함 앞에 더 큰 사람이 있으므로 total++ 같은 키들은 앞에 있는 사람 볼 수 있으므로 연속 .. 2022. 12. 21. BOJ 1662] 압축 [ 1차 시도 ] [ 원리 ] 1. 숫자와 괄호 모두 스택에 담는다. 2. )가 나오면 (가 나올때까지 pop하면서 temp++ 3. (를 pop하고, top의 숫자*temp 만큼 스택에 수 채우기 4. 반복 [ 실패 ] 메모리 초과가 떴다... 더보기 #include #include #include #include #include #include using namespace std; stack stk; string str; int res = 0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> str; for (int i = 0; i < str.length(); i++) { if (str[i] == .. 2022. 12. 20. BOJ 9935] 문자열 폭발 [ 1차 시도 ] - 스택에 담아서 끝에서 부터 검사하려고 했다. - 이렇게 그렇게 하면 문장이 끝까지 일치하지 않으면 다시 처음부터 검사를 해야하는데 스택을 이용하면 처음부터 다시 검사를 할 수 없다는 것을 알게됨. - 다른 방법을 모색하다 그냥 Array를 사용하면 될것 같다고 생각함. [ 2차 시도 ] - Vector를 이용해서 재도전 - 반복문을 통해 2개의 조건문을 동시에 해결하려다 out of range가 계속 떠서 그냥 차례대로 하기로함. [ 원리 ] 1. 해결할 문자열과 Boom 문자열을 string 으로 입력받는다. 2. Boom의 길이만큼 벡터에 해결할 문자열을 vector에 push_back한다. 3. Boom의 길이 == vector의 size 이면, vector == Boom 인지.. 2022. 12. 19. BOJ 2504] 괄호의 값 [ 생각해야 할 점 ] - 괄호의 짝이 맞을 때, 그 괄호는 어디에 있는 괄호인지 구분해야함 (+와 *의 차이를 위해) - 연산을 하기 위해 따로 피연산자와 수를 넣는 스택이 필요한지 고민해야함 - 입력을 모두 받고 할지, 입력받으면서 할지 고민해야함 [ 첫번째 시도 ] - 연산을 모두 받고 계산하기로 함 - 연산을 하기 위한 피연산자와 연산자를 넣을 스택을 구비함 - 다음 조건을 생각해냄 (*가 오는 경우) - (나 [가 들어오면 (+가 오는 경우) - 쌍이 맞아 pop한 후, 여는 괄호가 들어올때 (연산하는 경우) - *이 스택에 들어올때 - 스택이 비었을 때 코드가 너무 길어지고, 복잡해서 그냥 int 변수에 연산을 하기로 결정 더보기 #include #include #include #include.. 2022. 12. 19. DP 문제 맛보기 (카드 구매하기 1,2) https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [DP 문제 풀기전] - 작은 문제를 일단 풀어본다. - 그 사이에 반복되는 문제가 있는지 살펴본다. - 그 다음 문제를 풀때, 반복되는 것을 전 문제 것을 차용한다. [ 접근법 ] i장의 카드 값을 저장하는 배열(arr)과 i장의 최대 구입비를 저장하는 배열(dp)를 설정한다. 1장을 구매하는 방법은 다음과 같다. - 1장 구입 (= 0장의 최대 구입비 (dp[0]) + 1장 구입(arr[1])) 2장.. 2022. 12. 19. 후위 표기식 계산하기 [ 후위 표기식 이란? ] 일반적으로 우리가 사용하는 중위 표기식과 달리 연산자를 뒤쪽에 배치하는 표기식을 의미한다. (중위 표기식) 1+2*3/2 (후위 표기식) 12+*32/ 후위표기식을 구하기 위해 우리는 Stack을 이용한다. 이때문에 컴퓨터는 후위 표기식의 연산속도가 더 빠르다라고 알고 있다. [ 중위 -> 후위 ] - 우리가 신경써야할 것은 부호를 어떻게 배치하나 이다. - 피연산자는 순서대로 출력하고, 부호에 의해 괄호 및 우선순위가 결정된다. [ 원리 ] - stack에 연산자를 제외한 부호를 넣어준다. - 만약 *나/가 오게되면 기존에 stack에 있던 같은 우선순위의 부호들(*, /)를 출력 및 pop해주고 자신을 push한다. - 만약 +나-가 오게되면 이미 자신보다 우선순위가 높은 .. 2022. 12. 16. 이전 1 ··· 15 16 17 18 19 다음
