code the world

문제슬슬 다가오는 예비군 시즌을 의식하다보니 눈에 띄는 제목의 문제가 있어 클릭해보았다. N이 첫번째 줄에,P, Q가 두번째 줄에 공백으로 구분되어 주어진다. 기댓값의 최댓값풀이푸르매가 전부 쏘고 나서 하늘이로부터 도움을 받는 것으로 순서를 정해서 계산했다.문제에서는 확률을 대문자로 표시했지만 이 글에서는 소문자 $p,q$를 사용했다. 일단 푸르매가 2차시기에 $N$번 쏴서 $n$개를 맞출 확률을 $Q(n)$이라고 하자.이 때 값은 $_{N}\textrm{C} _n q^n (1-q)^{(N-n)}$이 된다. 비슷하게 하늘이가 푸르매에게 $n$회 지원을 해줬을 때 $k$개가 명중할 확률을 $P_k (n)$이라고 하자. 이 때 값은 $_{n}\textrm{C} _k p^k (1-p)^{(n-k)}$ 이다. ..

블로그의 글 중 colab을 사용한 글이 있었는데, 시간이 좀 지나면 연결이 끊기고, 사용량 제한까지 있어 여러모로 불편했기 때문에 내가 가지고 있는 로컬 GPU를 사용해 걱정없이 학습을 진행해보려고 한다. 환경 분리하나의 컴퓨터에서 하나의 프로젝트만 진행하지 않을 수도 있다.또는 현재 컴퓨터에 깔린 프로그램(패키지)의 이전 버전이 필요할 수도 있다.따라서 가상환경은 필수적이다. 파이썬 가상환경을 관리해주는 conda라는 프로그램의 가벼운 버전인 miniconda를 설치한다. 1. miniconda 설치아래 링크에서 다운받을 수 있다.https://www.anaconda.com/docs/getting-started/miniconda/main Miniconda - AnacondaShould I instal..

문제나도 재미있게 본 영화 콘택트를 배경으로 하는 문제이다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ N ≤ 200)의 범위를 갖는다. 각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.풀이문제에서 제시한 찾아야하는 패턴은 (100+1+ | 01)+ 이다.정규표현식을 안다면 쉽게 이해할 수 있을 것이다. 나는 state transition graph를 그려서 풀었다.원래는 NFA에서 DFA로 바꿔서 그리려고 했지만 밑의 그래프도 코드로..

문제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$대의 자동차를 새로 만들..

Vanishing Gradients라는 현상을 알아보자. AI를 학습할 때 backpropagation(역전파)이 진행되는 중에 gradient가 점차 줄어들어 앞쪽 layer에서 거의 학습이 되지 않는 현상이다.역전파는 미분을 계속 곱하면서 전달되는데 이 미분값들이 0~1사이라면 계속 값이 줄어들기 때문이다.sigmoid 함수의 경우 최대 미분값이 0.25이고, 양끝으로 갈수록 미분값은 더 낮아진다.앞쪽 layer에서 가중치 학습이 거의 이루어지지 않고 뒤쪽 layer에서만 조금 학습된다.따라서 전체 학습 속도가 느려지게 된다.이런 현상을 네트워크 앞부분이 죽는다고 표현하기도 한다. 이번 글에서는 2개의 은닉층이 있는 간단한 신경망에서 활성화 함수를 sigmoid와 ReLU로 각각 설정했을 때 학습의 ..

문제생명 공학을 연구하는 현생이는 요즘 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$개의 순서가 정해진 업무를 가지고 있다.각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다.다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다.단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째..