정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다. www.acmicpc.net 1. 풀이 백트래킹이라고 하긴 했지만 가지치기는 안 해서 사실상 완전 탐색 문제 처음에 시간 초과가 났는데, 1. 모든 단어에 포함되어 있는 'a', 'n', 't', 'i', 'c'의 5글자를 빼주지 않아서 2. 조합 경우의 수를 재귀적으로 구할 때 vector를 인자로..

0. 문제 주소 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1. 풀이 나쁜 수열을 어떻게 판별할까 고민했던 문제. 확실히 c++로 문자열을 처리하는 부분이 약한 걸 느꼈다. 마지막에 새로 추가하는 숫자를 포함하는 부분 수열만 체크할 것이고, 이 경우 체크해야 할 인접한 부분 수열의 길이는 1부터 (현재 문자열의 길이) / 2 까지 일 것이다. 그렇기에 부분 문자열의 길이를 i라 하고, 현재 문자열의 길이를 N이라고 한다면 비교해야 할 두 부분 수열은 ..