그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제를 핵심만 남겨서 해석해보자면 다음과 같다. "정렬되지 않은 정수 배열이 주어질 때 연속적으로 증가하는 가장 큰 정수 배열의 길이를 구하여라" 이는 흔히 LIS (Longest Increasing Subsequence), 즉 최장 증가 부분 수열이라 불리는 문제이다. 다음과 같은 논리로 위와 같은 문제를 DP로 풀 수 있다. 먼저, DP 배열은 다음과 같이 선언한다. DP[지금 탐색 중인 상자의 번호]..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net AC라는 새로운 언어를 사용하여 정수 배열을 다루는 연산을 해주는 걸 처리하는 문제이다. AC언어는 'R'과 'D'로 이루어진 언어이다. R함수는 정수 배열을 뒤집는다. D함수는 정수 배열의 첫 번째 숫자를 버린다. 이 두 가지 연산을 하는 문제인데 생각보다 까다로운 부분이 두 가지 정도 있다.. 1. 정수 배열을 정수를 띄어쓰기로 구분해서 주는 것이 아니라 문자열 형식으로 준다. 2. 정수 배열의 크기가 최대 100,000인데 명령이 100,000번까..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 이 문제는 처음과 끝이 연결되어 있는 큐가 있을 때 큐의 처음으로 이동시켜서 뽑아야 하는 원소들을 뽑아야 하는데 왼쪽으로 전체 한 칸 미는 연산과(처음의 원소는 끝으로) 오른쪽으로 전체 한 칸 미는 연산을(끝의 원소는 처음으로) 최소한의 횟수로 해서 뽑는 문제이다. 문제를 푸는 방법은 일단 deque를 하나 선언해주고 회전하는 큐의 크기만큼 자연수를 넣어 deque를 초기화시켜준다. 그 뒤 뽑..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 자료구조 중 덱을 구현하는 문제이다. 나는 그냥 무식하게 조건의 2배 이상 크기의 배열을 잡고 그 중간부터 head와 tail을 이용하여 deque를 구현했다. 굳이 그럴 필요 없이 C++의 stl인 deque를 사용해서 풀어도 되는 문제이다. 신경 써줄점은 명령을 제대로 받아서 구분해서 작업을 처리하는 부분이다. 나는 명령어가 몇 개 안되기 때문에 그냥 문자열의 일부분을 보고 구..

https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net C로 문제풀던 시절에 세그먼트 트리를 공부하고 풀었던 문제이다. 어느 구간의 비디오를 빌려올 때 그 구간에 모든 비디오가 다 있는지 체크하는 문제이다. 당연히 브루트 포스로 범위 안을 모두 확인해보면 TLE가 난다. 문제를 푸는 핵심은 어느 구간 [x, y]의 비디오를 빌려왔다고 가정하면 그 구간의 비디오 번호의 최댓값과 최솟값이 있을 것인데 겹치는 번..