이 블로그는 방문자 통계를 위해 티스토리 기본 기능과 Woopra를 사용합니다. 원하지 않으신다면 사용하시는 웹 브라우저에 내장된 DNT 헤더를 켜고, JavaScript를 끄셔도 무방합니다.
이 블로그 방문자의 약 60%는 네이버 검색을 사용하십니다. 을 이용하시면 더 유용한 정보를 쉽게 얻게 되실 수도 있습니다. [mediatoday]
« 2019/12 »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
블로그 이미지
제가 주제인 블로그... 그냥 주제 없는 블로그입니다. 전공 분야나 예전 관심 분야 등등에 관한 글이 우선입니다만, 두어 문단을 넘길 만한 글이라면 대강 정리해 기록합니다. 학부생입니다. 트위터에서 볼 수 있습니다. http://aurynj.net/ 어­리


이번 솔루션은 다소 간단하다.
또한 내가 작년에 쓰다가 한 문제를 망치게 만든 바로 그 방법이기도 하다....
(당시 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가 일어나지 않는다.


지난번 글에 비해 이번 글은 상당히 늦었습니다. 시험 기간이라든지 등등...

댓글을 달아 주세요

  1. 지환태 2009.07.26 20:25 신고  댓글주소  수정/삭제  댓글쓰기

    tower에는 n을 입력받은 후에 sizeof(int)*n 만큼만 동적할당하는 게 더 안전하지요.

    • 어­리 2009.07.26 20:58 신고  댓글주소  수정/삭제

      그렇지만 오해를 줄이기 위해 딱 저기만 바꿨습니다. 실제로 500001개의 int를 할당할 수 있다는 걸 보여주기 위해서이기도 합니다. 트랙백 감사합니다! :D

  2. ... 2010.05.09 18:13  댓글주소  수정/삭제  댓글쓰기

    malloc를 쓰는 것보다 tower배열을 외부변수로 만들어 버리는게 쉽지 않을까요?

  3. ... 2010.05.14 19:45  댓글주소  수정/삭제  댓글쓰기

    외부변수는 int[10000000]도 에러 안나고 잘됩니다.