연구실에서 좋은 기회로 해외 학회에 가게 되었다. 내가 가게 된 학회의 이름은 PLDI(Programming Language Design and Implementation)로, 프로그래밍 언어 분야에서 가장 중요한 학회 중 하나이다. 이번 2024년 리스트에 올라와 있는 논문을 간단히 살펴보고, 어떤 하위 분야가 있는지 간략하게 정리해보았다. 아래 하위 분야들은 서로 독립적이지 않으며, 한 논문에서 여러 내용을 포함하고 있을 수 있다. Probabilistic Programming (확률적 프로그래밍)확률 모델을 일반 프로그래밍 언어로 표현하기는 어렵다. 이러한 모델을 잘 표현하고 처리할 수 있기 위해서는 기존 프로그래밍 언어에 확률 분포로 부터의 샘플링 또는 데이터에 관측 결과에 따라 조건을 적용할 ..
이전 장에서 본 LeNet, AlexNet의 경우 컨볼루션 레이어가 3개, 5개밖에 되지 않았다. 최근의 신경망은 100개 이상의 컨볼루션 레이어를 가지고 있다. 이렇게 층을 깊게 한 Deep Neural Network를 사용하는 것을 Deep Learning이라고 한다. 8.1.3 깊게 하는 이유 층을 깊게 하는 이유가 무엇일까? 위와 같은 convolution 연산을 생각해보자. 5x5 합성곱 연산 1회는 3x3 합성곱 연산 2회로 대체 할 수 있다. 매개변수의 개수도 25개에서 16개로 줄어들며, 층을 더 깊게 할 수록 더 많이 줄일 수 있다. 같은 receptive field를 가지면서, 학습할 매개 변수의 개수는 줄어든다. 문제를 계층화 하여 각 층의 문제를 더욱 단순한 문제로 대체할 수 있다...
완전 탐색이란? 완전 탐색이란, 가능한 모든 경우의 수를 탐색하여 답을 구하는 기법을 의미한다. 연산마다 다르지만 C++기준 약 1억번의 연산에 대해 약 1초가 소요된다. 따라서 문제에서 요구하는 연산량이 많지 않고, 제한 시간이 목표 시간 내에 들어온다면 완전 탐색 기법을 사용해 풀이를 시도할 수 있다. 경우에 따라서 완전 탐색 기법을 최적화하여 풀이를 진행한다. (ex. Backtracking!) https://osmopolirt.tistory.com/47 선형 구조를 탐색하는 방법으로는 순차 탐색, 비선형 구조를 탐색하는 방법으로는 아래의 링크에 제시된 DFS, BFS 등이 있다. 백트래킹(Backtracking) 백트래킹(Backtracking)이란? 제약 조건(constraints)을 가진 최적..
이분 탐색이란? 정렬된 배열(or collection)에서 특정한 값의 원소를 찾을 때 사용하는 탐색 방법이다. 최적화 문제의 조건 Condition을 만족시키는 x의 최대 혹은 최소를 찾을 때 많이 사용한다. x의 값에 따라 Condition의 값이 두 구간 (T, T, ... , F, F)로 나뉠 때, T와 F가 바뀌는 경계를 이분 탐색으로 찾는다. O(logN)의 시간 복잡도를 가지기 때문에, 매우 큰 수에 대해 문제가 나오는 경우가 많다. 오버플로우 주의! 탐색 과정 low = 배열의 시작 인덱스, high = 배열의 끝 인덱스로 초기화 한다. mid = (low + high) / 2 Condition(mid)를 확인한 후, 해당 Condition이 바뀌는 지점이 있는 범위로 탐색을 좁힌다. Co..
백트래킹(Backtracking)이란? 제약 조건(constraints)을 가진 최적화 문제, 결정 문제를 푸는 방법 중 하나로 퇴각 검색이라고도 부른다. 완전 탐색(brute force)과 비슷하게 모든 경우의 수를 시도한다. 탐색 과정에서 현재 경로(해, solution)가 조건을 만족하지 못할 것 같다면 배제하고 이전 단계로 돌아간다. 해가 될 가능성이 있는 해를 유망하다(promising)고 한다. non-promising한 해를 제외하는 것이라고도 할 수 있으며, 이를 가지치기(pruning) 라고도 부른다. 일반적인 완전 탐색에 비해 탐색해야 하는 경우의 수가 줄어들게 된다. 일반적으로 DFS를 이용해 구현하며, 탐색 과정에서 제약 조건을 걸어 만약 해당 조건을 만족 시키지 못한다면 이전 No..
BFS(Breadth First Search)란? Tree 또는 graph를 탐색할 때 사용되는 탐색 알고리즘의 일종 임의의 node에서 시작하여 해당되는 분기에서 단계별로, 너비를 우선하여 탐색한다. Breadth First!) 즉, 시작 정점에서 인접한 정점들을 우선적으로 방문하는 방법이다. BFS의 특징 목표 상태까지의 정보(step, distance)를 알지 못하는 uninformed search의 일종이다. 시작 노드에서 가까운 노드를 우선적으로 탐색하므로, 주로 가중치가 없는 그래프에서 두 노드 사이의 최단 경로 또는 임의의 경로를 찾을 때 사용한다. DFS는 보통 재귀적으로 구현했지만, BFS는 주로 FIFO 자료구조인 Queue를 사용한다. Pseudo code Function bfs() ..
