[백준] 4949 균형잡힌 세상
2023. 1. 19. 15:17
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하기 모든 "(" 는 ")"와만 짝을 이루어야 함 모든 "[" 는 "]"와만 짝을 이루어야 함 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼족 괄호가 존재 모든 괄호의 짝은 1 : 1 매칭이 가능함 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 함 문제 풀이법 stac..
[백준] 5430 AC
2023. 1. 18. 18:48
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 배열이 주어지고, R과 D로 이루어진 AC 언어가 주어졌을 때 최종 결과를 구하기 R : 뒤집기 D : 맨 앞의 수를 버리기 만약 비어있으면 에러 출력 문제 풀이법 R이 들어오면 배열을 뒤집어야 하는데 R이 들어올 때마다 뒤집을 수는 없으니 bool reverse를 통해 뒤집었는지 확인한 후, deque의 특징을 살려 reverse가 true일 때는 뒤에서, false일 때는 앞에서 처리하는 것이 핵심! AC 언어를 입력받을 string st..
[백준] 1021 회전하는 큐
2023. 1. 17. 19:13
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있을 때, 이 큐에서 몇 개의 원소를 뽑아내려고 한다 다음 3가지 연산을 수행할 수 있을 때, 원소들을 주어진 순서대로 뽑는데 드는 2번, 3번 연산의 최소값을 구하기 첫 번째 원소를 뽑아냄 왼쪽으로 한 칸 이동 오른쪽으로 한 칸 이동 문제 풀이법 양방향 순환 큐를 사용한다고 했으므로 앞, 뒤 모두 pop, push 가능한 deq..
[백준] 10866 덱
2023. 1. 17. 18:53
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 만들기 push front X : 정수 X를 덱 앞에 넣음 push_back X : 정수 X를 덱의 뒤에 넣음 pop_front : 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력. 만약, 덱에 들어있는 정수가 없는 경우에는 -1 출력 pop_back : 덱의 가장 뒤에 있는 수를 빼고, 그 ..
[백준] 2164 카드2
2023. 1. 17. 18:32
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1부터 N까지의 수가 있는 카드가 순서대로 놓여져 있고, 주어진 동작을 했을 때 제일 마지막에 남게되는 카드 구하기 가장 위에 있는 카드를 버림 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김 => 위 동작을 카드가 한 장 남을 때 까지 반복 문제 풀이법 1부터 N까지 순서대로 카드가 놓여있기에 queue를 사용한다 우선 1부터 N까지 queue에 값을 넣어준 후, 카드의 개..
[백준] 10845 큐, 18258 큐2
2023. 1. 16. 19:18
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정수를 저장하는 큐를 구현한 다음,..
[백준] 17299 오큰등수
2023. 1. 13. 20:34
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 n인 수열이 주어질 때, 각 원소의 오등큰수를 구하기 오등큰수는 오른쪽에 있으면서 수열에서 등장한 횟수가 큰 수 중에서 가장 왼쪽에 있는 수 그러한 수가 없으면 오큰등수는 -1 문제 풀이법 [백준 17298 오큰수] 문제와 매우 유사하다 다른점은 원소의 크기가 아닌, 원소의 횟수를 따로 저장해서 비교해 주어야 한다는 점이다 수열을 담을 vector v monotone stack을 활용할 st..
[백준] 17298 오큰수
2023. 1. 13. 19:53
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 n인 수열이 주어질 때, 수열의 각 원소에 대해서 오큰수를 구하여라 오큰수는 각 원소의 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수이다 그러한 수가 없는 경우에는 -1이다 문제 풀이법 이 문제도 역시 Monotone stack을 사용하면 된다 수열을 담을 vector v monotone stack을 활용할 stack s; 답을 담을 vector ans; 이 3개가 필요하다 우선 수..
[백준] 6198 옥상 정원 꾸미기
2023. 1. 13. 19:23
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net n개의 빌딩이 있고, 오른쪽의 빌딩만 볼 수 있다 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있을 때, 그 다음에 있는 모든 빌딩의 옥상을 보지 못할 때, 관리인들이 옥상 정원을 확인 할 수 있는 수 구하기 문제 풀이법 문제에서 주어지는 문제 풀이 방법를 통해 문제를 풀려면, 풀리지 않는다 Monotone stack을 사용해야 한다 Monotone stack이란? 스택의 원소들을..
[백준] 2493 탑
2023. 1. 12. 19:48
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net n개의 탑이 서로 다른 높이를 가지로 있다. 탑은 수평 직선의 왼쪽 방향으로 레이저 신호를 발사하고, 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신할 수 있을 때, 각각의 탑에서 발사한 레이저 신호는 어느 탑에서 수신하는지 구하기 문제 풀이법 처음에는 굳이 stack을 써야 하나 싶었다 하지만 stack을 써야 하나씩 입력을 받으면서, 바로바로 값을 구..