code the world

문제Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져있는 $n\times n$ 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀있음을 의미합니다. 아래는 $n$이 3인 경우의 예시입니다.0 0 00 0 00 0 1차량은 $n\times n$격자 내에서 $m$개의 지점을 순서대로 방문하려고 합니다. 이때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한번 지났던 지점은 다시는 방문해서는 안됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지수를 구하는 프로그램을 작성해보세요.위의 예에서 $m=3$, 방문해야 하는 지점이 순서대로 (3행, 1열)..

문제자동차로 출퇴근을 하는 현서는 지루하지 않게 종종 길을 바꿔 다니곤 한다. 새로운 동네를 발견하는 일은 현서의 소소한 행복이다.현서의 출근길과 퇴근길은 가끔 겹친다. 즉, 출근길에 들른 동네를 퇴근길에 다시 지나곤 하는 것이다. 이에 대해 곰곰이 생각하던 현서는 이렇게 두 번 들를 수 있는 동네가 그렇게 많지 않음을 깨달았다. 도로의 연결 모양, 그리고 일방통행 여부 등으로 인해 출퇴근길 모두 방문 가능한 동네가 한정되는 것이다.현서의 출퇴근길은 단방향 그래프로 나타낼 수 있다. 즉 각 동네를 $1$부터 $n$까지의 번호가 매겨진 $n$개의 정점으로, $m$개의 일방통행의 도로를 단방향 간선으로 삼아 그래프를 만들 수 있다. 이때 현서의 집과 회사가 각각 정점 $S$와 $T$로 나타난다고 하면 출퇴근..

문제자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.이러한 평가 지표 중 하나는 자동차의 연비입니다.자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다. 만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.첫 번째 자동차의 연비는 9km/L, 두 번째 자동차의 연비는 15km/L, 세 번째 자동차의 연비는 20km/L이라고 합시다.이 경우, 중앙값은 15km/L이 됩니다.따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며, 이는 자동차 제조 과정에서 테스트의 결과를 평가하는데에 활용될 수 있습니다. $n$대의 자동차를 새로 만들..

문제생명 공학을 연구하는 현생이는 요즘 DNA 염기서열을 연구하고 있다.DNA 염기서열이란 4종류의 핵염기 a(아데닌), c(사이토신), g(구아닌), t(티민)이 일자로 연결된 가닥이다.문자열로는 a, c, g, t 네 문자의 나열로 나타낸다. 현생이는 인간에게 좋게 작용하는 좋은 염기서열 $N$개를 가지고 있고 이 모든 좋은 염기서열의 길이는 $M$이다.주어진 좋은 염기서열은 몇 개의 와일드 카드(.)을 가지고 있어, 이 부분에는 a, c, g, t의 어떤 염기가 들어가도 좋은 염기서열로 작용한다고 하자. 주어진 좋은 염기서열의 조건을 만족할 수 있는 염기서열을 초염기서열이라고 한다.그러나 주어진 모든 좋은 염기서열을 만족하는 것은 불가능할 수 있어서, 여러 초염기서열을 만들어서 여러 그룹의 좋은 염..

문제현주는 $N$명의 사원이 참가하는 프로그래밍 스터디 그룹을 이끌고 있다.현주는 스터디를 위해 대회를 세 개 출제하였고, 모든 구성원이 각 대회에 참여하였다. 각 참가자는 각 대회에서 $0$이상 $1000$ 이하의 정수인 점수를 얻는다. 한 대회에서 둘 이상의 참가자가 동점이 나오는 경우도 있을 수 있다. 현주는 각 대회별 등수 및 최종 등수를 매기고 싶다. 등수는 가장 점수가 높은 사람부터 $1$등, $2$등, ..., $N$등의 순서대로 붙는다. 만일 동점이 있을 경우 가능한 한 높은(등수의 수가 작은) 등수를 부여한다. 즉, 점수가 내림차순으로 $10,7,6,6,4$의 순서일 경우, $6$점을 받은 두 사람은 공동 $3$등이 되고, 그 다음 순서인 $4$점을 받은 사람은 $5$등이 된다. 이 규..

문제어떤 부서의 업무 조직은 완전이진트리 모양이다.즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다. 모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 $H$이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.업무는 $R$일 동안 진행된다. 처음에 말단 직원들만 각각 $K$개의 순서가 정해진 업무를 가지고 있다.각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다.다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다.단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째..

문제현대자동차그룹 연구소에서는 임직원들의 편의를 위해 출퇴근 통근 버스를 제공하고 있다. 퇴근 시간이 되면 연구소 주차장에는 수 많은 버스들이 일렬로 주차되어 있다.퇴근 버스는 번호순서 대로 출발해야 하는데, 주차장은 폭이 좁아 앞의 버스가 모두 나가야 뒤의 버스가 나갈 수 있는 구조로 되어 있다. 버스를 순서에 맞게 출발시키기 위해, 연구소 주차장의 맞은편에 임시 주차장을 추가로 건설하였다.이렇게 만든 임시 주차장은 출입구가 하나밖에 없는 데다가, 폭이 좁아서 Stack처럼 맨 처음 들어간 버스는 맨 마지막에 나올 수 있다.또한, 한 번 임시 주차장으로 이동했던 버스는 다시 원래의 주차장으로 이동할 수 없다. 위와 같은 상황에서 퇴근 버스를 번호 순서대로 출발시키는 문제는 스택 정렬로 모델링할 수 있다..

문제대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다.병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다.클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다. 현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다.클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다.그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다.이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다. 이 클러스터에는 $N$대의 컴퓨터가 있으며, 각각의..

문제대학교 학부생활을 마치고 현대자동차에 프로그래머로 취직한 사회초년생 현빈이는 팀장님에게 보안에 관련한 지식이 하나도 없음을 들키고 말았다. 그래서 현빈이는 업무시간 틈틈이 보안과 관련된 주제들을 공부하고 있다. 오늘 공부할 주제는 암호화 방식중 하나인 Playfair cipher(플레이페어 암호)다. Playfair cipher는 알파벳으로 이루어진 어떤 문자열(평문; plaintext)을 암호화하는 방법으로, 이를 위해 알파벳으로 이루어진 문자열인 키(key)가 필요하다. Playfair cipher는 빈도분석을 어렵게 하기 위해 한번에 두 글자 단위로 암호화를 진행하며, $5\times 5$크기의 표를 사용하기 때문에 알파벳 26개를 모두 담기에는 칸이 한 개 부족해 I와 J를 동일한 것으로 생각..

문제자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 우회전이 불가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로를 통과할 수 있다.자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다.이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자. 1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량..