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

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

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수이면서 펠린드롬인 수를 찾는 문제이다. 에라토스테네스의 체 알고리즘을 사용하면 쉬운 문제다. 에라토스테네스의 체란 소수를 판별하는 일종의 브루트포스 알고리즘이다. 꼭 체에 수를 걸러서 소수만 남기는 것 같다는 이유와 그리스의 수학자 에라토스테네스의 이름을 따서 에라토스테네스의 체라고 불린다. 더 자세한 설명은 여기로! 에라토스테네스의 체 팰린드롬이란 한글로 회문 즉 앞..

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]의 비디오를 빌려왔다고 가정하면 그 구간의 비디오 번호의 최댓값과 최솟값이 있을 것인데 겹치는 번..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 암호를 구성하는 여러 조건이 주어졌을 때 주어진 조건을 모두 충족하는 가능한 모든 암호를 구하는 문제이다. 암호를 구성하는 조건들은 다음과 같다. 1. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다. 2. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있다. 모음인지 자음인지 구별하는 함수와 알파벳 순인지 구별하는 함수를 만들어서 구현했다. 사실 알파벳 ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 어느 수들이 주어지고 그 수들이 상근이가 가지고 있는 수 중 존재하는지 알아내는 문제이다. 브루트 포스로 모든 수를 비교해보고 푼다면 O(N^2)이므로 TLE가 나는 문제였다. 상근이가 가진 수들을 먼저 정렬해주고 이분탐색으로 풀면 되는 문제이다. 나는 재귀로 구간을 반반 나눈 다음에 두 구간 중 수가 포함될 가능성이 있는 구간만 재귀로 똑같이 탐색하는 함수를 구현했..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net 조합의 끝자리 0의 개수를 출력하는 문제이다. 끝자리 0의 개수를 새기위해선 식에 10이 몇번 곱해져있는가를 구하면 되는데 이건 식에 2와 5가 곱해진 횟수중 더 작은 것의 횟수와 같다. (2와 5의 곱이 10이므로) nCm = n! / (n-m)!m! 이므로 n!에 곱해져있는 2의 횟수와 5의 횟수에 각각 (n-m)!와 m!에 곱해져있는 2의 횟수와 5의 횟수를 빼면 된다. 2의 횟수와 5의 횟수를 새는 방법은 예를 들어 24!의 2의 갯수와 5의 갯수를 샌다고 가정하면 2의 갯수는..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 탐색을 통해 이분 그래프인지 아닌지 판별하는 문제이다. 문제에서 설명하는 이분 그래프의 설명은 다음과같다. "그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다." 쉽게 비유를 들면 사람들이 잔뜩 있는데 사람이 각각 정점이라고 하면 남자와 여자 두 성..