[문제] 어떤 도시에서 코로나-19사태에 대응하여 지점 S에서 지점 T로의 이동을 완전히 봉쇄하려고 한다. 아래 그림에서 색으로 칠해진 부분은 사람이 이동할 수 없는 공간(산이나 호수, 강)이다. 여러분의 목표는 단 하나의 그리드 위치(Cell)에 장애물을 세워 S에서 T로 갈 수 있는 경로(path)를 막는 것이다. 왼쪽 예시의 경우 {a, b, c, d, e, f}로 표시된 곳 중 하나를 막으면 S에서 T로의 이동을 완전히 봉쇄할 수 있다. 오른쪽 예시의 경우 하나의 Cell만을 막아서는 S에서 T로 가는 것을 막을 수 없다. 여러분은 S-T 경로를 봉쇄할 수 있는 Cell을 모두 찾아 그 index를 사전식으로 나열해야 한다(S나 T를 직접 막을 수는 없다). 만약 봉쇄할 수 없을 때는 0을 출력한..
[문제] 생물체의 특정 염색체를 Next Generation Sequencing(NGS) 기기를 이용하면 해당 염색체 전체를 작은 조각으로 잘라서 읽을 수 있다. 이 서열화(Sequencing) 단계는 분자생물학, 생물정보학 연구에서 가장 중요한 작업이다. 이때 NGS 기기를 통해서 읽은 전체 DNA 서열의 조각을 read라고 부른다. DNA로 이루어진 염색체의 길이는 보통 수백 메가바이트의 크기이므로 한 번의 NGS 실험으로 생산되는 리드(read)는 수억에서 수십억 개에 이를 정도로 매우 많다. 실제 {모기, 고릴라, 개, 사람}의 몇 염색체에서 추출된 read sequence가 주어진다. read 서열은 { a, g, t, c } 4개의 염기를 나타내는 소문자들로 구성되어 있다. 입력으로 받은 re..
[문제] $k$ 개의 음식 재료 중에서 몇 개를 선택하여 그 안에 포함된 4가지 영양분 [단백질, 탄수화물, 지방, 비타민] 각각의 합이 일정 수치 이상이 되도록 하고자 한다. 아래 예를 통하여 설명해보자. 우리에게 필요한 4개 성분의 최소 기준이 (100, 70, 90, 10) 이라고 가정해보자. 우리는 아래 준비된 6가지 재료 중에서 몇 개를 선택하여 각 4개의 영양분 (단백질, 지방, 탄수화물, 비타민)의 합이 최소 (100, 70, 90, 10)이 되도록 해야한다. 이 경우 모든 재료를 선택하면 해결되지만, 비용이 너무 커진다. 우리는 최소 영양분 조건을 만족하면서도 선택한 재료의 비용을 최소화해야 한다. 예를 들어 재료 {1, 3, 5}를 선택하면 영양분은 (100, 145, 130, 10)으로..
[문제] 어떤 도시 NASUP에서 국제적인 철인 마라톤(iron marathon) 대회가 열린다. 이 대회는 기존 42.195km를 달리는 일반적인 마라톤과 다르게 개최지 도시가 제공할 수 있는 최대한의 거리를 달린 후 다시 출발점으로 돌아온다. 따라서 도시에 따라서 이 달려야 하는 거리는 매해 달라진다. 우리는 NASUP시의 지도를 받아서 가장 긴 마라톤 코스를 설계해야 한다. 도로망은 edge에 가중치가 있는 단순 그래프(simple graph) 형식으로 제공된다. 두 교차로(vertex)를 지나는 도로(edge) 길이는 모두 정수(km)이다. 여러분은 경기장 ‘a’ 에서 출발하여 다시 그 장소로 되돌아오는 가장 순환로 중에서 가장 긴 사이클을 찾아야 한다. 도시의 모든 정점은 알파벳 소문자 1자로 ..
[문제] 어떤 물체의 2차원 단면정보가 이 물체에 수직, 수평, $\pm$45도씩 4방향의 Z-ray를 주사하여 측정된 값의 1차원 배열에 저장되어 있다. 우리는 이 배열 정보를 이용해서 이 물체의 원래 단면 모습을 2차원 배열로 재구성하여 비파괴 검사에 활용하고자 한다. Z-ray는 물체로 채워진 단위 그리드를 한번 통과할 때마다 1씩 그 세기가 감소한다. 아래 예시를 따르면, 수직으로 세기=10인 Z-ray를 주사(projection)하면 물체 영역 B cell 하나에 대하여 그 강도가 1씩 감소하여 바닥에 감지된 Z-ray 값은 왼쪽부터 [9,7,8,8]이 된다. 즉, 원래 주사한 Z 광선의 세기를 빼면 물체 내부를 채운 셀의 개수를 얻을 수 있다. 단, 이 문제에서는 계산의 편의를 위해서 지나친 ..
[문제] 어떤 도시 NASUP에서 국제적인 마라톤 대회가 열린다. 우리는 이 대회를 위하여 42.195km의 마라톤 코스를 설계하는 과제를 맡았다. 도시의 도로망은 edge에 가중치가 있는 단순 그래프(simple graph) 형태이며, 두 교차로(vertex)를 지나는 도로(edge) 길이는 모두 정수(km)다. 우리는 이 도시에서 경기장에서 출발하여 다시 돌아오는 42km의 순환로를 만들어야 한다. 도시의 모든 정점은 알파벳 소문자 1자로 표시된다. 따라서 도시는 최대 26개의 정점까지 가질 수 있다. 우리가 완성해야 할 마라톤 코스는 다음의 성질을 만족해야 한다. 1) 출발점 vertex는 항상 스타디움이 위치한 a로 고정되어 있다. 2) 순환로는 선수가 헷갈리지 않도록 같은 장소를 2회 이상 방문..
[문제] 7개의 음(pitch)으로만 구성된 악곡이 있다. 예를 들어 중세 그레고리안 성가는 7개의 음, 우리나라와 중국 일본의 민속 음악은 5개의 음으로 구성된 펜타토닉 음계를 사용한다. 음악에서 반복과 변형은 노래를 끌고 나가는 매우 중요한 동력 알고리즘이다. 반복이 너무 없으면 청중은 무료함, 지루함을 느끼지만, 또 너무 같은 상투적인 구조가 변화 없이 반복되면 긴장감이나 새로움이 떨어져 유치해지거나 쉽게 흥미를 잃게 된다. 이 문제에서 입력 음악은 7개의 소문자 {$c,d,e,f,g,a,b$}로 구성된 문자열로 표현된다. 이 문제에서 음의 지속을 나타내는 박자는 일단 무시하기로 한다. 어떤 구절이 반복된다는 것은 어떤 부분 문자열(substring)이 다른 위치에서 비슷한 모양으로 다시 나타난다는..
[문제] $N$ 개의 바둑돌이 담긴 항아리가 있다. 이 항아리를 두고 $F$ 와 $S$ , 이 두 사람이 게임을 한다. 게임은 자신의 차례가 왔을 때 항아리에서 3가지 선택 $s_1$, $s_2$, $s_3$ 중 하나를 선택해서 $s_i(i=1,2,3)$개의 돌을 꺼낼 수 있다. 이 작업을 두 사람이 번갈아 가면서 할 때 자기 차례에서 더 이상 허용된 작업을 못하는 사람이 지고(lost) 상대방은 이기게(win) 된다. 단 이 게임에는 몇 가지 제한 사항이 있다. 1) 만일 앞 차례에서 개의 돌을 꺼냈다면 다음 차례 사람은 다시 같은 수의 돌 을 연이어 꺼낼 수 없다. (반복 금지, 따라하기 금지의 원칙) 2) 제일 처음 시작하는 사람은 $s_1$, $s_2$, $s_3$ 중에서 어떤 것이라도 선택할 수..
[문제] 고급 주택의 청소만을 전문으로 하는 1인 기업 프리랜서 HCC(House Cleaning Company)가 있다. 이 사람은 소비자들의 요청을 미리 받아서 종합하여 그중에서 가장 이익이 많도록 작업을 선택 조정한다. 작업 단위는 일(daily) 단위이며 365*3(년)까지의 일정을 그전에 모두 확정한다. 사용자들은 자신의 집을 청소하기 원하는 기간(일단위)와 그때 지불할 비용을 Mr.X의 블로그에 올린다. 청소를 신청한 고객을 라고 할 때 이를 나타내는 신청 정보는 $(b_i, e_i, c_i)$로서 각각은 시작일과 종료일, 그리고 견적 비용(cost, 만원)을 나타낸다. 이 값은 조건, $1 \leq b_i \leq e_i \leq 365 * 3$을 항상 만족한다. 최소한 기간은 하루(a da..
[문제] 부산 시민의 숙원사업인 돔 야구장을 부산 외곽 지역에 건립하고자 한다. 야구장 건립을 위해서 볼파크 공사 예정지는 아래 그림과 같이 $N \times M $ {0,1} 행렬(matrix)로 표시되며, 공사 예정지 내의 $k \times k$ 크기의 정방형 공간에 돔구장을 지으려고 한다. 그런데 이 지역의 어떤 지점에는 큰 암반이나 물구덩이가 있어서 해당 지점에서는 공사할 수가 없다. 아래 그림에서 $M_{i,j} = 1$ 은 위치 $(i , j)$에 지점에 엄청난 크기의 돌, 보호해야 할 정도의 큰 수목, 깊은 웅덩이 등의 장애물이 있음을 나타낸다. 그리고 $M_{i,j} = 0$ 은 해당 지점 $(i , j)$ 을 그대로 활용할 수 있음을 나타낸다. 우리는 이 예정 지역에 가장 큰 완전 $k ..
