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

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net N개의 물건이 주어지고 그 물건들에 대한 대소관계가 M개 주어질 때 각 물건들끼리 대소 관계를 파악할 수 있는지 없는지를 파악하는 문제이다. 이 문제에서 주목해야 할 포인트는 두가지 정도이다. 1. 저울의 대소관계는 방향성 그래프의 간선으로 생각할 수 있다. 예를 들어 A B, B -> C로의 단방향 간선 두 개로 생각할 수 있다. 2. ..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 오랜만에 눈물의 AC를 받은 문제이다. LCS의 길이를 구하는 것 까지는 설명을 듣고 이해할 수 있었다. 하지만 실제 LCS를 구하는 방법에서 막혀서 시간이 걸렸다. 다음과 같은 순서로 LCS를 구하는 문제에 접근했다. 1. string2차원 배열을 만들고, DP 배열을 채울 때 string 배열도 DP가 채워짐에 따라서 똑같이 채우는 방법. 하지만..

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가 나는 문제였다. 상근이가 가진 수들을 먼저 정렬해주고 이분탐색으로 풀면 되는 문제이다. 나는 재귀로 구간을 반반 나눈 다음에 두 구간 중 수가 포함될 가능성이 있는 구간만 재귀로 똑같이 탐색하는 함수를 구현했..