본문 바로가기

분류 전체보기

 (21)
[논문 읽기] Attention is all you need 1 Introduction 이전의 모델들은 hidden layer h(t)를 구하기 위해 input과 h(t-1)값을 참고하는데, 메모리 제약 등으로 인해 긴 문장들에게는 critical 하게 됨. attention mechanism을 이용하면 거리에 상관없이 영향을 구할 수 있음. 이 논문에서는 새로운 모델로 Transformer를 제안하는데, attention mechanism에 의존하여 input과 ouput의 global dependencies를 구해준다. 2. Background Extended Neural GPU [20], ByteNet [15] and ConvS2S -> 거리가 멀어지면 그 관계성을 찾기 힘들다. Self-attention : 서로 떨어져 있는 비슷한 문맥의 단어들을 비슷한 ..
[Day 4] 백준 9663 : N-queen 사실 3344번을 풀려고 했지만.. DFS로는 도저히 시간복잡도가 나오지 않는다. 그래서 다른 해법들을 찾아보니 케이스 by 케이스로 분류해서 비교해보는 문제였기 때문에 비교적 작은 값들로 시행하는 9663번을 선택하여 풀게 되었다. 해법 : DFS 이긴 한데 사실상 시간 제한이 10초이기 때문에 가능한 해법이라고 볼 수 있다. 그만큼 DFS 시간복잡도가 매우 나쁘다. 특히 이 문제에서는 O(n!)의 시간복잡도.. n 최대가 15여서 가능한 풀이라고 볼 수 있다. 어릴 때 이 문제를 처음 봤을 때에는 대각선 분류를 어떻게 해야하는지를 가지고 많은 시간을 고민했었던 것 같다. 그 학습의 결과인지 모르겠지만 대각선 분류는 행 번호(i)와 열 번호(j)를 이용하여 쉽게 할 수 있다. slash 방향의 대각선은..
[Day 4] 백준 7569 : 토마토 해법 : 3차원 bfs 정보올림피아드 2013 초등본선 3번 문제인데 이 당시에 본선에서 문제를 풀 때.. 그냥 배열로 3차원을 구현할 수 있을지 몰랐어서.. 당황했던 기억이 난다. 사실 그냥 2차원에서처럼 3차원에 적용해서 풀어주면 된다. 유의할 점은 for 문을 작성할 때 행, 열, 차원 순서가 아니라 차원, 열, 행 순서로 작성해야 한다는 점 정도 인듯. #include #include #include #include #include using namespace std; int n,m,h; int A[105][105][105]; int vt[105][105][105]; struct tuple2 { int x,y,z; int val; }; vector que; int r,f; int ans; int ..
[Day 3] 백준 2589 : 보물섬 해법 : bfs 최단 거리들 중에서 최대값을 찾아야하는데 map의 크기가 50*50이기 때문에 각각의 점들에 대해서 bfs를 각각 돌려도 시간복잡도가 충분히 나온다. #include #include #include #include using namespace std; int n,m; int M[55][55]; int vt[55][55]; int que[2505][3]; int r,f; int _max; int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0}; void bfs(int x,int y) { que[r][0]=x; que[r][1]=y; que[r++][2]=1; int i,j; for(i=0;i
Schedule 2021-01-21 11729 : 하노이 1753 : 최단경로 dijkstra 01-22 1931 : 회의실 배정 1937 : 욕심쟁이 판다 greedy 01-23(토) 3344 : N-queen 2589 : 보물섬 dfs / bfs 01-24(일) 7569: 토마토 dfs / bfs
[알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로는 하나의 시작점이 정해져있을 것, 그리고 음수 값을 가진 간선이 없을 것이다. Greedy 적인 방법으로 접근하기 때문에 음수 값의 간선이 존재하면 알고리즘이 성립하지 않는다. 자세한 설명들은 다른 블로그에 잘 나와있으니까.. 헷갈릴 만한 개념들만 되짚어보자. 진행 방향은 다음과 같다. 초기조건 : 일차원 Distance를 저장할 수 있는 배열(이하 Dist[]). 무한대에 비슷한 큰 값을 넣어준다. 시작 집합에 시작점을 넣어준다. 알고리즘 : 1. 시작집합과 연결된 노드 중 가장 거리가 짧은 노드(이하 a)..
[C++] STL heap 예제로 간단히 정리하기 아래는 heap djikstra인데 오름차순 정렬해주는 heap을 사용하였다. 자동으로 O(logn)에 정렬해주기 때문에 매우 유용하다. #include #include #include #include #include #define INF 99999999 using namespace std; int n,e; int s; struct tuple2 { int node; int val; }; struct pq_tuple { int idx; int dist; bool operator node.dist; } }; vector A[20005]; long long dist[20005]; int visited[200..
[Day 1] 백준 1753 : 최단경로 해법 : dijkstra 그런데 시간복잡도 문제 때문에 heap dijkstra로 작성해야 한다. 편이를 위해서 STL을 사용하였다. dijstra 설명 : [알고리즘] Dijkstra (tistory.com) [알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로 algorithm01.tistory.com #include #include #include #include #include #define INF 99999999 using namespace std; int n,e; int s; struct tuple2 { int node; ..
[Day 1] 백준 1937 : 욕심쟁이 판다 해법 : 이것도 greedy 음 사실 이것도 처음에 dfs로 뻘 코딩을 했다가 다시 생각해보았다. 사실 제목부터가... 물론 다른 의미지만 왜 greedy같은 형식으로 문제 푸는 것이 가능할까? 판다가 선택하는 기준에 방향성이 있기 때문인 것 같다. 시간복잡도와 내용을 고려해서 한 번 더 고민하는 것이 필요할듯.. #include #include #include #include using namespace std; int n; int A[505][505]; struct tuple2 { int x,y,val; }; tuple2 s[250005]; int _x[4]={1,-1,0,0}; int _y[4]={0,0,1,-1}; int m[505][505]; int _max; bool sf(tuple2 a,tu..
[C++] STL sort 시간복잡도 : O(n*logn) 추가해줘야할 헤더 : #include 사용법 : sort(A,A+n); (구조체, 배열) sort(A.begin(),A.end()); (vector 형식) #include #include #include using namespace std; int n; struct tuple2 { long long s,e; }; tuple2 A[100000+5]; bool sf(tuple2 a,tuple2 b) { if(a.e==b.e) { return a.s

티스토리툴바