수열 추정 문제
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 이하라고 가정한다.
#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
'개발&컴퓨터 > 알고리즘' 카테고리의 다른 글
| [알고리즘문제] 와일드 카드 (0) | 2015.05.03 |
|---|---|
| [알고리즘문제] 숫자 대응 (0) | 2015.04.18 |
| [소개] 알고리즘을 쉽게 이해하며 배워보기 (VisuAlgo.NET) (1) | 2015.03.15 |
| [알고리즘문제] 전화 수신 전환 문제 (0) | 2015.03.12 |
| 마방진 만들기 (소스 코드 포함) (0) | 2015.03.07 |
