알고리즘(71)
-
[백준/C++] 2504번 괄호의 값
문제: www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제풀이 스택과 배열을 이용하여 문제를 풀었다. 스택의 크기로 괄호가 몇 겹이 있는지 알 수 있고 스택의 크기를 인덱스로 하여 같은 수의 겹에 쌓여있는 수를 모두 더하고 한 겹을 벗어날 때마다 괄호 (, ]에 따라 2나 3을 곱해주었다. ( ) -> arr[s.size()] += 2 [ ] -> arr[s.size()] += 3 ) ) -> arr[s.size()] += arr[s.size()+1]*2..
2021.03.23 -
[백준/C++] 5430번 AC
문제: www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제풀이 입력되는 함수 R에 대하여 실제로 벡터 순서를 뒤집게 된다면 시간초과가 나온다. 때문에 덱을 이용하여 R이 현재까지 짝수번 입력되었다면 앞에서 함수 D(pop_front)를 실행하고 홀수번 입력되었다면 뒤에서 함수 D(pop_back)를 실행한다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; //테스트 케..
2021.03.22 -
[백준/C++] 18258번 큐 2
문제: www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제풀이 큐의 메소드들을 구현하는 문제이다. 명령의 수 N의 범위가 1 ~ 2,000,000 이므로 큐의 크기를 2,000,000으로 선언했다. 코드 #include using namespace std; void push(int); int pop(); int front(); int back(); int size(); int empty(); int fir = 0, rear = 0;..
2021.03.21 -
[백준/C++] 1021번 회전하는 큐
문제: www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제풀이 덱을 순차 탐색하여 뽑아야 하는 숫자의 인덱스를 찾은 후 front에서의 거리와 back에서의 거리를 비교하여 더 적은 쪽으로 덱을 회전시킨다. 코드 #include #include using namespace std; void funcL(deque& d, int num){ while(d.front() != num){ d.push_back(d.front()); d.pop_front(); } ..
2021.03.21 -
[백준/C++] 2493번 탑
문제: www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제풀이 스택을 사용하여 i번째 탑의 높이보다 크고 다른 탑에 의해 가려지지 않은 탑들만 스택에 남겨야한다. (i번째 탑에 서서 왼쪽의 탑들을 보았을 때 보이는 탑들) 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; pair tower[N]; f..
2021.03.20 -
[백준/C++] 5397번 키로거
문제: www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제풀이 C++ STL list iterator를 이용하여 문제를 풀었다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int T; cin>>T; list l; while(T--){ string str; cin>>str; list::iterator cursor = l...
2021.03.19