STUDY

도둑 문제 다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다. 위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 그림에서 각 집에 적혀 있는 숫자는 집마다 보관 중인 돈의 금액을 나타낸다. 어느 날 이 마을에 도둑이 들었다. 도둑은 이 마을에서 어떻게 도둑질을 할까 잠시 고민하다가, 빠르게 돈을 훔치고 달아나기 위해 M개의 연속된 집에서 돈을 훔치되, 돈을 훔칠 때는 각 집에 보관중인 돈을 전부 훔치기로 했다. 예를 들어..

봄버맨 2 문제 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다. 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이..

세 용액 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액..

걷는 건 귀찮아 문제 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상에서 걷는 게 제일 귀찮은 현솔이는 목적지인 M$M$까지 걷지 않고 인력거만을 타면서 이동하고 싶다. 첫 번째 인력거에 타고 있는 현솔이가 목적지까지 가기 위한 인력거의 최소 환승 횟수를 알아 내보자. 입력 첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$, $1 \le M \le 1\,000\,000$) 둘째 줄에 각 지점의 위치 $p_1$, $p_2$, $...$ , $p_N$이 공백으..

아기돼지와 늑대 문제 산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다. 고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다. 고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다. 게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 ..

인내의 도미노 장인 호석 문제 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 공격과 수비를 하는 게임이다. 공격수는 도미노를 계속 넘어뜨리고 수비수는 도미노를 계속 세우려고 한다. 본 게임은 다음과 같이 진행된다. N 행 M 열의 2차원 격자 모양의 게임판의 각 격자에 도미노를 세운다. 각 도미노는 1 이상 5 이하의 높이를 가진다. 매 라운드는 공격수가 먼저 공격하고, 수비수는 공격이 끝난 뒤에 수비를 한다. 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다. 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-..

visual attention Show, attend and tell Transformer (Self-attention) Sound representation Speech processing - Modules and applications Metric learning : positive pair(연관성이 있는)는 거리를 가깝게 negatve pair는 멀어지게 유도하는 학습 방법. 을 사용하여 joint embedding space를 디자인 기존 이미지 캡셔님의 문제점 - Attention의 등장(요즘 유행하는 Transformer에 나오는 그 Attention 맞음) - 상대적인 관계나 공간 위치가 고려되지 않음. - Global average pooling 같은 과정에서 작은 사물들이 무시되는 경향이..

Multi-Model Learning Text embedding Image tagging Recurrent neural networks Image captioning Multi-Model Learning 다양한 형태로 이루어진 데이터 특징을 효과적으로 학습하기 위한 방법 Multi-Model Learning 의 어려움 - 소리는 웨이브 형태의 데이터, 영상은 2차원의 칼라값을 넣은 array 형태, Text는 벡터로 존재. 각각의 데이터 표현 방식과 자료 구조가 다름. - 서로다른 데이터 타입 간 가지고 있는 정보의 비대칭 관계 하나의 문장이 여러 Image로 표현이 가능함. Text embedding - 문자열 표현은 인공지능 모델들이 사용하기에 어려움. - Dense vector로 치환하여 사용(Co..

CNN vs FNN(Fully-Connected NN) FNN : 데이터가 주어지면 하나의 피처를 뽑기위해서(하나의 히든 노드를 정의하기위해서) 모든 연결을 다 사용함. - 우리가 배워야하는 파라미터가 기하급수적으로 커짐. 조금만 변경되어도 파라미터 값이 많이 달라짐. LNN(Locally-Connected NN) : CNN 전단계, 국소적인 부분만 뉴럴 네트워크를 정의. 해당부분으로만 연결이 되어서 하나의 히든 노드를 도출. - 배워야하는 파라미터의 수가 줄어듦. 이렇게 하는 이유는 영상의 경우 전체를 보지 않고 부분적인 부분만 봐도 무엇인지 파악할 수 있기 때문. # 해당 영역의 파라미터를 다른 영역에서도 사용가능. 즉, 파라미터를 공유(이는 LNN에서 CNN으로 변환되는 과정) - 적은 파라미터로 ..

기계학습의 구성요소 - 경험 사례 - 모델 - 평가 기준 기계 학습이란? 계산/추론(computation/inference) : 함수를 주고, Output이 나오도록 계산 (F = ma, V = IR) 최적화(Optimization) : 한 세트의 (input,output)을 주고, 관계를 가장 잘 설명하는 f(함수)를 찾는 것. 이 2가지는 input과 output 두가지와 에러만 없으면 되지만, 우리가 모든 데이터를 사용할 수 없다. 즉, 우리가 모르는 데이터를 입력 하였을 때 제대로된 출력이 나오게 만들어야한다. 이는 일반화(Generalization)을 통해 수행되어진다. 일반화(Generalization) : 최적화를 통해 학습된 함수를 통해 학습된 적 없는 입력을 가지고 정확한 출력을 나오도록..