본문 바로가기

분류 전체보기156

[컴파일러] - 구문 분석 (Syntax Analysis) III 1. 상향식 파싱 (bottom-up parsing) 상향식 파싱은 트리의 가장 아래쪽에 위치한 leaf node에서 시작하여 트리의 최상단인 root node쪽으로 진행하면서 파싱을 수행하는 방법이다 [그릠 1]. 상향식 파싱에는 이동-감축 파싱 (shift-reduce parsing)이라고 하는 상향식 파싱의 일반적인 유형이 있으며, 하향식 파싱을 위한 LL 문법과 같이 상향식 파싱을 위한 LR 문법이 있다. 상향식 파싱은 완성된 파스 트리 (parse tree)의 관점에서 볼 때, 가장 우측의 nonterminal 부터 유도 (derivation)가 이루어지기 때문에 입력 문자열에 대한 최우단 유도 (rightmost derivation)을 찾는 것과 같다. [그릠 1] 상향식 파싱 (bottom-.. 2016. 8. 21.
[컴파일러] - 구문 분석 (Syntax Analysis) II 1. 하향식 파싱 (Top-down parsing) 하향식 파싱은 root node에서 시작하여 파스 트리의 노드들을 전위 순서 (preorder)에 따라 생성하는 것이다 [그림 1]. 따라서, 하향식 파싱은 항상 문자열의 가장 왼쪽 nonterminal부터 유도가 이루어지기 때문에 하향식 파싱은 입력 문자열에 대한 최좌단 유도 (leftmost derivation)을 찾는 것과 같다. [그림 1] 하향식 파싱 (top-down parsing)을 통한 파스 트리 (parse tree)의 생성 하향식 파싱에는 가장 일반적인 형태인 재귀적 하강 파싱 (recursive descent parsing)과 재귀가 필요없는 예측 파싱 (predict parsing) 등이 있다. 2, 재귀적 하강 파싱 (Recurs.. 2016. 8. 21.
[컴파일러] - 구문 분석 (Syntax Analysis) I 1. 개요 컴파일러에서는 구문 분석을 수행하는 모듈을 파서 (parser)라고 한다. 파서는 어휘 분석기에서 생성한 토큰 스트림이 생성 가능한 것인지를 판별하고, 토큰 스트림으로부터 파스 트리 (parse tree)를 생성한다.파서의 일반적인 유형으로는 보편적 (universal), 하향식 (top-down), 상향식 (bottom-up)이 있다. 보편적 파싱 방법은 어떠한 문법도 파싱할 수 있지만, 파싱 과정이 매우 비효율적이기 때문에 상용 컴파일러에는 적용될 수 없다. 따라서, 컴파일러에서는 하향식과 상향식 파서가 이용되며, 주로 상향식 파서가 많이 이용된다. 2. 문맥 자유 문법 (Context-free grammar, CFG) 우리가 영어 문장에서 문법적 오류를 검출하기 위해서는 영어 문법을 이해.. 2016. 8. 20.
[머신러닝] - Autoencoder 1. 개요 Autoencoder는 이미지 데이터의 압축을 위해 연구된 인공신경망 (Artificial Neural Networks, ANNs)이다. Autoencoder의 구조는 일반적인 feedforward neural networks (FNNs)와 유사하지만, autoencoder는 비지도 학습 (unsupervised learning) 모델이다 [1]. Autoencoder는 기존에 대부분 데이터의 압축을 위해 활용되었으나, 최근에는 딥 러닝 (deep learning)에 대한 연구가 활발해지면서 입력 벡터의 차원 축소, 은닉층의 학습 등에 많이 이용되고 있다 [2, 3]. 2. 구조 Autoencoder의 구조는 일반적인 FNN의 구조와 매우 유사하며, 한 가지 다른 점은 입력층 (input la.. 2016. 7. 30.
학습 모델의 종류 1. 비지도 학습 (Unsupervised Learning) 비지도 학습은 학습 벡터에 목표값 (target value)이 없을 때, 학습 데이터의 관계를 추론하여 학습을 진행하는 방식이다. 예를 들어, 비지도 학습에서는 고양이라는 것을 알려주지 않고 아래의 그림을 보여준다. 비지도 학습의 목표는 머신러닝 알고리즘이 아래의 [그림 1]을 보고 '네 마리의 동물은 고양이다'라고 학습하는 것이 아니라, '네 마리의 동물은 서로 같은 종'이라는 사실을 추론하는 것이다. [그림 1] 서로 연관이 있는 학습 데이터들 비지도 학습은 통계학의 밀도 추정 (density estimation)과 깊은 연관이 있으며, 머신러닝 및 데이터 마이닝 분야에서는 클러스터링 (clustering)에 많이 이용된다. 비지도 학습 또.. 2016. 7. 21.
딥 러닝 소개 1. 딥 러닝 (Deep Learning) 2012년, 구글은 1만 6천개의 컴퓨터 프로세스와 10억 개 이상의 neural networks 그리고 deep neural networks (DNNs)을 이용하여 유튜브에 업로드 되어 있는 천만 개가 넘는 비디오에서 고양이를 인식해내는 프로젝트에 성공하였다. 구글이 천만 개가 넘는 비디오에서 고양이를 인식하는데 사용한 기술이 바로 딥 러닝이다. 최근에는 마이크로소프트, 페이스북 등의 IT 기업에서도 딥 러닝 분야의 연구팀을 인수하거나 자체 개발 부서를 운영하고 있다. 마이크로소프트에서 개발한 감정 인식 API와 페이스북에서 개발한 얼굴 인식 API는 모두 놀라운 정확도를 보여주고 있다. 2. 딥 러닝의 정의 많은 자료와 기사에서 딥 러닝을 소개하지만, 자료마.. 2016. 7. 18.
[머신러닝] - Complex-Valued Neuron (CVN) 1. 개요 일반적인 neural network의 neuron은 가중치와 입력값, 출력값이 실수 도메인에 존재하며, 이러한 neural networks를 real-valued neural networks (RVNNs)라고 하고, RVNNs를 구성하는 각각의 neuron를 real-valued neuron (RVN)이라고 한다. 이 글에서 소개하는 complex-valued neuron (CVN)은 RVN과 같은 구조 및 데이터 처리 과정을 갖지만, 가중치와 입력값, 출력값이 복소 도메인에 존재한다. CVN으로 이루어지는 complex-valued neural networks (CVNNs)는 현재까지도 많은 연구가 이루어지고 있는 분야이며, RVNNs에 비해 다소 복잡한 구조를 갖고 있다. 특히, 실수 도메.. 2016. 7. 8.
이진 탐색 트리(Binary Search Tree) 1. 개요 이진 탐색 트리(binary search tree)는 각 노드가 최대 2개의 child node를 갖는 이진 트리(binary tree)의 특수한 형태이다. 이진 탐색 트리는 데이터를 정렬된 형태로 보관하기 때문에 효율적으로 탐색 연산을 수행할 수 있다. 평균적으로 이진 탐색 트리에서 탐색 연산의 시간복잡도는 $O(\log_2n)$이다. 그러나 이진 탐색 트리는 입력되는 값의 순서에 따라 트리의 구성이 달라지기 때문에 트리가 한쪽으로 기울어진 편향 이진 트리(skewed binary tree)가 생성될 수 있다. 이러한 경우에는 탐색 연산의 시간복잡도가 $O(n)$으로 급증한다. 2. 정의 이진 탐색 트리의 정의는 아래와 같다. 각 노드는 최대 2개의 child node만을 가질 수 있다.노드.. 2016. 6. 25.
트리(Tree) 1. 개요 트리는 그래프의 한 종류로써, 유닉스 및 리눅스의 파일 시스템과 검색 엔진 등에서 널리 사용되고 있는 자료구조이다. 트리는 컴퓨터공학의 모든 자료구조 중에서도 가장 많은 변형이 있으며, 대부분의 경우에 배열(array)보다 유연하고 연결 리스트(linked list)보다 효율적이다. [그림 1] 트리 구조의 활용 위의 [그림 1]과 같이 트리의 개념은 컴퓨터공학뿐만 아니라 생명과학, 게임 등 다양한 분야에서 이용되고 있다. 2. 수학적 정의 트리의 개념을 이해하기 위해서는 먼저 이산 수학(discrete mathematics)의 그래프(graph)를 이해할 필요가 있다. 그래프 $G$는 $G = (V, E)$와 같이 표현되며, $V$는 그래프 내의 어떠한 지점을 가리키는 vertex의 집합이고.. 2016. 6. 25.
이중 연결 리스트(Doubly Linked List) 1. 개요 일반적인 연결 리스트(linked list)의 노드들은 다음 노드를 가리키는 포인터만 포함하고 있기 때문에 한 방향으로만 탐색이 가능하다. 그러나 이중 연결 리스트(doubly linked list)의 노드는 아래의 그림과 같이 next와 prev라는 두 개의 포인터를 포함하고 있다. 노드의 next 포인터는 일반적인 연결 리스트와 같이 다음 노드를 가리키며, 이중 연결 리스트의 노드에 추가된 prev 포인터는 이전 노드를 가리킨다. 이중 연결 리스트의 가장 큰 장점은 일반적인 연결 리스트에 비해 효율적으로 탐색할 수 있다는 점이다. 예를 들어, 노드의 수가 $n$인 일반적인 연결 리스트에서는 $n-1$번째 노드에 접근하기 위해, 총 $n-2$번의 포인터 추적이 필요하다. 그러나 이중 연결 리.. 2016. 6. 18.
LinkedList.h Content: linked listLanguage: C++Official home page: noneDownload link: noneDownload file: 2016. 6. 17.
연결 리스트(Linked List) 1. 개요 선형 사상(sequential mapping)을 이용하는 배열, 큐와 같은 구조에서 insertion, deletion 연산은 매우 많은 비용이 소모된다. 아래의 그림은 배열에서 insertion 연산이 발생하는 경우, 연산이 실행되는 과정을 나타낸다. 선형 사상을 이용하는 배열과 같은 구조에서는 중간에 데이터를 추가하기 위해서는 해당 위치 다음에 저장된 모든 데이터를 일정 위치만큼씩 옮겨야한다. 이러한 shift 동작은 메모리 상에서도 많은 오버헤드가 발생하지만, 만약 하드디스크 상에서 shift 동작이 발생한다면 시스템이 감당할 수 없을 정도의 오버헤드가 발생할 수도 있다. 배열과 같은 선형 사상을 이용하는 구조의 또다른 문제점은 항상 고정된 크기를 갖기 때문에 예상한 것보다 데이터가 적게.. 2016. 6. 17.

티스토리툴바