내용

글번호 805
작성자 heojk
작성일 2018-01-19 16:18:46
제목 코딩 테스트 1-4
내용 조약돌 주행거리계 다빈치는 최초의 주행거리계를 발명하였다. 이 기계는 수레를 이용하여 만든 것으로서 수 레의 바퀴가 한바퀴 돌 때 마다 조약돌을 떨어트려서 거리를 잴 수 있게 한 것이다. 떨어트 린 조약돌의 수를 세면 바퀴의 회전수를 알아낼 수 있고, 이에 따라 수레가 이동한 거리를 알아낼 수 있다. 컴퓨터 과학자인 우리는 주행거리계에 소프트웨어를 이용한 제어기를 도 입하여 기능을 확장하였다. 이 문제의 목표는 주행거리계를 위해 만들어진 아래에 설명한 규칙과 같은 새로운 언어로 프로그램을 작성하여 제출하는 것이다. 사용하는 격자 (맵) 주행거리계는 가로와 세로가 각각 256개의 셀로 구성된 가상의 격자 위에서 움직인다. 각 셀은 2차원의 좌표로 표시되며, 각 좌표의 값은 0 이상 255 이하이다. 가장 북서쪽(왼쪽 위) 의 셀이 (0, 0) 셀이다. (첫번째 좌표 값은 남북 방향에 대한 것이며, 두번째 좌표 값은 동서 방향에 대한 것이다. 즉 (0, 0) 셀의 오른쪽에 인접한 셀은 (0, 1) 셀이다.) 각 셀에는 최대 15 개의 조약돌이 존재할 수 있다. 어떤 (i, j) 셀에 대해서 인접한 셀들은 (i - 1, j), (i + 1, j), (i, j - 1)과 (i, j + 1)이다. 물론 좌표 값이 지정된 범위 밖인 경우는 셀이 존재하지 않는다. 두 좌표 중 어느 하나라도 0이거나 255인 셀들은 경계 셀이라고 부른다. 주행거리계의 초기 상태는 (0, 0) 셀에서 북쪽을 향하고 있다. 기본 명령어들 주행거리계는 다음의 명령들을 이용하여 프로그램할 수 있다. left — 제자리에서 왼쪽으로 (시계 반대 방향으로) 90도 회전한다. (예를 들어, 주행 거리계가 남쪽을 향하고 있었다면 이 명령 이후에는 동쪽을 향하게 된다.) right — 제자리에서 오른쪽으로 (시계 방향으로) 90도 회전한다. (예를 들어, 주행 거리계가 서쪽을 향하고 있었다면 이 명령 이후에는 북쪽을 향하게 된다.) move — 현재 주행거리계가 향하고 있는 방향의 인접한 셀로 이동(전진)한다. 만약 그 방향에 셀이 존재하지 않는 경우이면 (현재 위치가 경계 셀이면 발생할 수 있는 경 우임) 이 명령은 아무 효과도 없다. get — 현재 셀에서 하나의 조약돌을 제거한다. 만약 현재 셀에 조약돌이 없다면 이 명령은 아무 효과도 없다. put — 현재 셀에 하나의 조약돌을 추가한다. 만약 현재 셀에 이미 15개의 조약돌이 있는 경우라면 이 명령은 아무 효과가 없다. 주행거리계는 무한한 개수의 조약돌을 가지고 있어서 조약돌이 모자라는 경우는 없다. halt — 프로그램의 수행이 종료된다. odometer - ko 1/6 주행거리계의 프로그램은 한 줄에 최대 하나씩의 명령어를 가지도록 주어져야 한다. 주행 거리계는 명령들을 주어진 순서대로 하나씩 수행한다. 빈 줄은 완전히 무시된다. 기호 #는 주석를 위한 것인데 어떤 줄에 이 기호가 나타나면 그 다음 글자 부터 그 줄의 끝까지는 모 두 주석으로 간주되어 무시된다. 프로그램의 수행이 마지막 줄을 넘어서게 되면 프로그램 은 자동으로 종료된다. 예제 1 주행거리계를 위한 다음 프로그램을 보자. 다음 프로그램은 주행거리계를 (0, 2) 셀로 보내 고 마지막에 동쪽으로 항하도록 만든다. (제일 첫 move 명령은 무시됨에 주의하자. 그 이 유는 초기에 주행거리계는 제일 북서쪽 셀에 위치해서 북쪽으로 향하고 있기 때문이다.) move # no effect right # now the odometer is facing east move move Label, border, pebble 명령문 현재 상태에 따라 프로그램의 동작이 달라지도록 하기 위하여 레이블을 정의할 수 있다. 레이블은 a, …, z, A, …, Z, 0, …, 9 의 문자들로 만들어진 문자열이며, 대소문자를 구분하 고 최대 128의 길이를 가질 수 있다. 레이블을 사용하는 명령들이 아래에 제시되어 있다. 아래 설명에서 L은 임의의 유효한 레이블을 의미한다. L: (즉, L 다음에 콜론 기호‘ :’가 있음) — 프로그램의 해당 위치를 L 레이블로 선언 한다. 프로그램 내의 레이블들은 모두 달라야 한다. 레이블 선언 자체는 프로그램 내 의 위치만을 의미하고 주행거리계가 특별히 수행하는 동작은 없다. jump L — 레이블 L의 위치로 무조건 점프를 수행하여 그 레이블 다음의 명령을 수 행한다. border L — 현재 주행거리계가 경계 셀에 위치하고 전방에 셀이 존재하지 않는 경우(즉, move 명령이 아무 동작을 하지 않게 되는 경우)라면 L에 해당하는 레이블 의 위치로 점프한다. 그와 다른 경우, 이 명령은 아무 동작을 수행하지 않고, 이어진 다음 명령이 수행된다. pebble L — 현재 셀에 조약돌이 하나 이상 존재하는 경우에는 레이블 L에 해당하 는 위치로 점프한다. 그와 다른 경우에는 이 명령은 아무런 동작을 수행하지 않고, 이 어진 다음 명령이 수행된다. 예제 2 다음 프로그램은 제일 위쪽(북쪽) 행(row)에서 조약돌이 있는 제일 왼쪽(서쪽) 셀을 찾아서, 그 셀에서 주행거리계가 멈추도록 하는 프로그램이다. 만약 제일 위쪽 행에 조약돌이 존재 하는 셀이 없는 경우 주행거리계는 제일 오른쪽 셀에서 멈춘다. 프로그램에는 leonardo와 davinci의 두 개의 레이블이 사용된다. odometer - ko 2/6 right leonardo: pebble davinci # pebble found border davinci # end of the row move jump leonardo davinci: halt 주행거리계는 우선 오른쪽으로 회전한다. 프로그램의 루프는 leonardo:로 시작하여 jump leonardo로 끝나는 부분이다. 루프에서 수행하는 작업은 현재 셀에 조약돌이 존 재하는 지의 여부를 검사하는 것과 열의 오른쪽 끝에 도달했는지를 검사하는 것이다. 두 경우 모두 아니라면, 주행거리계는 move를 수행하여 현재 셀 (0, j) 에서 인접한 셀 (0, j + 1) 로 이동한다. 인접한 셀이 존재함은 반드시 보장된다. (마지막의 halt 명령이 없어도 프로 그램은 정상적으로 종료되므로 마지막 명령은 반드시 필요한 것은 아니다.) 해야할 일 주행거리계를 기대한대로 움직이게 하도록 위에서 설명한 주행거리계 언어로 프로그램을 작성한다. 각 서브태스크(아래에 설명한다)에서 주행거리계가 수행할 행동과 제출할 프로 그램이 만족해야하는 제약조건들을 설명한다. 제약조건들은 다음 두 가지 요소들과 관련 이 있다. 프로그램 크기 - 프로그램은 충분히 짧아야 한다. 프로그램의 크기는 포함된 명령어 들의 수이다. 레이블 선언들, 주석들, 빈 라인들은 세지 않는다. 실행 길이 - 프로그램은 충분히 빠르게 끝나야 한다. 실행 길이는 수행된 스탭들의 수 이다: 모든 단일 명령어 실행은 그것이 효과가 있던 없던 간에 한 스탭으로 센다; 레 이블 선언, 주석, 빈 라인은 한 스탭으로 세지 않는다. 예제 1에서 프로그램 크기는 4이고 실행 길이도 4이다. 예제 2에서 프로그램 크기는 6이고, (0, 10) 셀에 하나의 조약돌이 있는 격자의 경우에 실행 길이는 43이다. 즉, right, 각각 4 스탭인 (pebble davinci, border davinci, move, jump leonardo) 루프의 10번 반복 , 그리고 마지막으로, pebble davinci 와 halt가 있다. 서브태스크 1 [9점] 초기에 (0, 0) 셀에 x 개 조약돌들과 (0, 1) 셀에 y 개 조약돌들이 있고, 모든 다른 셀들은 비 어있다. 만약 x ≤ y라면, 주행거리계는 (0, 0) 셀에서 종료하고, 그렇지 않으면, (0, 1) 셀에서 종료하게 되는 프로그램을 작성하시오. (주행거리계가 마지막에 어디를 향하고 있든지 상 관없다. 또한, 마지막에 격자에 얼마나 많은 조약돌들이 존재하던지 또는 조약돌들이 어디 에 있던지 상관없다.) 제한들: 프로그램 크기 ≤ 100, 실행 길이 ≤ 1,000. 서브태스크 2 [12 점] 서브태스크 1과 같지만 프로그램이 끝났을 때, (0, 0) 셀에 정확히 x 개 조약돌이, (0, 1) 셀에 정확히 y 개 조약돌이 존재해야 한다. odometer - ko 3/6 제한들: 프로그램 크기 ≤ 200, 실행 길이 ≤ 2,000. 서브태스크 3 [19점] 제일 북쪽 행 어딘가에 정확히 두 개의 조약돌들이 존재한다: 하나는 (0, x) 셀에 있고, 다른 하나는 (0, y) 셀에 있다. x 와 y 는 다르고, x + y 는 짝수이다. 주행거리계가 (0, (x + y) / 2) 셀 에서, 다시 말해서, 조약돌을 포함하는 두 셀들의 정확히 중간지점에서, 종료하도록 하는 프로그램을 작성하시오. 종료 시 격자의 조약돌들의 개수와 위치는 상관이 없다. 제한들: 프로그램 크기 ≤ 100, 실행 길이 ≤ 200,000. 서브태스크 4 [최대 32점] 격자에는 최대 15개의 조약돌이 존재하며, 하나의 셀에는 최대 1개의 조약돌이 존재한다. 조약돌 모두를 제일 북서쪽 셀에 모으는 프로그램을 작성하시오. 정확히, 초기에 격자에 x 개의 조약돌들이 존재하면, 마지막에 (0, 0) 셀에 정확히 x 개의 조약돌들이 존재해야 하며, 그 밖의 셀에는 조약돌이 없어야 한다. 이 서브 태스크의 점수는 제출된 프로그램의 실행 길이에 따라 다르다. 정확히, L 이 여러 테스트 케이스들에 대한 실행 길이의 최대값이면, 점수는 다음과 같을 것이다: L ≤ 200,000 이면 32점; 200,000 < L < 2,000,000 이면 32 - 32 log₁₀ (L / 200,000) 점; L ≥ 2,000,000 이면 0점. 제한들: 프로그램 크기 ≤ 200. 서브태스크 5 [최대 28점] 격자의 각 셀에는 임의의 수의 조약돌들이 존재할 수 있다 (물론, 0과 15 사이의 수이다). 그 러면 최소 조약돌 수를 가진 셀을 찾는, 다시 말해서, 다른 모든 셀 보다 작거나 같은 수의 조약돌들이 존재하는 (i, j) 셀에서 주행 거리계가 종료하도록 하는 프로그램을 작성하시오. 프로그램을 실행한 후, 각 셀의 조약돌 수는 프로그램을 수행하기 전과 같아야 한다. 이 서브 태스크의 점수는 제출된 프로그램의 크기 P 에 따라 다르다. 정확히 점수는 다음과 같다: P ≤ 444 이면 28점; 444 < P < 4,440 이면 28 - 28 log₁₀ (P / 444) 점; P ≥ 4,440 이면 0점. 제한들: 실행 길이 ≤ 44,400,000. odometer - ko 4/6 구현 세부 사항 위에서 기술된 규칙들에 따라서 작성된 프로그램을 서브 태스크마다 정확히 하나의 파일 로 제출해야한다. 각 제출된 파일은 최대 5MB를 넘지 않아야 한다. 각 서브 태스크에 대해 서, 코드는 몇 가지 테스트 케이스들로 테스트 될 것이고, 코드에서 사용된 자원들에 대한 피드백을 받게 될 것이다. 코드가 구문적으로 옳지 않고 테스트가 불가능한 경우에 특별한 구문 에러에 대한 정보를 받게 될 것이다. 제출할 때, 반드시 모든 서브 태스크들에 대한 프로그램들을 포함할 필요는 없다. 현재 제 출이 서브 태스크 X 에 대한 프로그램을 포함하지 않는다면, 서브 태스크 X 에 대한 가장 최근 제출이 자동적으로 포함될 것이다; 만약 그런 프로그램이 없다면, 이 제출에서 그 서 브 태스크는 점수 0 을 받을 것이다. 제출 결과 점수는 항상 각 서브 태스크에 포함된 점수들의 합이고 마지막 점수는 테스트된 제출들과 마지막 제출 중 최대값이다. 시뮬레이터 프로그램을 시험해 볼수 있도록 주행거리계 시뮬레이터가 여러분의 컴퓨터에 주어진다. 여러분은 시뮬레이터에 프로그램과 격자를 입력으로 주고 그 수행 결과를 볼수 있다. 주행 거리계를 위한 프로그램의 문법은 제출을 위한 것과 동일하다. (즉, 위에서 설명한 것과 같 다.) 격자의 초기 상태 표현 방법은 아래와 같다. 각 줄에는 빈칸으로 구분된 세 개의 자연수 R, C, P가 있어야 하는데, R은 행 번호, C는 열 번호이며, P는 (R, C) 셀에 P개의 조약돌이 있음 을 의미한다. 조약돌이 존재하지 않는 셀들은 설명에 포함할 필요가 없다. 예를 들어, 다음 파일을 보자. 0 10 3 4 5 12 이 파일에서 설명하는 격자에는 15개의 조약돌이 존재하는데, (0, 10) 셀에 3개와 (4, 5) 셀 에 12개가 존재한다. 시뮬레이터는 작업 디렉토리의 simulator.py에 프로그램 파일 이름을 인자로 주어 사 용할 수 있다. 시뮬레이터가 받을 수 있는 옵션은 다음과 같다. -h 옵션은 가능한 옵션들에 대한 설명을 제공한다. -g GRID_FILE 옵션은 GRID_FILE 에서 격자를 로드한다. (디폴트는 조약돌이 하 나도 없는 격자이다.) -s GRID_SIDE 옵션은 격자의 크기를 GRID_SIDE x GRID_SIDE로 잡는다. (디 폴트 값은 256이다.) 작은 크기의 격자를 사용하면 디버깅에 도움이 될 수도 있다. -m STEPS 옵션은 프로그램의 수행 길이를 최대 STEPS로 제한한다. odometer - ko 5/6 -c 옵션으로 컴파일 모드를 사용할 수 있다. 컴파일 모드에서 수행 결과 자체는 똑같 지만 시뮬레이터는 Python을 이용하는 대신 C 프로그램을 자동적으로 생성하여 컴 파일하고 그 결과로 생성되는 실행파일을 실행시킨다. 그 결과, 시뮬레이션의 시작 은 조금 늦어질 수 있지만, 전체 시뮬레이션 시간은 (특히 수행 길이가 긴 경우에) 많 이 줄어들 수 있다. 수행 길이가 10,000,000 단계 이상인 경우에는 이 옵션을 사용할 것을 권장한다. 제출 횟수 이 문제의 최대 제출 횟수는 128이다.