본문 바로가기

스택6

[Python] 백준 #2812 크게 만들기(탐욕 알고리즘) 이번 문제는 n개의 자리를 가진 숫자에서 k개의 자리수를 제거하여 n-k개의 자리를 가진 수 중에 가장 큰 수를 만드는 것입니다.  문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2812 저는 스택(stack)을 이용한 탐욕 알고리즘을 이용해서 문제를 풀었습니다.  알고리즘은 간단합니다.  다음수가 맨 마지막수보다 크고 빼어야할 수가 있다면, 맨 마지막수를 빼고 다음수를 추가하는 방식입니다. 입력 받기n, k = map(int, input().split())- 이 부분은 `n`과 `k`를 입력받습니다. `n`은 문자열 `s`의 길이, `k`는 제거할 문자 개수를 의미합니다.스택 초기화stack = ["9"]- 가장 큰 수를 만들기 위해 사용할 스택을 초기화합니다... 2024. 8. 17.
[C/C++] 백준 #2504 괄호의 값(스택) 괄호의 짝맞춤은 처음 언어를 배우면서 스택을 이용한 활용 사례로 많이 나오는 편입니다. 복합괄호 형태로 나오게 되는데요. 복합괄호가 아니라면 굳이 스택을 사용하지 않아도 됩니다. 이 문제는 단순한 괄호 짝 맞추기보다 어려운 문제입니다. https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 저는 일단 스택을 두가지 용도로 사용했습니다. 현재까지 계산된 결과를 저장하는 용도와 짝을 맞추는 용도로 썼습니다. 계산될 결과의 경우에는 양수값을 사용하였고.. 2023. 5. 30.
[C/C++] 백준 #2493 탑(스택) 이번 문제는 스택을 이용해서 간단하게 풀 수 있는 문제입니다. 현재 골드 레벨로 설정되어 있지만, 그보다 낮은 레벨이어도 될 것으로 봅니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net n개의 타워가 왼쪽부터 차례대로 일렬로 서 있습니다. 각각의 탑 꼭대기에는 신호를 송신하는 장치가 있고, 왼쪽으로만 수평 방향으로만 송신할 수 있습니다. 모든 탑에서는 어떤 높이에서든 송신된 신호를 받을 수 있습니다. 송신된 신호는 첫번.. 2023. 5. 24.
[C/C++] 백준 #1935 후위 표기식2(스택) 후위 표기식 계산을 스택을 이용하는 것은 이미 잘 알려져 있습니다. 이 문제는 \(+\alpha\)로 변수의 개념까지 둔 문제입니다. 제 경우에는 식과 변수값을 미리 다 읽고, 식을 읽으면서 스택에서 계산을 바로 하도록 작성했습니다. 후위 표기식 알고리즘은 간단한 스택 알고리즘을 작성하시면 되는 것이라 크게 어려운 점은 없습니다. 제가 작성한 소스입니다. //---------------------------------------------------------- // baekjoon #1935 - Postfix Equation // - by Aubrey Choi // - created at 2020-01-10 //---------------------------------------------------.. 2022. 11. 16.
[C/C++] 백준 #1918 후위 표기식(스택) 후위 연산식, 후위 표기식은 모두 스택을 이용해서 문제를 풀 수 있습니다. 여기서는 중위 연산식을 후위 연산식으로 바꾸는 것인데요. 사칙연산자와 괄호만 사용하고 있어서 구현 자체가 어렵지는 않습니다. 단지 주의할 것은 연산자 우선순위입니다. 연산자 우선순위는 테이블을 이용하기도 하지만, 저는 그냥 조건문으로 해결하였습니다. 연산자가 많은 경우에는 테이블을 이용하는 것이 더 유리하겠죠. 중위식에서 후위식으로 바꾸기 위해서는 토큰을 다음과 같이 나누어야 합니다. +, -, *, /, (, ), 숫자로 나눌 수 있습니다. 1) 연산자를 저장할 스택을 마련합니다. 2) + - 연산자의 경우 스택이 비거나 ( 기호가 나올 때까지 연산자를 끄집어내어 출력합니다. 해당 연산자는 스택에 넣습니다. 3) * / 연산자의.. 2022. 11. 8.
[C/C++] 백준 #1874 스택 수열(스택) 이번 문제는 스택에 대해서 잘 이해를 해야 합니다. N의 숫자가 주어지고, 스택이 하나 주어졌을때, 1부터 N까지의 숫자를 차례로 스택에 Push할 수 있고, 스택이 비어있지 않는다면, 언제든 Pop을 한다고 했을 때, 우리는 1부터 N까지의 숫자가 한번씩 사용이 된 수열을 얻게 됩니다. 예를 들어서 Push 1, Push 2, Push 3, Push 4, Pop, Pop 을 하면, 4와 3이 출력되게 되고, Push 5, Push 6, Pop 하면 6을 출력하게 됩니다. Push 7, Push 8, Pop, Pop, Pop, Pop, Pop, Pop 하게 된다면, 8, 7, 5, 2, 1 이 나오게 되어 최종적으로 4, 3, 6, 8, 7, 5, 2, 1 이라는 수열을 얻게 됩니다. 이번 문제는 바로 .. 2022. 10. 31.

티스토리툴바