https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 0 ~ 9 숫자를 1번씩만 사용하여 주어진 부등식을 만족하는 숫자를 만든 뒤 최댓값과 최솟값을 출력하는 문제입니다. bfs를 활용하여 0 ~ 9의 수 하나씩 넣은 벡터에 대해 다음에 들어올 0 ~ 9 의 수를 탐색하며 아직 해당 벡터에 없는 수이면 부등식을 만족할 때 벡터의 마지막 원소로 새로 넣습니다. 그런 다음 최댓값을 갖는 벡터 (초기값 0000..000), 최솟값을 갖는 벡터 (초기값 9..
https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1,2,3으로만 이루어진 수열 중 좋은 수열의 최소값을 찾는 문제입니다. 좋은 수열은 임의의 인접한 두 부분수열이 동일한 것이 없는 것으로 다음은 나쁜 수열입니다. ex. 33 / 123123 / 12323 1,2,3 3개의 수만 이용하여 구하는 것이므로 빈 string에 1,2,3을 하나씩 넣어보며 나쁜 수열이 나오는 경우 진행을 중단합니다. 1,2,3 순으로 dfs를 진행하기 때문에 가장 처음으로 좋은 수..
https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 입력으로 주어진 수들로 만들 수 있는 최대 수를 구하는 문제입니다. 다만 입력으로 주어진 모든 수를 사용해야하며 중복으로 고를 수 있습니다. k개의 수와 n개의 택을 할 때 어떻게든 가장 큰 수를 뽑기 위해서는 가장 큰 수를 최대한 많이 골라 이어 붙혀야 합니다. ex. 1, 23, 456 / 5개 택 => 456 23 1 1 1 < 456 456 456 23 1 또한 10..
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP 응용 문제입니다. 입력 받은 문자열에서 겹치는 것을 허용하였을 때 2번 이상 검색되는 부분문자열의 최대 길이를 구하는 문제입니다. 전형적인 KMP 알고리즘의 경우 1번 나오면 탐색을 종료하거나 모든 위치를 파악하는데 주로 쓰이지만, 2번의 카운트를 해주는 조건을 추가하면 됩니다. 문자열의 처음부터 구할 수 있는 최대 길이 (2번 이상 카운트 된) 를 m..
https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 오랜만에 알고리즘 문제를 풀었습니다 ㅎㅎ 이제 자기 전에 한 문제씩 다시 풀어야겠습니다... 길이 연결되어 있는 상황에서 길을 건너지 않고는 못 만나는 소가 몇 쌍인지 구하는 문제입니다. 반대로 생각하면 전체 경우인 kC2 에서 길을 안 건너고 만날 수 있는 경우를 빼면 됩니다. 조합으로 구하기 위해 소 번호는 자신보다 큰 소를 만날 때만 카운트합니다. ..