이 블로그는 방문자 통계를 위해 티스토리 기본 기능과 Woopra를 사용합니다. 원하지 않으신다면 사용하시는 웹 브라우저에 내장된 DNT 헤더를 켜고, JavaScript를 끄셔도 무방합니다.
이 블로그 방문자의 약 60%는 네이버 검색을 사용하십니다. 을 이용하시면 더 유용한 정보를 쉽게 얻게 되실 수도 있습니다. [mediatoday]
« 2019/11 »
          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
블로그 이미지
제가 주제인 블로그... 그냥 주제 없는 블로그입니다. 전공 분야나 예전 관심 분야 등등에 관한 글이 우선입니다만, 두어 문단을 넘길 만한 글이라면 대강 정리해 기록합니다. 학부생입니다. 트위터에서 볼 수 있습니다. http://aurynj.net/ 어­리


 
 
2번 문제는...ㅅㅂ


작년에 처음 정올 나갔을 때 메모리 관리하다가 병신이 된 까닭에

(그 때 malloc 쓰는 다 된 코드였는데 얘가 오버플로. 안 했으면 통과였다.)


그래서 올해는 아예 메모리 관리는 생각도 안 하고 나갔다.



근데 낭패.


  KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
  예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선상에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
  탑들의 개수 N과 탑들의 높이가 주어질 때, 각 각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
  실행파일의 이름은 TOWER.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)
5
6 9 5 7 4
출력 (OUTPUT.TXT)
0 0 2 2 4

..
.....
.......
쉬바.

일단 코드를 짜 봤다.


탑의 높이가 최대 100,000,000이면 long int로 가야 한다. (unsigned short int는 0~65535)

문제의 조건에서 탑의 높이가 같아도 신호를 받을 수 있다는군.

#include <stdio.h>

int main()
{
    int n, i;
    int tower[500000];
    FILE *fp;

    fp = fopen("INPUT.TXT", "r");
    fscanf(fp, "%d", &n);

    for (i = 0; i < n; i++)
        fscanf(fp, "%d" tower + i);

    /* 조금만 기다려. 이제 여기서 무언가 보여줄게. */

    return 0;
}
뭐 이 정도면 예비 작업으로 훌륭하다. (-_-)


이제 할 일은 저걸 배열에 저장해 가면서,

탑 하나하나에 그 이상의 높이를 가진 인덱스를 체크해 갱신하는 것이(랄까)다.

500000개의 배열 선언하면 되는데, 귀찮으니까 tower[500001]로 선언하고 [0]=100000000으로 세팅.
#include <stdio.h>

int main()
{
    int n, i, j;
    int higher = 0;
    int tower[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;
}
별 것 아니군.

과연 그럴까. 컴파일 성공. 2번 문제가 이렇게 쉬울 리가 없는데..?



근데 링크 끝내고 실행시키니까 이 웬수가 멎는다.

내가 뭘 잘못했냐 이 웬수야-_-;

코드를 아무리 체크해 봐도, 종이에 flow 그려 가며 해 봐도 문제가 없다.


디버그 모드 돌입.

근데 한 방 날려 주시는 우리의 VC++.

Unhandled exception in tower.exe: 0xC00000FD: Stack Overflow.
그랬다.


젠장 메모리 관리 연습 안 하고 가니까 메모리 관리하는 문제가 나오는군.



내 생각이 맞는지 확인하기 위해 아래의 코드 두 개를 컴파일해 봤다.
int main()
{
    int tower[500001];
    return 0;
}
같은 에러 메시지.

#include <stdio.h>

int main()
{
    int n, i, j;
    int higher = 0;
    int tower[50001];
    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;
}
정상 작동-_-;

솔루션은 다음 글에서나 공개해야겠다.

댓글을 달아 주세요

현재 난 고2다. 고로 난 고등부 정올에 나갔다(-_-;)
중딩 때부터 나갔으면 전국본선을 노릴 만하다고 생각하지만...
올해가 고작 2년째라서 상당히 병맛이다. 결과는 6월 5일에 나온다는군.

잡설은 집어치우고 각설.

연속구간

  여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하라.
 예를 들어 세 개의 숫자 12345123, 17772345, 22233331이 주어졌다고 하자. 12345123은 연속하여 같은 숫자가 나오는 것이 없으므로 1을 출력하고, 17772345는 7이 세 개 연속하여 나오므로 3을 출력하며, 22233331의 경우에는 2가 세 개, 3이 네 개 연속해서 나오므로 그 중 큰 값인 4를 출력하여야 한다. 
 실행파일의 이름은 CONT.EXE로 하고 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
  입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄부터 셋째 줄까지 각 줄에 하나씩 세 개의 여덟 자리 양의 정수가 주어진다.

출력 형식
  출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에서 셋째 줄까지 한 줄에 하나씩 각 입력된  수 내에서 같은 숫자가 연속하여 나오는 가장 긴 길이를 입력 순서대로 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)
12345123
17772345
22233331
출력 (OUTPUT.TXT)
1
3
4
ㅋㅋ 난 이래서 티스토리가 좋아 ㅋㅋㅋㅋㅋ


일단 이 문제는 상당히 단순하다.

입력은 8자리 자연수 3개뿐이다. 앞에 자료의 수가 나오고 어쩌고 없다.

그러면 일단 파일을 열고 3개의 정수를 입력받아 보자.

#include <stdio.h>

int main()
{
    FILE *fp;
    int a, b, c;
    fp = fopen("INPUT.TXT", "r");
    fscanf(fp, "%d %d %d", &a, &b, &c);
    /* 이제 a, b, c를 가지고 장난을 치겠지.
     * ............
     */
     return 0;
}
-_-;
미쳤냐.

실제로 써야 하는 데이터는 수가 아니라 숫자일세..

숫자를 써야 하는데 뭐하러 수로 입력받아서 다시 자릿수로 나누고 ㅈㄹ(-_-;)을 하세요.

그러므로 그냥 내용을 입력받을 때 8자리 문자열 배열로 입력받으면 된다.

#include <stdio.h>

int main()
{
    FILE *fp;
    char a[9], b[9], c[9]; // 왜 9개인지는 알지ㅡ_ㅡ
    fp = fopen("INPUT.TXT", "r");
    fscanf(fp, "%s %s %s", a, b, c);
    /* 이제 a, b, c를 가지고 장난을 치겠지.
     * ............
     */
    return 0;
}
이렇게.

그런데 생각해 보면 실제로 정올 문제 중 배열에 저장하지 않고 풀 수 있는 문제가 있다.

역대 1번 문제들이 그랬다. -_-;

특히 9*9 배열 중 최댓값을 찾는 문제는....

배열 만들어서 모조리 저장하고 다시 처음부터 찾고 하는 방식을 쓰면

두 배의 시간이 걸린다. 병맛이지.



이 문제도 마찬가지. 처음부터 다시 짜 보자.

일단 8자리 문자열(.....)이 세 개 주어지며, 따로 처리하게 되어 있으므로,

{하나 처리하고 하나 출력하고}를 세 번 반복하자.

그럼 파일 포인터가 두 개 필요하고, 세 번 루프를 돌아야 한다.

#include <stdio.h>

int main()
{
    FILE *fpi, *fpo;
    int i, j, conti;
    char str[8];
    fpi = fopen("INPUT.TXT", "r");
    fpo = fpoen("OUTPUT.TXT", "w");
    for (i = 0; i < 3; i++)
    {
        fscanf(fpi, "%s", str);
        /* 이제 j를 사용해 str에서 가장 큰 반복 횟수를 conti에 저장할 거다. */
        fprintf(fpo, "%d\n", conti);
    }
    return 0;
}
-_-;

나아진 게 없잖아.

보기에만 좋아졌지 배열에 저장한 후에 처리하는 건 달라지지 않았다.

(아니, 메모리는 덜 쓴다. 실제로 많은 다중데이터 문제에서 이래야만 한다.)

그래서 루프를 한 번 더 돌린다-_-;

흐르듯이 처리하려면 이전 문자랑 비교해야 하니까 문자 변수를 두 개 두자.
하나는 입력, 하나는 비교용.
#include <stdio.h>
 
int main()
{
    FILE *fpi, *fpo;
    int i, j, conti;
    char n, c;

    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");

    for (i = 0; i < 3; i++)
    {
        conti = 1;
        for (j = 0; j < 8; j++)
        {
            fscanf(fpi, "%c", &n);
            /* n이 이전 글자와 같으면 conti++, 다르면 conti = 1 */
        }
        fprintf(fpo, "%d\n", conti); // 반복 횟수 쓰고 한 줄 내리고.
    }
    return 0;
}
미친 게 틀림없다.

......
뭐 어때.

구조적인 프로그래밍 갖다 버리고 속도만 유지하고 싶은가.

문자로 받아서 7번 비교하고 결과 출력하는 작업을 코드에 똑같이 세 개 넣으면 된다.

그건 좀 아니잖아-_-;

어쨌든 이제 진짜 중요한, 주석으로 처리한 부분을 연구해 보자.

일단 '이전 문자'와 비교해야 한다.
그런데 처음 시작, 인덱스 0일 때 문제가 생긴다.

이전 문자가 누구세요...-_-;;;

그래서 사실 j에 관한 for문 아래에 if문을 둬서

j가 0일 때에는 묻지도 따지지도 않고 conti = 1, c = n으로 퍼 줘야 하겠다.


근데 저 j에 관한 for문은 알짜로 24번 실행된다.

시간 낭비가 생길 위험이 있으므로 일단 하나를 for문 밖에서 입력받고,

j는 1부터 시작하자. 미안.
#include <stdio.h>
 
int main()
{
    FILE *fpi, *fpo;
    int i, j, conti;
    char n, c;

    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");

    for (i = 0; i < 3; i++)
    {
        conti = 1;
        fscanf(fpi, "%c", &c);
        for (j = 1; j < 8; j++)
        {
            fscanf(fpi, "%c", &n);
            if (n == c) //위에서 주석문으로 처리한 부분을 구현한다.
                conti++;
            else
            {
                conti = 1;
                c = n;
            }
        }
        if (i != 0) fprintf(fpo, "\n"); /* 출력 형식을 제대로 맞춘다. */
        fprintf(fpo, "%d", conti);
    }
    return 0;
}

잘~ 실행된다.

꺼져ㅋㅋㅋㅋㅋㅋ 잘 실행되기는 무슨 ㅋㅋㅋ

문제가 뭘까요-_-;

이 코드의 문제점은 conti가 계속 갱신된다는 점에 있다.

최대 conti가 저장되지 않는다.....


그리하여 정말 정상적인 코드...
#include <stdio.h>
 
int main()
{
    FILE *fpi, *fpo;
    int i, j, conti, max;
    char n, c;

    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");

    for (i = 0; i < 3; i++)
    {
		max = 1;
        conti = 1;
        fscanf(fpi, "%c", &c);
        for (j = 1; j < 8; j++)
        {
            fscanf(fpi, "%c", &n);
            if (n == c)
                conti++;
            if (max < conti)
                max = conti;
            if (n != c)
            {
                conti = 1;
                c = n;
            }
        }
        if (i != 0) fprintf(fpo, "\n");
        fprintf(fpo, "%d", max);
    }
    return 0;
}
...라고 생각했으나 작동 결과가 영 병맛인 코드.

결론부터 말하자면, fscanf를 디버그 모드에서 돌려 보자,
%c 자리에 이쁘게 10을 넣어 주시더라. ASCII 10이 뭐게요.

쉣. 읽을 공백은 안 읽고 웬 줄바꿈은 읽고...
시험장에서 같은 문제에 걸려서 대충 루프 내 if문 조정하면서 해결했다.

그러나 제대로 된 해법은 그냥 한 번 더 입력받기.
#include <stdio.h>
 
int main()
{
    FILE *fpi, *fpo;
    int i, j, conti, max;
    char n, c;

    fpi = fopen("INPUT.TXT", "r");
    fpo = fopen("OUTPUT.TXT", "w");

    for (i = 0; i < 3; i++)
    {
		max = 1;
        conti = 1;
        fscanf(fpi, "%c", &c);
        for (j = 1; j < 8; j++)
        {
            fscanf(fpi, "%c", &n);
            if (n != c)
            {
                conti = 1;
                c = n;
                continue;
            } // 이걸 먼저 처리해서 continue로 보내 버리면 좀 더 빠르다.
            conti++;
            if (max < conti)
                max = conti;
        }
        fprintf(fpo, "%d", max);
        if (i < 3)
        {
            fprintf(fpo, "\n");
            fscanf(fpi, "%c", &c);
        }
    }
    fclose(fpi);
    fclose(fpo); // 파일 포인터 닫는 것도 잊지 말고.

    return 0;
}
인정한다. 모범답안은 이것보다 빠를 거다...-_-;


그냥 바로 적당한 코드 해설했어야 하는데 잡소리가 너무 길었습니다.
글이 길어진 점 사과드립니다 0_0;

댓글을 달아 주세요

  1. Lonewolf dlbo 2009.06.02 18:48 신고  댓글주소  수정/삭제  댓글쓰기

    fscanf("%1d")를 활용했다면 공백이나 캐리지리턴을 쌩깔 수 있었을텐데 아쉽네요.. ㅁ_ㅁa

    • 어­리 2009.06.03 21:40 신고  댓글주소  수정/삭제

      아차. 그런 간단한 걸 잊었습니다.;;;
      그나저나 원래 fscanf에서 공백 등등 무시한다고 알고 있는데 어쩌다가 CR은 먹어치우는지..
      솔직히 그냥 스트링으로 읽어서 처리하는 게 빨랐을 수도 있다고 생각해요.-_-;

  2. Larth 2009.06.03 20:08 신고  댓글주소  수정/삭제  댓글쓰기

    정올 출전하시는군요. 좋은 결과 있으시길.


    근데 이쯤이면 정올 지역본선 끝났나요?
    제 기억엔 기말고사 준비 전에 끝났던 것 같아서 -_-a;;;

  3. 지환태 2009.06.07 22:56 신고  댓글주소  수정/삭제  댓글쓰기

    저도 풀어 보았습니다 @_@

    • 어­리 2009.06.08 23:13 신고  댓글주소  수정/삭제

      잘 푸셨네요. 시간은 얼마나 걸리셨는지@_@
      1번 문제인데 그다지 많이 소모하지는 않았을 것 같군요.

      저도 위쪽에서는 char 배열로 풀까 했는데,,,,
      용량이 커질 때의 일반해법을 생각해서 좀 병맛나게 풀었습니다.
      제 것과 비교해서 어느 쪽이 빠른지는 생각 좀 해 봐야겠네요.

  4. BLUEnLIVE 2009.09.09 22:36 신고  댓글주소  수정/삭제  댓글쓰기

    저같으면 걍 fgets() 올인.

    (fscanf라고 오타를 냈네요. 바부같이. ㅠ.ㅠ)

    • 어­리 2009.09.12 10:46 신고  댓글주소  수정/삭제

      fscanf라고 쓰셨을 때 보고 무슨 말씀이신가 했습니다.
      fgets()가 제일 좋은 방법이기는 하죠. 사실 fscanf(fpi, "[^n]", s)로 할지 등등 생각해 봤습니다만 제 컨셉은 위와 같이 하나씩 입력하면서 카운트해 주는 것이었어요. :D

Programming: Problem-Solving Process.

Sablog Models/알고리즘 | 2009.05.03 00:08 | Posted by 어­리

블로그를 시작하면서 내용이 담긴 첫 글.

컴퓨터 프로그래밍이란 일반적으로,

  • 특정한 프로그래밍 언어를 이용해
  • 하나 이상의 추상적 (수학적) 알고리즘 또는 프로세스를 (프로그램을)
  • 구체적인 (실행 가능한) 형태로 구현

하는 과정을 의미한다. 이를 하나씩 짚어 보자... 프로그래밍이 포함하는 과정은 크게 두 가지이다.

첫째로 문제를 파악하고 사용 가능한 알고리즘을 선정하여 조직하는 단계이다. 프로그램도 존재 목적이 있다. 적당한 플랫폼상에서 일정한 역할을 수행하기 때문이다. 이것은 시스템의 특정 부분을 예정된 대로 변화시킨다. 이것을 프로그래밍의 의도로 볼 수 있다. 이 의도를 실행시키기 위해서는 논리적인 문제 해결 절차가 필요하다. 결국 프로그래밍에서는 코딩의 전 단계에 수학적 문제 해결 과정이 들어 있는 것이다. 다시 말해 프로그래머는 자신이 짜야 하는 프로그램(목적)을 파악해, 소스 코드로 바꿀 수 있는 수학적 계획의 형식으로 조직할 필요가 있다. 일종의 일반화이다.

둘째로 조직된 알고리즘을 소스 코드로 변환하는 단계이다. 이 작업이 대개 코딩이라고 불린다. 알고리즘이 좋아도 컴퓨터가 읽을 수 없으면 무용지물이므로, 프로그래머는 일반해법을 적당히 바꾸어 컴퓨터에 넣어 준다. 그래야 비로소 컴퓨터가 명령을 수행할 수 있는 것이다. 여기에서 특정한 프로그래밍 언어가 쓰이게 되며, 프로그램의 많은 부분이 결정된다. 대체로 둘째 단계는 첫째 단계에 비해 수단에 불과하다는 인식이 강하지만, 당장 몇 가지 언어를 접하게 되면 다른 생각을 가질 수 있다.

아무튼 굉장히 간단해 보이는 두 단계이지만, 아마추어가 프로그래밍을 이렇게 분리해 생각하기는 어렵다. 정보 올림피아드에 대비하지 특별히 않은 초보 프로그래머들은 대회에서 당혹감을 겪는다. 초보 프로그래머에게 첫 번째 단계는 거의 없는 것이나 마찬가지인 반면에, 정보 올림피아드 대회에서는 첫 번째 단계가 매우 중요하다는 점 때문이다. 현재 많은 큰 프로젝트들이 컴포넌트 단위로 프로젝트로 진행되며, 오픈 소스로 웹 상에서 코딩이 이루어지는 것도 많다. 이런 프로젝트에서 첫 번째 단계는 특히 더 중요해진다. 한편, 두 번째 단계에 대한 지식도 함께 갖고 있어야 일이 제대로 진행될 수 있다.

영 필요 없는 소리만 열심히 하고 있군. 블로그의 미래가 굉장히 걱정된다.

댓글을 달아 주세요

  1. Lonewolf dlbo 2009.05.03 01:16 신고  댓글주소  수정/삭제  댓글쓰기

    syntax Highlighter 라는 구글의 서비스가 있습니다. textarea태그의 확장형인데요... 구글이나 티스토리서 검색하시면 구문강조 기능과 설치법에 대해 상세한 설명이 나옵니다.

  2. Lonewolf dlbo 2009.05.03 01:17 신고  댓글주소  수정/삭제  댓글쓰기

    http://bluenlive.net/495?srchid=BR1http%3A%2F%2Fbluenlive.net%2F495 블루앤라이브님께서 신형 syntaxhighlighter에 대해 포스팅을 띄워두셨네요. 여기 참조하시면 되지 싶습니다.