aahcbird   1년 전

채점 번호 15767876번

소스 코드를 입력값으로 줬을 시에 Loops 3 6 이 출력되는 것이 정답이지만

Loops 1 8이 출력되는 코드를 작성했음에도 정답처리됩니다.

startlink   1년 전

위 예시는 데이터에 들어있지 않기 때문에, Loops 3 6을 출력한다고 오답 처리 되지는 않습니다.

위의 데이터에서 "Loops 3 6"를 출력하는 소스가 다른 데이터에서 틀렸기 때문에 오답 처리 된 것입니다.

채점에는 문제가 없습니다.

startlink   1년 전

재채점했습니다.

marin0625   1년 전

문제 풀어보니 루프 안에 무한 루프 있으면 더 큰 루프(무한 루프를 감싸는)로 출력해야 하던데 1~8 루프도 무한 루프니까  Loop 1 8 로 나오는게 맞지 않나요?

ho94949   1년 전

무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.


라는 조건을 만족하지 않는 것으로 보이네요.

startlink   1년 전

재채점했습니다.

ho94949   1년 전

헉 제 덧글도 잘못된듯 ㅠㅠ 

ho94949   1년 전

제 덧글 맞는듯 

marin0625   1년 전

[0][0][0] pointer(0) 초기상태

[1][0][0] pointer(0) +

[1][0][0] pointer(0) 첫 [ -> 가리키는 값 1이므로 실행 x 

[0][0][0] pointer(0) - 

[0][0][0] pointer(0) 내부 [ -> 가리키는 값 0이므로 실행 -> 내부 ]로 점프

[0][0][0] pointer(0) 내부 ]  -> 가리키는 값 0이므로 실행 x

[-1][0][0] pointer(0)  -

[-1][0][0] pointer(0) 외부 ] -> 가리키는 값 -1 이므로 실행 ->외부 [로 점프

--------------

이렇게 보면 외부 루프는 이미 한번 실행된 것 아닌가요? 

aahcbird   1년 전

원글 작성자입니다.


1. 문제 풀어보니 루프 안에 무한 루프 있으면 더 큰 루프(무한 루프를 감싸는)로 출력해야 하던데 1~8 루프도 무한 루프니까 Loop 1 8 로 나오는게 맞지 않나요?

-> 루프 안에 무한 루프가 있다고해서 바깥에 있는 루프를 무한 루프로 가정하여 출력해야 된다는 조건은 문제 어디에도 없었습니다.

https://gcpc.nwerc.eu/german-collegiate-programming-contest-2012

해당 콘테스트의 답안인 judge solutions는 위 링크에 총 5개가 제공되고 있는데,

5개 코드 각각에 해당 데이터를 넣어 돌려본 결과 모두 Loops 3 6이 출력되었습니다.


2. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다 라는 조건을 만족하지 않는 것으로 보이네요.

-> 이 또한 제가 올린 데이터에 해당되는 내용이 전혀 아닙니다.


원문은 다음과 같습니다.

You may safely assume that after 50 000 000 instructions, a program either terminated or hangs in an endless loop, which then was executed at least once. During each iteration of the endless loop at most 50 000 000 instructions are executed.


이 조건은 어떤 루프가 무한 루프임에도 불구하고, 그 루프를 이루고 있는 하나 하나의 iteration에서 루프 맨 마지막에 다다르지 않고 프로그램이 종료하는 상황을 고려하지 않도록 하기 위한 조건일 뿐입니다.

예를 들어 루프 A가 무한 루프이고, 루프 A 안에 무한 루프가 아닌 루프 B가 있다고 했을 때 루프 B를 도는 동안 명령어를 50,000,000개 소모했다고 한다면 프로그램이 종료되기 전까지 루프 A의 마지막에 도달하지 못했기 때문에 루프 A가 무한 루프로 출력되지 않는 상황이 발생할 수 있습니다. (그렇다고 해서 루프 B가 반드시 무한 루프로 출력되는 것도 아닙니다. 루프 B도 해당 루프의 맨 마지막에 다다르지 못했을 수 있기 때문입니다.)

만약 이것도 아니고 '무한 루프가 명령어를 50,000,000개 소모하는 것'으로 이해하셨다면 다음과 같은 예로 반박할 수 있습니다.

1
1000 5 1
+[+-]
a

위 데이터는 심지어 문제에서 input값으로 주고 있는 데이터지만 루프 내부가 무한히 반복됨에도 불구하고 한 번의 무한 루프에서 실행되는 명령어의 개수를 50,000,000개 이하로 가정하고 있습니다.

따라서 이 또한 올바른 반론이 아닙니다.


제가 올린 소스 코드가 문제의 조건에 어긋나는지 원문을 살펴보며 찾아보았지만 아직까지 문제에 어긋나는 어떠한 점도 발견하지 못했습니다.

따라서 데이터는 문제가 없고, 출제자들이 직접 작성한 solution들을 고려했을 때 해당 데이터에 해당되는 출력 값도 Loops 3 6이 맞습니다.

startlink   1년 전

이 문제는 원본 문제의 조건이 충분하지 않다고 판단되어서 문제에 여러가지 조건을 추가할 예정입니다.

kipa00   1년 전

애초에 무한 루프가 뭔가요?

원글 작성자분께서 쓰신 위 긴 논증은 무한 루프가 무엇인지를 전혀 설명하지 않고, 출제자들의 solution에 의지한 주장을 하고 계십니다.

  • semantically 앞에서 순서대로 실행했을 때 루프에 들어가기 전 주어진 메모리들에서 탈출할 가능성이 없는 루프를 무한 루프라고 한다면, 안쪽 루프가 무한 루프일 때 바깥쪽 루프 역시 탈출할 가능성이 전혀 없기에 바깥쪽 루프도 무한 루프라고 볼 수 있습니다. (Note: 이 논증은 위 예시뿐만이 아니라 어떤 중첩된 두 루프라도 가능합니다.)
  • 반대로 syntactically 무한 루프를 판단하게 되면 brainf**k에서는 당연히 어떤 루프도 무한 루프가 아니게 됩니다.

만일 바깥쪽 루프가 무한 루프라고 한다면, 바깥쪽 루프의 한 iteration에서 끝없는 instruction을 시행하게 되기 때문에 (바깥쪽 루프의 두 번째 iteration에서 실행되는 instruction은 -><><><><...입니다) 위 데이터는 조건을 위배합니다. 이 논증 역시 어떤 중첩된 두 루프라도 가능합니다. 따라서 제가 제시한 첫 번째 정의를 믿는다면, effectively 제한을 "endless loop의 바깥에는 루프가 없다"로 바꿀 수 있게 됩니다.

원글 작성자분께서는 위 데이터가 조건을 만족하는 데이터라고 말씀하고 계시므로 바깥쪽 루프는 무한 루프가 아니라고 생각하시는 것입니다. 이는 결국 "탈출할 수 없는 루프가 무한 루프가 아닐 수도 있다"를 함의하는데, 저에게는 굉장히 이상한 말로 들립니다. (@ho94949 님도 여기에 동의하시는 것 같습니다.) syntactically 무한 루프더라도 이 조건에 따른 무한 루프가 아닐 수 있는데, C++로 아래의 코드의 바깥 루프는 (syntactically/semantically) 조건이 항상 참이므로 "무한 루프"라고 판단할 수 있겠지만 작성자님의 주장에 따르면 아니어야 합니다. (아래 코드는 문제 조건을 만족하는 코드는 아닙니다. 참고용으로만 봐 주세요.)

ho94949   1년 전

무한루프를 다음과 같이 정의한다는 내용을 만들고 출제자의 코드가 이에 부합하는지 보면 되겠네요, 또한 데이터의 검사가 필요 해 보입니다.


무한 루프 정의:

어떤 루프가 무한 루프를 포함한다는 것은, 프로그램 실행 후 충분히 긴 시간이 지난 이후에 프로그램이 반복적으로 해당 루프 안에 있는 명령어만 수행한다는 것을 의미한다. 무한 루프를 포함하는 루프 중에서 가장 안쪽에 있는 루프를 무한 루프라고 한다.

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