코딩고치

1. 문제 주소 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 2. 문제 이 전에 풀었던 가장 긴 증가하는 부분수열 문제의 응용 문제이다. 이전에는 가장 긴 부분 수열의 길이만을 출력하였지만 이 문제는 부분 수열까지 출력을 해야한다. 언제 수열의 길이가 증가하는지 확인하고 그 때의 index를 배열에 저장을 하여 재귀함수를 이용하여 수열을 출력하였다. 3. 소스 코드 1 2 3 4 5 6 7 8 9 10 11..

1. 문제 주소 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 2. 문제 전체 수열을 입력받은 후 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 수열을 입력받았을 때 인덱스 i를 기준으로 앞의 숫자들과 대소 관계를 확인하여 a[i]>a[before] 이면 수열의 길이를 늘려나간다. 이때 같은 숫자가 반복되는 것을 배제할 수 있도록 조건을 넣어주면 쉽게 해결할 수 있다. 3. 소스 코드 1 2 3 4 5 ..

1. 문제 주소 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 2. 문제 n자릿수의 이진수가 있을 때 1이 연속하여 존재하지 않는 경우의 수를 구하는 문제이다. 2차원 배열을 이용하여 마지막 자릿수의 숫자가 0, 1 두 가지 경우로 나누어서 나올 수 ..

1. 문제 주소 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 자릿수 N이 주어질 때 인접한 모든 자릿수의 차이가 1이 되는 경우의 수를 구하는 문제이다. 2차원 배열(d[n][1의 자릿수의 숫자])을 이용하여 코드를 작성하였다. n=1일 때 d[1][1]~d[1][9]까지 전부 1개씩 존재한다(0으로 시작하지 않으므로 d[1][0]=0). n>=2일 때 d[n][0]은 d[n-1][1]에서 1개가 나오고, d[n][9]은 d[n-1][8]에서 1개가 나온다. 이 외에 모든 d[n][j]는 d[n][j-1]과 d[n][j+1] 1개씩 나오게 된다. 이를 이용하여 코드를 작성하였다. 3. 소스 코드 1 2 3 4 ..