Algorithm Study Algorithm Study

팀 나누기 문제N명의 학생을 M개의 팀으로 나누려고 한다. 각 학생은 본인의 능력을 나타내는 숫자를 하나씩 갖고 있으며, 편의상 팀을 나눌 때에는 연속한 학생들을 하나의 팀으로 만든다고 하자. 예를 들어, 다음 그림은 10명의 학생을 3개의 팀으로 나누는 두 가지 예이다.각 팀의 점수는 그 팀에 속한 학생들의 점수의 합이다. 예를 들어, 첫 번째의 경우 각 팀의 점수는 9/7/14 가 되며, 두 번째의 경우에는 4/16/10 이 된다. 팀을 잘 나누기 위해서는, 각 팀의 점수가 비슷해야 한다. 즉, 하나의 팀의 점수가 매우 높아서는 안 된다. 따라서 점수가 최대인 팀의 점수를 최대한 적게 만들고 싶다. 위의 예제에서는 아래와 같이 나누게 되면, 각 팀의 점수가 9/11/10 이 된다. 점수가 최대인 팀은..

최소비용 팰린드롬 문제팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 우리는 두 가지 연산을 할 수 있다. 첫 째로는, 하나의 문자를 삽입하는 것이며, 둘 째로는 기존에 문자열 내에 존재하는 하나의 문자를 삭제하는 것이다. 이 두가지 연산을 통하여 주어진 문자열을 팰린드롬으로 만들 수 있다. 하나의 문자를 삽입 또는 삭제하기 위해서는 비용이 들어가며, 이는 각 알파벳마다 다르다. 문자열이 주어지고, 각 알파벳을 삽입할 때의 비용, 삭제할 때의 비용이 주어질 때, 주어진 문자열을 팰린드롬으로 만들기 위한 최소 비용을 출력하는 프로그램을 작성하시오. 입력첫 번째 줄에 문자..

팰린드롬 만들기 문제팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “abcba”, “abccba” 등이 있을 수 있다. 문자열이 주어질 때, 이를 팰린드롬으로 만들기 위하여 추가해야 하는 최소의 문자 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 문자열이 “abca” 로 주어질 경우, ‘b’만 추가하면 “abcba” 를 만들 수 있으므로, 이 때는 1개의 문자만 추가하면 된다. 또 다른 예로써, 문자열이 “adcba” 로 주어질 경우에는, 문자 2개를 추가해야 한다. 입력첫 번째 줄에 문자열이 주어진다. 이 문자열의 길이는 1,000 을 넘지 않는다. 출력주어진 문자열을 팰린드롬으로 만들기 위해서 추가해야 하는 문자 개수의 최솟값을 출력한다. 예제 입력adcba예제 ..

두 문자열 사이의 거리 문제두 문자열 A, B 가 주어질 때, 두 문자열 사이의 거리를 구하려 한다. 여기서 거리는 다음과 같이 정의된다. 문자열 A가 주어질 때, 여기서 하나의 연산은 하나의 알파벳을 삽입 또는 삭제하는 것을 의미한다. 문자열 A와 B 사이의 거리란, A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의된다. 예를 들어, 문자열 A가 “abcabcd”이고, 문자열 B가 “abccabc” 라면, 문자열 A와 B 사이의 거리는 2가 된다. 왜냐하면 문자열 A의 세 번째에 ‘c’를 삽입하고, 가장 마지막에 있는 ‘d’를 삭제하면 문자열 B를 얻기 때문이다. 두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오. 입력첫 번째 줄과 두 번째 줄에 문자열이 주어지며..

연속부분 최대합 L 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9예제 출력11 예제 입력5 -1 -2 3 -2 4예제 출력5 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokeni..

자원채취 문제N x M의 지도가 주어지며, 이 지도의 각 칸에는 자원이 존재한다. 자원의 양은 정수로 나타난다. 다음 그림은 5 x 6 의 지도에 존재하는 자원을 나타낸다.철수는 자원을 채취하는 로봇을 갖고 있으며, 이 로봇은 (0, 0) 에서 출발하여 (N-1, M-1) 에서 자원 채취를 마친다. 로봇은 한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것이다. 이 로봇을 이용하여 가장 많이 채취할 수 있는 자원의 양을 출력하는 프로그램을 작성하시오. 위의 예제의 경우 다음과 같이 채취하는 것이 최대이며, 그 양은 49이다. 입력첫 번째 줄에 N, M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 두 번째 줄부터 N x M 의 지도에 존재하는 자원의 양이 주어진다. 출력로봇을 이용하여..

제곱수의 합 문제숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.45 = 3^2 + 6^2 입력첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 출력필요한 제곱 수의 최소 개수를 출력한다. 예제 입력45예제 출력2 예제 입력38예제 출력3 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class dp_sum_squa..

직사각형 배치의 경우의 수 문제2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다. 입력첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 ) 출력가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 예제 입력3예제 출력3 예제 입력8예제 출력34 예제 입력37예제 출력87896 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..