이러쿵저러쿵


수열 추정 문제

 

 감소하지 않는 수열의 일부가 주어져 있다. 현재 주어진 수열의 마지막 수 다음에 있는 수들은 무엇인지를 추정하고자 한다. 수열에서 수를 추정할 때 다음과 같이 수의 차를 이용하는 방식이 있다. 이 방식을 예를 들어 설명하기로 한다. 수열 3, 6, 10, 15가 주어져 있다고 하자. 이 수열의 차를 한번 구하고, 원소의 수가 둘 이상이면 다음과 같이 이 과정을 반복한다.

 

 

  3    6   10   15

 3    4    5

 1    1

 

 

 위 수열에서 5번째 수를 추정하기 위해서 마지막 행은 상수로 모두 같은 수가 반복된다고 가정한다. 위에 예에서는 아래와 같이 마지막 행에 0을 추가하고, 역으로 계산하여 5번째 원소가 21이라고 추정할 수 있다.

 

 

  3    6   10   15   21

 3    4    5    6

 1    1    1

 

 

 입력으로 길이가 n인 수열과 양의 정수 k가 주어질 때, 이 수열에서 (n+1)번째 수부터 (n+k) 번째까지 개의 수를 추정하여 출력하는 프로그램을 작성하시오. n과 k는 모두 10,000 이하라고 가정한다.

 

 

 

// C언어 코드

 

#include <stdio.h> // printf()
#include <conio.h> // getch()

 

int n, k, space = 0; // n : 입력된 수열의 길이, k : k : 출력될 수열의 길이(결과값), space : 같은수가 반복되는 수열이 나타났을 때, 그 반복되는 숫자
int data[10000] = {0, }; // 입력된 수열의 실제 데이터 값
int sumCount = 0; // 수열의 깊이 - 같은 수가 반복되는 수열을 찾기 위해 나타난 수열의 개수
int sumData[100] = {0, }; // 반복되는 수열을 찾기 위해서 지금까지 나타난 수열들의 가장 마지막 값을 저장하고 있는 배열 (임의로 100이하로 설정하였습니다. 변경가능)

 

void InputFile(); // 파일(Input.txt)로 부터 데이터 읽기
void FindResult(); // 결과를 얻고, 파일(Output.txt)로 쓰기

 

void main()
{
    InputFile();
    FindResult();
    printf("작업이 완료되었습니다. 결과 : Output.txt");
    getch();
}

 

void FindResult()
{

int i, j, x = 0; // i,j : for문을 위한 임시 변수,  x : 수열이 저장된 배열값의 위치를 가리키는 임시 변수
int temp[2] = {0, }, result = 0; // temp[] : 새로 설정된 값을 기존의 data[]배열에 덮어쓰기 위해 임시로 그 값을 저장하고 있는 변수, result : 결과값 Output.txt에 출력될 값
bool changeTemp = false; // temp[]를 번갈아 사용하기 위해 체크할 변수, data[]배열에 새로운 값을 쓸 때, 계산이 끝나지 않은 기존의 변수가 임의로 삭제되는 것을 방지하기 위한 방법

 

sumData[sumCount++] = data[n-1]; // sumData[0]에 입력된 수열의 가장 마지막 값을 넣는다. (sumData 배열은 모든 수열의 마지막 값 만을 입력받는다.)

 

while(1) // 반복 횟수는 수열을 추정하기 위해 나타난 수열의 개수 - 1 ( -1 : 같은 값이 반복되는 마지막 수열은 제외)
{

if((data[x+1] - data[x]) == (data[x+2] - data[x+1])) // 같은 숫자가 반복된다면
{

space = data[x+1] - data[x]; // 마지막 수열에서 반복되는 숫자
break; // while문 종료

}

 

for(i = x; i < n-1; i++) // 입력받은 수열 반복 (항상 전부를 반복하는 것은 아니다. x값은 1씩증가)
{

if(changeTemp != true) // temp[]변수를 번갈아 사용하기 위해서
{

temp[0] = data[i+1] - data[i]; // 뒤의 숫자에서 앞의 숫자를 빼서 temp[0]에 저장
changeTemp = true; // 다시 루프가 돌때 아래의 else 문을 수행한다.
data[i] = temp[1]; // temp[1]에 임시로 저장된 값을 기존의 배열에 덮어 쓴다.

}
else // temp[]변수를 번갈아 사용하기 위해서
{
    temp[1] = data[i+1] - data[i]; //위의 if문의 내용과 동일한데, temp변수만 다름
    changeTemp = false;
    data[i] = temp[0];

}

}

 

if(changeTemp != true) // sumData에 수열들의 마지막 값을 저장한다. (data[i] = temp[0]or[1] 는 위의 for문 내와 동일)
    sumData[sumCount++] = data[i] = temp[1];

else
    sumData[sumCount++] = data[i] = temp[0];

 

x++; // x증가

}

 

sumData[sumCount] = space; // 마지막의 (즉 같은 수가 반복되는 수열) 의 그 숫자값을 sumData에 포함 (sumData는 모든 수열의 마지막 값만을 가지고 있다.)

 

FILE *fp; // 파일 포인터 개체
fp = fopen("Output.txt", "w"); // Output.txt 파일을 쓰기 형식으로 열기

 

for(i = 0; i < k; i++) // 출력할 숫자의 개수만큼 반복
{

for(j = sumCount; j >= 0; j--) 

{

result += sumData[j]; // sumData에 저장되어 있는 값을 모두 더하면 입력된 수열의 그 다음에 나타날 값을 얻을 수 있다.

 

if(j < sumCount) // sumData는 한번 result값을 얻게 되면 입력된 수열의 그 그 다음의 값을 얻기 위해 변경된다. (단 반복된 수열의 값은 바뀌지 않는다.)
    sumData[j] += sumData[j+1]; // sumData 배열에 새로운 값 설정

}

 

fprintf(fp, "%d ", result); // 파일에 결과 쓰기
result = 0; // 다음 result를 얻기 위해 변수 초기화

}

 

fclose(fp); // 파일 개체 닫기

}

 

void InputFile() // 파일로 부터 입력받기
{
      FILE *fp; // 파일 포인터 개체

fp = fopen("Input.txt", "r"); // 파일 열기

fscanf(fp, "%d", &n); // n 값을 입력받는다.
fscanf(fp, "%d", &k); // k 값을 입력받는다.

 

for(int i = 0; i < n; i++) // 파일로부터 데이터를 얻어온다.
    fscanf(fp, "%d", &data[i]);

 

fclose(fp); // 파일 닫기

}

 

* 위의 방법은 해결 법중의 하나이며, 최적의 답안은 아닐 수 있습니다.^^

(특히 어렸을 때, 작성한 것들이 기초 C 코드이고, 알고리즘도 단순합니다.)

 

 

 - 간단한 해설 -

 

수열들의 마지막(가장 큰 값들) 숫자들의 합을 통해 결과 값을 구하는 방식을 사용.

 

입력의 길이 : N
출력할 숫자의 개수 : K
계산중에 나타난 수열의 개수 : A 

알고리즘 효율 : (N * A + K * A) = A(N+K) // A는 상수값 2를 넘지 않음. O(n)

 

예1) 입력값
     4 2
     3 6 10 15

 

루프(while,for) : 첫번째 N * A 루프 (소스 코드 참조)

루프(for,for) : 두번째 K * A 루프 (소스 코드 참조)

N = 4, K = 2

Data[] = 3,6,10,15

SumData = NULL

 

루프(while,for) 첫번째 실행후 변화
Data[] = 3, 3, 4, 5 (첫번째값을 제외한 다른 값들은 기존의 값들의 차로 대체, 첫번째 값을 제하면 새로운 수열)
SumData = [0] : 15 (기존의 데이터에서 가장 큰값)

 

루프(while,for) 두번째 실행후 변화
Data[] = 3, 3, 4, 5 (값들의 차가 모두 1로 동일한 값을 가지기 때문에 값의 변화없이 루프종료)
SumData = [0] : 15, [1] : 5 (두번째 새로 생성된 수열의 최대값 5 추가)

 

루프 종료후
SumData = [0] : 15, [1] : 5, [2] : 1 (마지막 반복 수열의 반복 숫자 값 1 추가)
루프(for,for) 첫번째 실행 후 변화 – SumData만을 이용하여 결과 출력
SumData = [0]:15, [1]:5, [2]:1    # 15 + 5 + 1 = 21 –> (n+1)의 값
Output.txt 파일에 -> 21 출력 (n+1)
SumData변화 -> [0]:21=15+5+1, [1]:6=5+1, [2]:1
루프(for,for) 두번째 실행 후 변화
SumData = [0]:21, [1]:6, [2]:1    # 21 + 6 + 1 = 28 -> (n+2)의 값
Output.txt 파일에 -> 28 출력 (n+2)

 

 

예2) 입력값 (조금 더 복잡한 케이스)

6  3

2     7     22     55    115    212         (입력된 수열)

   5     15     33     60     97              (두번째 구해진 수열)

10     18     27     37                 (세번째 구해진 수열)

    8      9     10                       (네번째 구해진 수열)

       1       1                          (마지막 수열, 즉 A(수열의 개수 = 5))


첫번째 루프(while,for)를 모두 돌고 나면 위와 같은 작업을 반복하여 sumData[]에 212, 97, 37, 10, 1 값(각 수열의 가장 큰 값)이 저장됨.

  두번째 수열을 통한 결과
sumData[] = (212), (97), (37), (10), (1)   (각 숫자의 합 : 357, n+1의 값)
sumData[] = (212+97+37+10+1), (97+37+10+1), (37+10+1), (10+1), (1)
           = (357), (145), (48), (11), (1)  (각 숫자의 합 : 562, n+2의 값)
sumData[] = (357+145+48+11+1), (145+48+11+1), (48+11+1), (11+1), (1)
           = (562), (205), (60), (12), (1)  (각 숫자의 합 : 840, n+2의 값)
. . . . .

 

결과 값(Output.txt) : 357 562 840 

 

 

 

 

파일 내려받기 (소스코드, 실행파일, 입력파일)

 

sequenc_estimation.zip

 

 

 

저작자 표시 변경 금지
신고

Comment +0

티스토리 툴바