이번 솔루션은 다소 간단하다.
또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다....
(당시 int 형 변수를 제곱한 만큼 신규 할당시켰더니 오버플로)
바뀐 줄은 강조해 놓았다.
이 해법이 먹히는 까닭은 간단하다.
C 컴파일러는 함수, 블럭 맨 앞에 있는 변수들을 처음에 미리 설정해 놓는다.
이들은 운영체제 상에서 하나의 함수로 취급되어, 그 정보는 스택(stack)에 저장된다.
(시스템 콜/인터럽트 후에 적절한 작업 후 call, ret가 일어나기 때문이다.)
그러나 위와 같이 해 놓으면, *tower만 스택에 저장되고,
나머지는 힙(heap)에 저장된다. 힙은 포인터를 이용해 얼마든지[?] 확장할 수 있는 구조체이다.
고로 Stack Overflow가 일어나지 않는다.
지난번 글에 비해 이번 글은 상당히 늦었습니다. 시험 기간이라든지 등등...
또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다....
(당시 int 형 변수를 제곱한 만큼 신규 할당시켰더니 오버플로)
바뀐 줄은 강조해 놓았다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, j;
int higher = 0;
int *tower = (int *)malloc(sizeof(int)*500001);
FILE *fpi, *fpo;
tower[0] = 100000000;
fpi = fopen("INPUT.TXT", "r");
fpo = fopen("OUTPUT.TXT", "w");
fscanf(fpi, "%d", &n);
for (i = 0; i < n; i++)
{
fscanf(fpi, "%d", tower + i);
for (j = 0; j < i; j++)
{
if (tower[j] >= tower[i])
higher = j + 1;
}
if (i != 0) fprintf(fpo, " ");
fprintf(fpo, "%d", higher);
}
fclose(fpi);
fclose(fpo);
return 0;
}.....;;이 해법이 먹히는 까닭은 간단하다.
C 컴파일러는 함수, 블럭 맨 앞에 있는 변수들을 처음에 미리 설정해 놓는다.
이들은 운영체제 상에서 하나의 함수로 취급되어, 그 정보는 스택(stack)에 저장된다.
(시스템 콜/인터럽트 후에 적절한 작업 후 call, ret가 일어나기 때문이다.)
그러나 위와 같이 해 놓으면, *tower만 스택에 저장되고,
나머지는 힙(heap)에 저장된다. 힙은 포인터를 이용해 얼마든지[?] 확장할 수 있는 구조체이다.
고로 Stack Overflow가 일어나지 않는다.
지난번 글에 비해 이번 글은 상당히 늦었습니다. 시험 기간이라든지 등등...
'Sablog Models > 알고리즘' 카테고리의 다른 글
| 2009 정보올림피아드 지역본선 문제 Review (3)-2 (0) | 2009.12.06 |
|---|---|
| 2009 정보올림피아드 지역본선 문제 Review (3)-1 (3) | 2009.07.18 |
| 2009 정보올림피아드 지역본선 문제 Review (2)-3 (6) | 2009.07.18 |
| 2009 정보올림피아드 지역본선 문제 Review (2)-2 (0) | 2009.06.21 |
| 2009 정보올림피아드 지역본선 문제 Review (2)-1 (0) | 2009.06.14 |
| 2009 정보올림피아드 지역본선 문제 Review (1) (9) | 2009.06.02 |
댓글을 달아 주세요
tower에는 n을 입력받은 후에 sizeof(int)*n 만큼만 동적할당하는 게 더 안전하지요.
그렇지만 오해를 줄이기 위해 딱 저기만 바꿨습니다. 실제로 500001개의 int를 할당할 수 있다는 걸 보여주기 위해서이기도 합니다. 트랙백 감사합니다! :D
malloc를 쓰는 것보다 tower배열을 외부변수로 만들어 버리는게 쉽지 않을까요?
잘 모르겠는데요, 외부 변수라면 int[500001]을 만들어도 스택 문제가 없나요?
외부변수는 int[10000000]도 에러 안나고 잘됩니다.
첨언 감사합니다. C 컴파일러 구조를 공부 안 해서 겉돌기나 했지 이런 기본을 모르고 있었군요.