이 블로그는 방문자 통계를 위해 티스토리 기본 기능과 Woopra를 사용합니다. 원하지 않으신다면 사용하시는 웹 브라우저에 내장된 DNT 헤더를 켜고, JavaScript를 끄셔도 무방합니다.
이 블로그 방문자의 약 60%는 네이버 검색을 사용하십니다. 을 이용하시면 더 유용한 정보를 쉽게 얻게 되실 수도 있습니다. [mediatoday]
« 2018/07 »
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/ 어­리


 

'프로그래밍'에 해당되는 글 2

  1. 2009.06.02 2009 정보올림피아드 지역본선 문제 Review (1) (9)
  2. 2009.05.03 Programming: Problem-Solving Process. (3)
 
현재 난 고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;

Programming: Problem-Solving Process.

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

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

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

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

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

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

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

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

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