원티드에서 쇼미더코드라고 대회를 개최한다길래 참여해봤다. 같은 시간에 프로그래머스에서 데브매칭도 진행한다길래 둘 중 어디를 참여할 지 고민해봤는데, 이름이 더 마음에 들어서 쇼미더코드만 지원했다. 시간이 겹친다길래 장난식으로 "컨텍스트 스위치하면서 풀면 되지"라고 얘기하고 하나만 지원했는데, 진짜로 두개 동시에 진행했어도 통과될 뻔 했다... A. 물약구매 정확히는 기억이 안 나지만 "물약을 살 때 마다 다른 물약들의 가격이 떨어지는데, 그 때 모든 물약을 사는 최소 비용"을 구하는 문제였던 것 같다. n이 15인가 10인가 아무튼 굉장히 작기 때문에 그냥 브루트포스로 돌아갔다. next_permutation으로 수열 돌려가면서 시뮬레이팅하면 된다. B. 숫자 이어 붙이기 대충 수를 이어 붙혀서 만들 수..
2018년 참가 이후 첫 참가다. 작년엔 복학이후 학교 수업 따라가기도 벅차서 icpc와 scpc만 출전했다. 딱히 준비한 것은 아니지만 그래도 정신차리고 풀면 티셔츠는 받지 않을까 하는 생각에 참전한다. 전날 영화보고 잠들어서 거의 12시에 일어나는 바람에 3시간 30분 정도 늦게 시작했지만 예상보다 속도감있게 풀어서 다행이다. 1. Punch Cards 지문 처음부터 읽다가 때려치우고 Input 바로 위 문단만 읽었다. 단순히 n, m 받고 조건에 맞게 출력해주면 되는 언럭키별찍기 2. 3D Printing 얘도 지문이 너무 길어서 읽는데 고생 좀 했는데, 프린터 3개의 잉크량을 입력받고, 모든 프린터에서 1,000,000만큼 출력 가능한지 출력하는 문제다. 말도 안 되게 단순한 문젠데, 전 문제와 ..
[문제] 어떤 도시에서 코로나-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자로 ..
그래프 알고리즘 spfa, floyd-warshall [링크] [풀이] 예전에 풀었던 문제이나, 동아리 리뷰 문제로 나온 문제중 레이팅이 가장 높고, 이전에 짰던 코드를 보니 굉장히 복잡해서 더 간단하게 풀어보기 위해 건드려보았다. 먼저, '최대'이윤을 구하는 문제이고 문제 정의상 음수 간선에서 양수 cycle을 판별해야하는 문제이기 때문에 spfa로 해결이 가능하다. 일반적으로 spfa에서 cycle을 판별하듯이 판별하여 cycle이 있으면 바로 'Gee'를 출력하면 해결이 될까? 0 2 0 0 1 9999 1 2 9999 2 1 9999 0 3 0 10000 10000 10000 10000 이런 입력이 들어온다고 치자. 1과 2에서 cycle이 발생하므로 일반적으로 cycle판별 후 있을 때 retu..
[문제] 어떤 물체의 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회 이상 방문..
A. K-divisible Sum $n$과 $k$가 주어지면 $n$개의 아무 수를 더 해서 $k$의 배수를 만들고 싶은데, 그 $n$개의 수중 가장 큰 수의 값을 가장 작게 만들고, 그 수를 구하는 문제다. $n$보다 $k$가 작으면 성립하지 않으므로 $n$보다 크면서 가장 작은 $k$의 배수를 구해준다. $n$개의 수를 모두 1로 맞추면 $n$이 나오고, $n+1$은 1,1,1,1.....2, $n+2$는 1,1,1,1.....2,2, $n + (n - 1)$은 1,2,2,2,2....2 이므로 $t*n + alpha$에 대해 $alpha == 0$이면 $t$이고 $alpha != 0$이면 $t + 1$이다. $t*n + alpha = k$를 계산해주면 된다. B. Inflation 매 달의 물건의 가..
