Cara's Moving Cara's Moving

Union_find를 사용해서 푸는 문제들을 여러 풀면서 정리해 보았다. 문제를 간단히 정리하자면, input으로 들어오는 두 친구 정보 (ex. ("Fred", "Barney")) 사이에 존재하는 친구 수를 구하는 문제이다. 다만, 이 입력되는 친구가 서로 이미 친구라고 가정한다. 또한, 친구 수에는 본인도 포함한다. 따라서, Fred는 Barney는 본인을 포함하여 최소 2의 값을 가진다. https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을..

Kaggle의 랭커들의 전략을 보면, 많이들 CRF layer를 활용했다. 사용자가 설정한 모델에 CRF layer을 추가적으로 붙이는 것은 'from keras_contrib.layers import CRF로 한 줄이면 활용하면 간단하게 끝나지만, 이 CRF가 왜 다양한 NLP문제에서 활용되고 있는지, 왜 이 CRF layer가 효과적인지 평소에 궁금하여 이번 포스팅에 다루게 되었다. CRF(Conditional Random Field) 는 Sequence tagging task를 위한 graphical model 중 하나이다. Sequence tagging task에서 가장 널리 알려진 개체명인식 문제 NER(Name Entity Recognition)에 CRF는 자주 적용되고 있기도 하다. CRF는..

Dataframe의 apply 메서드는 주어진 Dataframe에서 데이터를 사용자의 의도에 따라서 재가공하고자 하는 경우 사용된다. Dataframe의 1차원 배열이나의 각 행/열의 원소들에 임의의 함수를 적용하여 원하는 값을 얻을 수 있다. apply메서드를 적용할 수 있는 여러 문제 상황을 구체적으로 설명하면서 소개하겠다. 먼저, 자연어처리의 NER task에서 다음과 같은 Dataframe을 얻었다고 가정해보자. 1) 특정 컬럼값의 모든 원소에 함수를 적용하고자 할 경우 data['Sentence #']의 컬럼에서 나는 문장 번호를 따로 떼어내서 새로운 칼럼 data['number']에 넣고 싶다. 아래와 같은 함수를 만든 뒤, sent_number = lambda x: int(x.split()[..

dataframe의 정보들을 그룹핑하여 유의미한 통계량을 내는데 있어서 자주 쓰는 함수가 groupby다. 컬럼 혹은 인덱스에서 구조화되지 않은 경우, dataframe.groupby(['컬럼명'])으로 그룹지은 후, 사용자의 의도에 맞는 함수를 적용시켜 이것에 대한 세부 통계를 구한다. 실제 분석에 사용한 데이터를 가지고 이해해보자. game_id(게임 대전 고유 번호), winner, time, player, species, event, event_contents 로 칼럼으로 구성된 게임 데이터셋 train이 있다고 가정하자. 위의 데이터셋에서 나는 특정 게임 대전 마다(game_id) event에서 각 세부 게임 로그 활동이 얼마만큼 일어나는지를 알고 싶었다. 즉, game id가 0일 때, Cam..

https://pongdangstory.tistory.com/487 이전 포스팅에서, Unfractional knapsack problem을 다루었다. 이번에는 가방에 물건을 담을 때, 물건의 일부를 담는 경우는 어떠할까? 믹서기 같은 물건의 경우, 믹서기를 쪼개면 그 기능을 다하지 못하기 때문에 쪼갤 수 없는 반면에, 초콜릿이라고 한다면, 초콜릿은 소분해서 담을 수 있고 그 가치도 그 소분한 가치만큼에 해당하기 때문에 쪼갤 수 있다. 이 경우 그리디 알고리즘의 접근법으로 비교적 간단히 풀 수 있다. 이전의 input과 동일하게 문제가 주어졌다고 가정하자. K는 가방에 담을 수 있는 최대 무게 상한선이다. 즉, 물건이든, 물건의 부분이든 이 K kg의 무게를 넘을 수 없다. stuff_array는 다음과..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 냅색알고리즘이라고 불리는 이 유명한 문제는 다음과 같다. 가방에 가치를 극대화하도록 물건들을 담아야 한다. 이 때 가방은 특정 무게 이상을 담을 수 없다. 제한된 K kg의 이하의 물건들을 담을 수 있다. 물건들은 (Weight, Value)로 무게와 가치라는 원소를 가지고 있다...

문제 출처; https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 위의 그림에서 왼쪽 끝에서부터 오른쪽 아래까지 지나갈 수 있는 경로 수에 대해서 구해야 한다. 단, 움직일 때 원래 위치한..

Self-attention이 있는 Transformer의 후속 모델들은 positional encoding도 transformer의 방식을 따른다. 본 포스팅은 Positional Encoding부분을 자세하게 다루고자 한다. "Attention is all you need"라는 논문에서 cos, sin함수를 활용하여 토큰의 위치정보를 보완한다고 하는데, 이게 어떻게 이뤄지는 건지 궁금했었다. 논문에서는 cos, sin함수를 활용했다고만 언급되어 있다. 이 부분을 읽으면서 들었던 생각은, 단순히 문장에 속한 단어 토큰에 1,2,3, ..., 등의 정수를 붙여주면 안되나? 2π라는 주기와 최대 최소값을 가지고 있는 cos, sin함수를 굳이 활용하는 이유가 있을까라는 의문점이 들었다. 먼저 위치정보를 정수..