본문 바로가기

C++105

[C++] 백준 2164번 : 카드2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 문제에 풀이법이 나와있다! 맨위 카드는 버리고 그 다음 카드는 맨 밑으로 넣는다. 느낀 점 어렵지 않은 문제였다. 코드 #include #include using namespace std; int n; queue q; void func(int n) { for (int i = 1; i 1) { q.pop(); q.push(q.front()); q.pop(); } cout > n; func.. 2021. 7. 24.
[C++] 백준 18258번 : 큐 2 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 풀이 기본 큐 문제이다. STL에서 지원하는 컨테이너를 사용하면 쉽다! 느낀 점 이번 기회로 DS를 다시 복습하는 기분이라 만족스럽다. 코드 #include #include #include using namespace std; int n, tmp; string command; queue q; int main() { ios_base::sync_with_stdio(0);.. 2021. 7. 23.
[C++] 백준 17298번 : 오큰수 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 문제 풀이 오큰수를 구하는 것 자체는 어렵지 않다. 하지만 이 문제에서 중요한 것은 시간 복잡도이다. 일반적인 for문을 구하면 시간 초과가 나서 스택을 활용해서 풀어야 한다. 스택의 LIFO를 이용하기 위해서 내림차순으로 쌓아준다. (Bottom은 최댓값, top은 최솟값) 스택의 top과 비교해서 arr [i] (입력받은 i번째 값) 보다 작다면 pop 해준다. 만약 스택이 비어있으면 '-1'을 저장해준다... 2021. 7. 23.
[C++] 백준 1874번 : 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 풀이 1부터 n까지 숫자들을 스택을 이용해서 처음에 입력받은 수열을 구현하는 문제이다. {1, 2, 5, 4, 3}의 수열을 구현하기 위해서는 push, pop, push, pop, push, push, push, pop, pop, pop의 과정을 거치면 된다. 구현할 수 없는 경우에는 "NO"를 출력해주면 된.. 2021. 7. 23.
[C++] 백준 4949번 : 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 풀이 이전 문제와 비슷하다! 하나 차이가 있다면 변수 flag이다. flag의 필요성은 이전 괄호 문제와 다르게 2개의 다른 괄호가 오기 때문이 필요한 것이다. 왜냐하면 스택이 비어있는데 닫는 괄호가 오거나 괄호의 짝이 맞지 않다면 절대 맞을 수 없기 때문이다. 느낀 점 코드 자체는 어렵지 않다고 느꼈다. 근데 채점을 하는 도중에 else flag = false; break; .. 2021. 7. 22.
[C++] 백준 9012번 : 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀이 VPS인지 확인하는 법은 간단하다. 입력받은 괄호들을 스택에 차례대로 쌓고 '( )' 쌍이 나오면 스택에서 제거하면 된다. 그럼 스택에 '('이 등장하면 쌓아주고 ')'이 등장하면 제거하는 연산을 하면 된다. 함수 func 연산을 해주는 함수, 비어있으면 "YES" 아니라면 "NO" 출력 이후 스택을 초기화해준다. 느낀 점 분명히 맞은 것 같은데 계속 틀렸.. 2021. 7. 21.

티스토리툴바