목록분류 전체보기 (116)
while (1): study();
투 포인터(Two Pointers) 알고리즘은 말 그대로 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 간단하게 얘기하면 '시작점'과 '끝점'을 이용하여 데이터의 범위를 표현하는 방법론입니다. 특정한 합을 가지는 부분 연속 수열 특정한 합을 가지는 부분 연속 수열을 찾아야 할 때, 투포인터 알고리즘이 유용하게 쓰일 수 있습니다. 절차는 다음과 같습니다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2. 현재 부분합이 M과 같다면 카운트한다. 3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다. 4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까..
특정한 수의 소수 판별 특정한 수가 소수(Prime number)인지 여부를 판별하기 위해서는 해당 수에 이르기까지 모든 수를 나누어보고 나머지가 0인지 확인하면 됩니다. import math def is_prime_number(x): for i in range(2, x): if x % i == 0: return False return True is_prime_number(1e100) 단 이 경우엔 x가 매우 큰 값일 경우 계산해야 하는 경우의 수가 많아져 결과적으로 효율성이 저하됩니다. 따라서 이를 개선하기 위해서 약수(Dvisor)의 성질을 알고 있다면 좋습니다. 모든 수는 자신의 모든 약수에 대해서 대칭적인 형태를 보입니다. 16을 예로 들었을 때, 16의 약수는 1, 2, 4, 8, 16이며 1 ..
1. 데이터 모델링의 이해 데이터 모델링이란? 더보기 1) 업무 분석 기법 2) 약속된 표기법으로 표현 3) DB 구축을 위한 분석/설계 과정 데이터 모델링 유의점 더보기 1) 중복 2) 비유연성 3) 비일관성 Peter Chen 표기법 엔터티 - 특징 더보기 1. 필요성 2. 유일성 (식별자) 3. 인스턴스 4. 프로세스 5. 속성 6.관계 - 분류 더보기 1. 유무형에 따른 분류 유형 엔터티, 개념 엔터티, 사건 엔터티 2. 발생시점에 따른 분류 기본 엔터티, 중심 엔터티, 행위 엔터티 속성 더보기 업무에서 필요로 하는 인스턴스에서 관리하고자 하는 의미상 더 이상 분리되지 않는 최소의 데이터 단위 한 개의 엔터티는 두 개 이상의 속성을 가짐 관계 더보기 1) 관계속성 관계를 정의할 목적으로 생성된 속..
출처: https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 최근 바빴던지라 문제풀이를 전혀 못했었는데, 오랜만에 한번 풀어봤습니다. 오랜만에 푼 게 삼성전자 공채 기출문제라니 쉽지는 않았으나.. 오히려 이전 청소년 상어보다 훨씬 쉽게 풀었습니다. 문제 조건 자체가 상당히 복잡하게 느껴졌는데, 이전에 한번 청소년 상어에서 호되게 당해서 그런지 몰라도 차근차근 구현하니까 풀만하게 느껴집니다. 전형적인 구현(..
드디어 최근 인공지능 SOTA의 핵심에 서있는 어텐션을 구현합니다. 이전까지 단어 간 대응 관계를 나타내는 정보인 얼라인먼트(Alignment)를 인간이 직접 만들어야만 했다면, 어텐션은 얼라인먼트조차 기계가 대신 학습한다는 점에서 큰 의미가 있습니다. 간단하게 얘기하면 인코더의 은닉상태를 입력으로 받아, 디코더의 은닉상태와 내적한 뒤 소프트맥스로 정규화하여 가중치를 구하고, 이를 이용하여 가중합을 구해 맥락 벡터(Context vector)를 생성합니다. 이전 장에서 Peeky를 이용하여 인코더의 은닉상태를 디코더의 모든 계층에 전달했었는데, Attention은 이 과정을 조금 더 효율적으로 수행하고 있습니다. 그리고 Seq2seq 모델의 관건이 인코더의 맥락을 디코더에 제대로 전달하는 것이라는 것도 ..
이번 장에서는 RNN 아키텍처를 이용한 생성 모델의 끝판왕인 Seq2Seq을 간단하게 구현해봅니다. 일전에 Seq2seq 기계번역기를 수업을 들으며 꽤 그럴싸하게 구현한 적이 있었는데, 당시엔 파이토치를 사용하여 구현했기 때문에, 원리도 알아볼겸 천천히 책을 따라가봤습니다. 일전에 구현했던 기계번역기 모듈은 다음 깃허브 레포에 있습니다. https://github.com/jeongchanyoung-1234/Neural_Machine_Translation GitHub - jeongchanyoung-1234/Neural_Machine_Translation: Neural Machine Translation with Attention (Experiment result will be up Neural Machin..
이번 장에서는 Vanilla RNN에서 개선된 버전인 LSTM을 구현하여 본격적인 RNN LM을 구축합니다. 기존의 Vanilla RNN은 다음과 같이 계산됩니다. $$h_{t} = tanh(h_{t-1}W_{h} + x_{t}W_{x} + b)$$ 이 때 $W_{h}$와 $W_{X}$는 계층 내에서 같은 가중치이므로, 타임스탭이 길어질 때마다 매번 같은(정확히는 비슷한) 행렬이 입력에 곱해지게 됩니다. 행렬의 최대 특잇값이 1보다 크다면 출력은 지수적으로 증가하고, 1보다 작으면 지수적으로 감소합니다. 따라서 역전파 과정에서 커지거나 작아진 가중치가 곱해지면 기울기도 그에 따라서 폭발하거나 소실될 가능성이 증가합니다. 또한 하이퍼볼릭 탄젠트 함수의 도함수가 0부터 1사이의 값을 가질 수 있기 때문에, ..
드디어 자연어처리의 핵심 기술 중 하나라고 할 수 있는 순환 신경망에 접어들었습니다. 저번 장에서 구현했던 CBOW는 기본적으로 FFN(Feed Forward Network)이며, 결과적으로 임의의 귀납적 편향(Arbitrary inductive bias)를 주입합니다. 쉽게 말하면 자연어의 특성 중 하나인 순차성에 대해서는 전혀 고려하지 않는다는 것입니다. 따라서 언어모델을 구축하기 위해서는 다른 아키텍처가 필요합니다. 언어모델(LM; Language Model)이란 특정한 언어 시퀀스의 확률을 반환하는 모델으로, 실제 일상 속 문장의 발생확률을 모사하는 것을 목표로 합니다. 문장의 발생 확률은 간단하게 다음과 같이 동시확률로 표현할 수 있습니다. $$P(w_{1}, w_{2}, ...)$$ 여기에 순..
이 장에서는 이전 장에서 구현했던 Word2Vec의 속도를 개선해봅니다. 두 가지 측면에서 개선점이 있습니다. 1. Embedding layer를 이용한 입력층 연산 감소 2. Negative sampling을 이용한 출력층 연산 감소 추가적으로 단어의 밀집 벡터를 통계 기반 방법으로 얻은 경우 Distributional representation이라고 표현하며, 추론 기반 방법으로 얻은 경우 Distributed representation이라고 표현합니다. 따라서 우리는 결론적으로 최적의 Distributed representation을 얻는 것이 목표입니다. 1. Embedding layer 이전의 CBOW는 입력 가중치가 (Vocab size, Hidden size)였습니다. 입력으로 주어지는 맥락..
이전 장에서 통계 기반 방법론에 대해서 학습했고, 이번 장에서는 추론 기반 방법론에 대해 배웁니다. 가장 큰 차이점은 통계 기반 방법론이 전체 코퍼스에 대해서 1회 처리하는 데에 비해, 추론 기반 방법론은 미니배치 단위로 학습하는 것이 가능하다는 점입니다. 결과적으로 메모리 사용량을 획기적으로 줄일 수 있고, GPU로 병렬처리 시 시간도 단축할 수 있습니다. 다만 두 방법론은 모두 분포가설에서 출발하는 것은 같습니다. 대표적인 모델로는 CBOW와 Skip-gram이 있습니다. CBOW(Continuous Bag-of-Words)는 맥락을 받아 타겟을 학습합니다. 아래와 같이 다수의 맥락을 배경지식으로 삼아 등장할 단어를 예측하는 것이 바로 CBOW입니다. 이때 입력과 연산되는 가중치, 즉 그림에서 $W_..