문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 다이나믹 프로그래밍을 활용하여 문제 해결 1, 주어진 가치의 합 k의 개수만큼 배열을 할당해준다 2, 이 때 문제의 정답인 경우의 수를 생각해보면 k의 값을 ..

KMP 알고리즘 문자열 검색 알고리즘으로 보통 ABC라는 문자열이 ABCDEFG과 같은 문자열에 포함여부를 알기 위해서는 시간 복잡도가 O(NM) 정도로 상당한 복잡도를 보이는 데 반해 KMP 알고리즘을 사용하게 되면 불필요한 계산을 건너뛰기 떄문에 복잡도를 O(N+M) 정도로 줄일 수 있다 접두사와 접미사 이 KMP 알고리즘을 이해하기 위해서는 먼저 접두사와 접미사에 대한 개념을 짚고 넘어가야 한다 접두사는 말그대로 문자열의 앞에 붙은 패턴을 의미하고 접미사는 문자열의 끝에 붙어있는 패턴을 의미한다 이것을 예로 들어 설명하면, "ABCDABC"라는 패턴이 있다면 접두사로 ABC, 접미사로 ABC가 패턴이 동일하게 반복되는 것을 알 수 있다. KMP 알고리즘에서는 위와 같은 접두사와 접미사가 같은 패턴을..

문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,..

문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 풀이 처음과 끝을 변수로 두고 해당 값을 갱신해나가는 형태로 알고리즘 로직을 짜주면 된다 임시 변수가 부분합보다 작을 경우에는 right=right+1을 통해 끝 변수를 늘려준다 임시 변수가 부분합보다 클 경우에는 left=left+1을 통해 처음 변수를 늘려준다 # 부분합 구현문제? N, S..

문제 설명 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다. 신규 유저가 입력한 아이디가 new_id 라고 한다면, 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 ..