천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

문제 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 그렇지 않으면 J를 인쇄합니다. 조건 입출력 예제 솔루션 먼저 문서의 인덱스와 중요도를 가지고 있는 문서 객체를 만드는 클래스를 구현한다. 클래스 생성 이유 ?) 문서의 인덱스와 중요도를 함께 다루기 위해서 (배열 2개를 사용할 경우 굉장히 번거로울 거라 생각). idx는 중요도가 높은 것부터 차례대로 접근하기 위한 인덱스이며, 순차적으로 문서를 뽑아내는 것이므로 큐 자료구조를 사용한다. 중요도가 담겨 있는 priorities 배열을 순서대로 모두 큐에 삽입해준다 (Offer()). priorities 배열을 오름차순 ..

문제 조건 입출력 예제 솔루션 먼저 정답인 answer = 1로 초기화하고 (성공할 수 있다고 가정), 스택 자료구조를 사용한다. Why 스택 ?) 동일한 문자열이 나오면 스택의 Pop()을 이용하여 제거하고, 다음 문자부터 다시 Push() 하면 될 것이라 판단. 문자열 s의 길이 만큼 반복한다. 스택이 비어 있다면, 문자를 스택에 Push() 한다. 스택이 비어 있지 않다면, 동일한 문자인지 비교한다. 스택의 꼭대기 (Top) 문자와 문자열 s의 i번째 문자가 동일하다면, 스택을 Pop() 하여 제거한다. 동일하지 않다면, 스택에 i번째 문자를 Push() 한다. 반복문이 종료된 이후에도 스택이 비어 있지 않다면, 성공적으로 수행하지 못하는 것이므로 answer = 0 으로 바꿔준다. (실패) Cod..

벨만-포드 (Bellman-Ford) ? 다익스트라 알고리즘은 한 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 중 가장 유용한 알고리즘이다. 하지만, 음수 간선이 있는 그래프의 경우 그 정당성이 보장되지 않는다. 벨만-포드의 최단 경로 알고리즘은 이와 같은 문제점을 해결하는 알고리즘이다. 벨만-포드는 다익스트라와 동일한, 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우, 이 또한 알려준다. 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 이것은 BFS를 기반으로 한 번..

원본 http://colah.github.io/posts/2015-08-Understanding-LSTMs/ The Problem of Long-Term Dependencies RNN의 매력 중 하나는 RNN이 이전 정보를 이전 비디오 프레임을 사용하는 것이 현재 프레임을 이해하는데 도움을 줄 수도 있는 것 같은 현재 작업에 연결할 수 있다는 아이디어임. RNN이 이러한 것을 할 수 있었다면, 엄청나게 유용했을지도 모름. 하지만, 상황에 따라 다름. 가끔, 우리는 현재 작업을 수행하기 위해 최근 정보만을 볼 필요가 있음. 예를 들어, 언어 모델이 이전 단어를 기반으로 다음 단어를 예측하기 위해 시도하는 것을 생각해보겠음. 만약 우리가 "the clouds are in the sky," 의 마지막 단어를 ..

원본 및 참조 http://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-1-introduction-to-rnns/ http://karpathy.github.io/2015/05/21/rnn-effectiveness/ https://wikidocs.net/22886 RNN (Recurrent Neural Network) ? 사람은 매번 생각을 처음부터 시작하지 않음. 당신이 이 에세이를 읽으면서, 이전 단어들에 대한 이해를 바탕으로 각 단어들을 이해함. 모든 것을 버리고 처음부터 다시 사고를 시작하는 것은 아님. 당신의 생각은 지속적이라는 것임. 기존 신경망들은 이러한 점을 할 수 없으며, 이 것은 중요한 결점인 것처럼 보임. 예를 들어, ..

트라이 (Trie) ?도입정수나 실수형 변수는 크기가 항상 정해져 있기 때문에 비교하는데 있어서 상수 시간이 걸린다고 가정해도 된다.하지만 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문에 다르게 다뤄야 한다.N개의 원소를 갖는 이진 탐색 트리에서 원하는 원소를 찾는 경우, 원소 간의 비교를 상수 시간에 할 수 있을 때는 시간 복잡도가 O(log N) 라고 할 수 있다.하지만, 문자열의 비교에는 길이에 비례하는 시간이 걸리므로 문자열의 최대 길이 M을 곱한 O(M * log N) 의 시간 복잡도가 된다.이러한 문제들을 해결하기 위해 고안된 자료구조가 트라이이다.소개트라이는 문자열의 집합을 표현하는 트리 자료구조이며, Prefix Tree 또는 Digital Tree라고도 불린다.문..

Abstract 우리는 질문을 바탕으로 가중치가 적응적으로 결정되는 동적 파라미터 계층과 함께 CNN (Convolutional Neural Network) 을 학습하여 이미지 질문 답변 (ImageQA) 문제를 해결함. 적응 파라미터 예측의 경우, 우리는 별도의 (Separate) 파라미터 예측 네트워크를 사용하며, 이는 질문을 input으로 삼는 GRU (Gated Recurrent Unit) 와 Output으로서 일련의 후보 가중치를 생성하는 완전 연결 계층으로 구성된 별도의 파라미터 예측 네트워크를 사용함. 그러나, CNN의 완전 연결된 동적 파라미터 계층에서 다수의 파라미터에 대한 파라미터 예측 네트워크를 설계하는 것은 어려움. 우리는 동적 파라미터 계층에서 개별 가중치들을 결정하기 위해 미리 ..

플로이드 와샬(Floyd Warshall) ? 모든 쌍 간의 최단 거리를 구하고 싶다면 다익스트라, 벨만-포드 알고리즘보다 좀더 빠르고 간단한 플로이드 (Floyd) 의 모든 쌍 최단 거리 알고리즘을 사용하면 된다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][] 를 계산한다. 이 배열의 원소 dist[u][v] 는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 플로이드 알고리즘의 동작 과정을 이해하기 위해서는 경로의 경유점의 개념을 소개할 필요가 있다. 두 정점 u, v를 잇는 어떤 경로가 있다고 하자. 당연하지만 이 경로는 항상 시작점 u와 끝점 v를 지난다. 이 외에 이 경로는 다른 정점들을 지나쳐 갈 수도 있다. u와 v를 직접 연결하..