목록분류 전체보기 (405)
오답노트
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. 주어지는 작업은 정렬되어 있다는 가정이 존재하지 않는다. 그러므로 시작시간을 기준으로 정렬한다. (난 그냥 heapq를 사용해서 오름차순 정렬을 했음) 2. 정렬된 작업들에서 마지막에 수행된 작업시간 이전에 요청된 작업을 뽑는다. 3. 뽑은 작업들을 다시 heapq에 담는다 대신 작업의 소요시간 순으로 오름차순 정렬될 수 있도록 한다. 4. 그 중 가..
문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 우선 최소 힙과 최대 힙을 각각 만든다. 기본적인 아이디어는 두 힙을 서로 동기화 시키는데에 있다. 하지만 무조건 동기화만 시킨다면 시간 초과로 문제를 풀 수 없다. 지금부터는 자명한 정답들에 대한 내 생각이다. 시간 초과를 극복하기 위해서는 문제에서 요구하는 조건만 충족시키는 한에서 두 힙을 동기화 시키는 것이 가장 적절해 보인다. 즉, 두 힙을 무조건 동기화 시킬 필요가 없다는 것이다. 아래 사진은 예제 입력1에 두번째 케이스에서 정답을 출력하..
문제 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의 모델을 도..