Oneulog

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시..

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 예시) 선수과목을 고려한 학습 순서 결정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다. 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 ..

https://school.programmers.co.kr/learn/courses/30/lessons/152995 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 ..

Bag of Words란 Bag of Words란 단어들의 순서는 전혀 고려하지 않고, 단어들의 출현 빈도에만 집중하는 텍스트 데이터의 수치화 표현 방법이다. Bag of Words를 직역하면 단어들의 가방이라는 의미이다. 단어들이 들어있는 가방을 상상해보자. 갖고 있는 어떤 텍스트 문서에 있는 단어들을 가방에다가 전부 넣는다. 그 후에 이 가방을 흔들어 단어들을 섞는다. 만약, 해당 문서 내에서 특정 단어가 N번 등장했다면, 이 가방에는 그 특정 단어가 N개 있게 된다. 또한 가방을 흔들어가 단어를 섞었기 떄문에 더 이상 단어의 순서는 중요하지 않다. BoW를 만드는 과정을 이렇게 두 가지 과정으로 생각해보자. 1. 각 단어에 고요한 정수 인덱스를 부여한다. # 단어 집합 생성 2. 각 인덱스의 위치에..

단어의 표현 방법 단어의 표현 방법은 크게 국소 표현과 분산 표현으로 나뉜다. 국소 표현 방법은 해당 단어 그 자체만 보고, 특정값을 매핑하여 단어를 표현하는 방법이며, 분산 표현 방법은 그 단어를 표현하고자 주변을 참고하여 단어를 표현하는 방법이다. 예를 들어 puppy(강아지), cute(귀여운), lovely(사랑스러운)라는 단어가 있을 때 각 단어에 1번, 2번, 3번 등과 같은 숫자를 매핑하여 부여한다면 이는 국소 표현 방법에 해당된다. 반면, 분산 표현 방법의 예를 하나 들어보면 해당 단어를 표현하기 위해 주변 단어를 참고한다. puppy라는 단어는 cute, lovely한 느낌이다로 단어를 정의한다. 이렇게 되면 이 두 방법의 차이는 국소 표현 방법은 단어의 의미, 뉘앙스를 표현할 수 없지만..

자연어 처리에서 텍스트를 표현하는 방법으로는 여러 가지 방법이 있다. 그 중 DTM(Document Term Matrix)과 TF-IDF(Term Frequency-Inverse Document Frequency)는 정보 검색과 텍스트 마이닝 분야에서 주로 사용되는 카운트 기반의 텍스트 표현 방법이다. 텍스트를 위와 같은 방식으로 수치화를 하고 나면, 통계적인 접근 방법을 통해 여러 문서로 이루어진 텍스트 데이터가 있을 때 어떤 단어가 특정 문서 내에서 얼마나 중요한 것인지를 나타내거나, 문서의 핵심어 추출, 검색 엔진에서 검색 결과의 순위 결정, 문서들 간의 유사도를 구하는 등의 용도로 사용할 수 있다.

두 개의 모델 A, B가 있을 때 이 모델의 성능은 어떻게 비교할 수 있을까? 두 개의 모델을 오타 교정, 기계 번역 등의 평가에 투입해볼 수 있다. 그리고 두 모델이 해당 업무의 성능을 누가 더 잘했는지를 비교하면 된다. 그런데 두 모델의 성능을 비교하고자, 일일히 모델들에 대해서 실제 작업을 시켜보고 정확도를 비교하는 작업은 공수가 너무 많이 드는 작업이다. 만약 비교해야 하는 모델이 두 개가 아니라 그 이상의 수라면 시간은 비교해야 하는 모델의 수만큼 배로 늘어날 수도 있다. 이러한 평가보다는 어쩌면 조금은 부정확할 수는 있어도 테스트 데이터에 대해서 빠르게 식으로 계산되는 더 간단한 평가 방법이 있다. 바로 모델 내에서 자신의 성능을 수치화하여 결과를 내놓는 펄플랙시티(perplexity)이다. ..

영어나 기타 언어에 비해서 한국어는 언어 모델로 다음 단어를 예측하기가 훨씬 까다롭다. 한국어는 어순이 중요하지 않다. 한국어에서는 어순이 중요하지 않다. 그래서 이전 단어가 주어졌을 때, 다음 단어가 나타날 확률을 구해야 하는데 어순이 중요하지 않다는 것은 다음 단어로 어떤 단어든 등장할 수 있다는 의미이다. 1. 나는 운동을 합니다 체육관에서. 2. 나는 체육관에서 운동을 합니다. 3. 체육관에서 운동을 합니다. 4. 나는 운동을 체육관에서 합니다. 위의 4개의 문장은 전부 의미가 통하는 것을 볼 수 있다. 심지어 '나는' 이라는 주어를 생략해도 말이 되어버린다. 이렇게 단어 순서를 뒤죽박죽으로 바꾸어놔도 한국어는 의미가 전달되기 때무에 확률에 기반한 언어 모델이 제대로 다음 단어를 예측하기가 어렵다..