오답노트

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 1. 회의실 배정이 끝나는 시간을 오름차순 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 오름차순 정렬한다. 2. 정렬된 상태에서 가장 먼저 시작하는 회의를 선택한다. 3. 문제의 조건에 맞춰 선택된 회의의 끝나는 시간보다 같거나 큰 시간의 시작 시간을 가진 회의를 선택한다. 4. 3번을 계속 반복하며 회의를 선택한다. 위 과정을 통해 예제 입력1을 풀이한 결과는 다음과 같다. 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 (8,11),(8,12) 같은 경우 2번을 통해 (8,11) 선택해야한다. 코드 import sys ..

문제 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 예제입력과 내가 자체적으로 만든 Test Case를 통해 풀이할 것이다. 예제입력 예제입력은 위 사진의 표와 같이 입력된다. 1. dp 테이블을 만든다. 이때 기존에 주어진 n x m 보다 큰 (n+1) x (m+1) 크기의 테이블을 만든다. 테이블의 원소는 모두 0으로 초기화 한다. 아래 사진에는 설명을 위해 입력 테이블에 행과 열을 하나씩 추가했다. 2. dp 테이블 기준으로 (1,1)부터 2x2 사각형의 오른쪽 아래 지점으로 가정한다. 그리고 한 칸씩 방문하여 입력 테이블에 1인 지점에서 점화식을 계산한다. 점화식은..

문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 1. 이번 예시에서는 동전의 종류는 2원, 4원, 7원이고 이를 사용해서 11을 만드는 경우의 수를 찾아야한다. 우선 dp 테이블을 2차원 배열로 row는 가지고 있는 동전의 종류 col은 0부터 M까지로 만든다. 2. 동전의 종류 중 가장 작은 값인 2를 초항으로 선택한다. 2로 0원부터 11원까지 만들 수 있는 경우의 수를 모두 입력한다. 여기서 0원을 만들 수 있는 경우의 수는 무조건 1이다. (각 동전을 사용하지 않는 경우에 0..

https://arxiv.org/pdf/1708.05031.pdf 서론 LG U+에서 주최한 AI Ground 경진대회에서 알게된 딥러닝 기반 추천시스템 알고리즘이다. 경진대회를 참가 했을 때는 추천 시스템에 대한 개념이 아예 없어서 제대로 해보지도 못하고 대회를 마무리 했는데, 어떤 계기로 인해 추천 시스템을 계속 공부하고 있다. 본론 기존 Matrix Factorization sij 를 유저 i와 유저j 의 관계로 봤을 때, s23(0.66) > s12(0.5) > s13(0.4)의 관계를 가지고 있다. 이를 기하학적으로 봤을 때, (b)처럼 p2와 p3이 가장 가깝고 p1과 p3이 가장 멀다. 선형적인 공간에서 u4과 같은 새로운 유저가 등장하면 문제가 발생한다. 유저 4와 다른 유저들과의 관계는 ..

순위 지표 순위 지표는 추천 시스템이 제공하는 추천 결과의 순서와 실제 사용자의 선호도 순서 간의 유사성을 측정하는 지표다. 순위 지표는 일반적으로 정확도 지표와는 달리, 추천 결과가 아이템 리스트의 어떤 위치에 있는지에 초점을 둔다. 이러한 이유로, 순위 지표는 추천 시스템의 실제 사용 상황을 잘 반영한다. MAP (평균 정밀도, Mean Average Precision) MAP는 Precision@k의 평균 값이다. 여기서 k는 추천 리스트에서 고려하는 상위 k개의 아이템이다. MAP는 추천 시스템이 추천한 아이템 중 실제로 관심 있는 아이템이 있는 비율에 초점을 둔다. 위 그림에서 추천은 각 인덱스는 사용자에 추천할 아이템이고 0은 모델이 추천하지 않는 것, 1은 모델이 추천했음을 의미한다. 첫번째..

정확도 지표 분류문제에서 자주 사용되는 지표들을 의미한다. 추천시스템에서는 제공하는 추천 결과 중에서 실제로 사용자가 선호하는 아이템의 비율을 측정하는 지표다. 대표적으로 정확도 (Accuracy), 정밀도 (Precision), 재현율 (Recall), F1-Score이 존재한다. 정확도 (Accuracy) 정확도는 모든 경우에서 예측과 실측이 모두 맞았을 때를 의미한다. 하지만 데이터가 편향되어 있다면 그 신뢰성이 많이 떨어진다. 예를들어 True가 일반적인 Domain에서 가끔 False가 등장한다고 했을 때, 모델이 대부분을 True로 예측할 것이다. 그렇다면 True에 대한 정확도는 높지만 False에 대한 정확도는 낮다는 단점이 있다. 정밀도 (Precision) 정밀도는 예측이 True인 것..

Embedding Embedding은 sparse 벡터 데이터를 dense 벡터 데이터로 변환 하는 것을 의미한다. sparse 벡터 데이터는 One-Hot Encoding된 데이터인데, One-Hot Encoding은 데이터 마다 인덱스를 부여하고 데이터의 유니크 개수 만큼의 차원의 벡터에 해당 인덱스에 1을 입력하는 것이다. 위 그림에서 red는 [1,0,0], blue는 [0,1,0], green는 [0,0,1] 으로 표현 가능하다. dense 벡터 데이터는 sparse 벡터 데이터와 달리 0이 대부분 없는 데이터를 의미한다. sparse 벡터 데이터를 dense 벡터 데이터로 변환할 때 가중치 테이블을 사용해 변환하게 되는데, 역전파를 통해 이 가중치 테이블이 계속 업데이트 된다. Embeddin..

Negative Sampling 네거티브 샘플링은 다중 분류 문제에서 이진 분류 문제로 바꾸는 것에 초점을 준다. 다중 분류에서 이진 분류로 문제를 바꾸므로 임베딩 벡터 값을 업데이트 시킬 때, 원하는 벡터 값만 업데이트 한다. 이 과정에서 연산량이 크게 줄어든다. NLP에서의 Negative Sampling Skip-gram에서 Negative Sampling를 사용할 수 있다. Skip-gram은 주변 단어를 예측하기 위해 중심 단어를 활용하는 모델이다. 즉, Skip-gram은 중심 단어를 input으로 주변 단어들 중 1개를 맞추는 다중 분류 문제인 것이다. 하지만 Skip-gram에 Negative Sampling을 사용하여 이진 문제로 바꿀 수 있다. 위는 기존의 Skip-gram의 모델을 도..

Collaborative Filtering 협업 필터링은 사용자와 항목의 유사성을 동시에 고려해 추천한다. 기존에 사용자의 관심사가 아닌 항목도 추천 가능하고 자동으로 임베딩 학습이 가능해 도메인 지식이 필요없다. 하지만 학습 과정에 나오지 않은 항목은 임베딩을 만들 수 없다. 또 추가 특성을 사용하기 어렵다. KNN 머신러닝에서 봤던 KNN과 같은 원리다. 가장 근접한 K 명의 이웃을 통해서 예측하는 방법. https://dhjkl123.tistory.com/226 [ML] KNN (K-Nearest Neighbors) KNN 예측 데이터의 변수로 부터 실측 데이터의 변수 사이의 거리를 계산하여 그 중 가장 가까운 k개 데이터의 평균으로 타겟 데이터를 예측하는 알고리즘 (출처 : https://pub...

Content-based Filtering Content-based Filtering은 이전의 행동과 명시적 피드백을 통해 좋아하는 것과 유사한 항목을 추천한다. 유사도를 기반으로 추천한다. 많은 수의 사용자를 대상으로 쉽게 확장 가능하고 사용자가 관심을 갖지 않던 상품까지 추천 가능한 장점이 있다. 하지만 입력 특성을 직접 설계해야 하기 때문에 많은 도메인 시직이 필요하고 사용자의 기존 관심사항을 기반으로만 추천 가능한 단점이 있다. 유클리드 거리 위에서 유사도를 기반으로 추천한다고 했는데, 그 중 사용되는 유사도인 유클리드 거리 유사도이다. 이를 Python 코드로 구현하면 아래와 같다. import numpy as np euclidean_dist = np.sqrt(np.sum(np.square(my..