dygks232   6년 전

- 원문에는 없는 내용이지만, "어떤 루프에 대해, 해당 루프를 한번이라도 탈출한 적이 있다면, 이는 무한 루프가 아니다." 와 같은 내용의 지문을 추가해 주세요.

.

중첩 루프 케이스에 대해서 모호한 점이 있어 다음의 게시글도 살펴보았지만, 의문점을 해결하지는 못했습니다.

https://www.acmicpc.net/board/...

.

현재 문제에서 "무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다." 외에 무한 루프에 대한 어떤 설명도 없습니다.

하지만 이 조건은 무한하지 않은 루프에 대해서도 성립(입력 코드 예시: ++[-] )하는 설명이므로, 실질적으로 현재 지문 상 무한 루프에 대한 정의는 없다고 보여집니다.

위키피디아에 따르면 "무한 루프(infinite loop)는 컴퓨터에서 프로그램이 끝없이 동작하는 것으로, 루프문에 종료 조건이 없거나, 종료 조건과 만날 수 없을 때 생긴다." 라고 기술되어 있습니다.

.

본 문제에서 루프의 종료(=탈출) 조건은 "포인터가 가리키는 값이 0인지 아닌지" 로 항상 존재하기 때문에, 특정 루프가 무한루프이기 위해서는 종료 조건과 만날 수 없어야 합니다.

하지만 문제에서는 "프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다." 라고 기술되어 있습니다.

이를 종합하면, "5000만번의 명령어를 수행하고 나서 프로그램이 종료되지 않았을 때, 루프를 한번 이상 실행했으나 아직 탈출한 적이 단 한번도 없는 루프가 무한루프이다." 와 같은 결론이 도출됩니다.

.

루프가 1번 중첩된 예제 케이스 2가지를 비교하자면,

2
10 7 1 // 1st Test Case - 기대 Output : Loops 4 5
+[>+[]]
q
10 9 1 // 2nd Test Case - 기대 Output : Loops 1 8
+[>-[-]<]
q

첫번째 케이스는, 바깥 루프 진입 후 안쪽 루프 진입 시, 포인터가 가리키는 값이 1로 항상 변하지 않아 5000만번 수행 이후에도 안쪽 루프를 탈출하지 못하기 때문에 안쪽 루프가 무한 루프라고 판단되어야 합니다.

반면 두번째 케이스는, 바깥 루프 진입 후 안쪽 루프 진입 시, 포인터가 가리키는 초기값은 255이지만, 안쪽 루프를 실행하며 포인터 값이 1씩 감소하기 때문에 255번의 루프 실행 후에는 안쪽 루프를 빠져나올 수 있습니다. 하지만 이후 바깥쪽 루프 내의 명령을 수행하며 다시 포인터 초기값이 255인 상태로 안쪽 루프에 진입하는 상황이 반복되고, 결국 5000만번의 명령 이후에도 프로그램은 종료되지 않습니다. 이는 안쪽 루프는 탈출했었으나 바깥쪽 루프를 탈출하지 못했기 때문이므로, 바깥쪽 루프가 무한 루프라고 판단되어야 합니다.

.

- 문제 내에 무한 루프에 대한 정의가 없어, 위와 같은 중첩 루프 케이스에 대해 판단 기준이 모호하기 때문에, 문제 내에 "어떤 루프에 대해, 해당 루프를 한번이라도 탈출한 적이 있다면, 이는 무한 루프가 아니다." 와 같은 내용의 지문을 추가해 주세요.

dygks232   6년 전

unsigned char a, b, c, d;
a = b = c = d = 255;
whlie(a)
{
    a--;
    while(b)
    {
        b--;
        while(c)
        {
            c--;
            while(d)
                d--;
            d = 255;
        }
        c = 255;
    }
    b = 255;
}

추가로, 위의 C 코드 내 루프는 255^4번 반복하면 빠져나올 수 있는 무한하지 않은 루프이지만, 본 문제의 "프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다." 라는 조건의 특수성 때문에, 본 문제에서 무한 루프에 대한 별개의 정의는 꼭 필요하다고 생각합니다.

dygks232   6년 전

@jh05013 말씀해주신 내용들 모두 이해했습니다. 무한 루프 판별 기준을 저 나름대로의 기준으로 정립해버리고 작성한 글이었네요...

반례로 주신 케이스에서 제 코드(채점코드 19262778)는 "Loops 3 6"이 아닌 "Loops 2 8"을 출력하고 AC를 받았는데 이 또한 추가되어야 할 케이스겠네요.

그런데 본 문제 게시판을 훑어보니 부족한 채점 케이스가 꽤 있는 것 같아, 어떻게 요청해야할지 감도 안오네요 ㅎㅎ...

우선 본 요청글은 잘못된 글이므로 해결됨으로 바꾸겠습니다!

satelites   6년 전

dygks232

1

1 9 1
++[[++]+]
a

이 예시는

"Loops 3 6"이 아닌 "Loops 2 8"을 출력하는 게 틀린게 아니라 정답아닌가요?

안쪽루프는 포인터 값이 255 - > 0으로 변할때 탈출합니다. 하지만 바깥쪽 루프는 0으로 탈출한 뒤 무조건 1을 더하기 때문에 절대로 탈출 할 수 없죠.

문제가 뭔말인줄은 알겠는데 좀 모호하긴 한거 같아요.

댓글을 작성하려면 로그인해야 합니다.