본문 바로가기

분류 전체보기184

Attention Is All you Need - Transformer IDEA BERT의 주요 네트워크로 사용되고 있는 Attention Trasformer이다. 논문 저자는 기존 RNN베이스 모델에 대해서 많은 회의감을 느끼는 것 같다. 그렇다면 이 논문에서 RNN의 어떤 점을 안좋게 보았으며, RNN의 단점을 어떻게 보완했을까? RNN의 단점 RNN의 구조를 보면 하나의 직렬로 이루어진 Network이다. 그래서 병렬처리가 되지 않는다. RNN은 오래 전에 학습된 데이터에 대해서는 유추하기 어렵다. long term dependencies RNN은 한방향에 대해서 밖에 유추 할 수 없다. Attention Trasformer의 장점 병렬처리가 가능하다. RNN처럼 직전의 input을 보는 유추하는 것이 아닌 전체 데이터에서 가장 가능성이 높은 것을 선택한다. 2번의 이.. 2020. 8. 30.
U-Net: Convolutional Networks for BiomedicalImage Segmentation 1. 아이디어 U-Net은 bio에서 segmentation할 때 많이 쓰이는 Network이다. 이전에 Network는 2가지 결점이 있었다고 얘기한다. 첫 번째, 각각의 patch들을 분리해서 학습하기 때문에 느리다. 두 번째, localization의 정확성과 context의 사용에 trade-off관계가 있다고 한다. 큰 patch들은 더 많은 max pooling이 필요하고 localization의 정확성을 줄이며, 작은 patch들은 사용 할 수 있는 context들이 너무 적다. 하지만, U-Net은 이러한 trade-off를 개선하여 localization의 정확성과 context사용을 모두 잡을 수 있다고 한다. 2. 알고 넘어가야 할 용어 및 구조 그림을 보고 왼쪽 Network와 오른.. 2020. 7. 18.
Introduction: A Simple Market Model (4) 1.6 Call and Put Options \( A(0) = 100, A(1) = 100, S(0) = 100 \)달러고 $$ S(1) = \cases { \rm 120\ \ with\ \ probability\ \ p, \cr \rm 60\ \ \ with\ \ probability\ \ 1-p} $$ 이다. Call Option은 time 1에 100$(즉, S(0), strike price or exercise price)의 가격으로 주식을 살 권리를 준다. 만약 strike price보다 떨어진다면, 이 옵션을 쓸모없게 된다. 만약 market price가 80$가 된다면, 누구도 이 권리를 수행하고 싶지 않을 것이다. 하지만, 주가가 120$보다 높아진다면, 100$에 사서 120$로 팔 수 .. 2019. 7. 6.
Introduction: A Simple Market Model (3) 1.4 Risk And Return A(0) = 100, A(1) = 110이라고 하자. 그러나 S(0) = 80 달러이며 $$ S(1) = \cases { \rm 100\ \ with\ \ probability\ \ 0.8, \cr \rm 60\ \ \ with\ \ probability\ \ 0.2} $$ 포트폴리오에 10000달러는 투자한다고 가정하자. x = 50만큼 사고, y = 60으로 고정하여 산다. 그렇다면 $$ V(0) = \cases { \rm 11,600\ \ \ \ \ if\ \ goes\ \ up, \cr \rm 9,600\ \ if\ \ goes\ \ down. } $$ 일때, $$ K_{A} = \cases { \rm 0.16\ \ \ \ \ if\ \ goes\ \ up, \.. 2019. 6. 10.
Introduction: A Simple Market Model(2) 1.2 No-Arbitage Principle 이 섹션에서 마켓에 대한 가장 근본적인 가정에 대해서 말할 것이다. 간략하게 초기투자금액이 없는 risk-free profits는 존재하지 않는다. 예를 들어 뉴욕의 딜러 A가 영국 파운드를 파운드당 $d_{A}=1.62$의 비율로 판다. 하지만 딜러B가 이 파운드를 $d_{B}=1.60$ 에 판다고 하면 $d_{A} - d_{B} = 0.02$차이가 생기게된다. 초기자본금이 없는 투자자는 이 차액만큼 이익을 얻을 수 있으며 딜러B에게는 short position이 딜러A에게는 long position이 동시에 발생하게 된다. 이럴 경우 환율을 조정하게 하여 이러한 기회를 없애버린다. 이러한 차이를 금지하는 것을 가정해야만 한다. Assuption 1.6 (.. 2019. 6. 9.
공유기 설치 - 2110번 풀이 방법 L이 증가 할수록 공유기의 개수를 감소한다. 만약 크기가 L이고 i번째에 공유기를 설치했다면 다음 공유기를 설치할 좌표(j)는 아래 공식과 같다. $$ X[i] + L 2019. 6. 9.
Introduction Design Principles 1. Program to an interface, not an implementation ( 구현이 아니라 interface를 프로그램하라! ) 이 디자인 원리는 구현 의존성을 굉장히 줄여준다. Clients는 interface를 참고하고 구현과는 독립적이다. 이것은 구현은 변화 없이 존재하는 clients마다 독립적으로 다양 할 수 있다는 것을 의미한다. 이것은 여기에서 다루는 일반적인 디자인 패턴의 주제이고 한 시스템이 구현의 관점이 아닌 interface의 관점으로 쓰여진다는 것을 보장한다. 결론적으로 clients는 interface에 의존한다. interface를 다양하게 하는 것은 존재하는 clients를 없앨 수 있다. 그러므로 interface는 신중하게 디.. 2019. 6. 8.
Introduction : A Simple Market Model 1.1 Basic Notions and Assumptions 2가지 자산을 트레이드한다고 가정하자. 하나는 risk-free이고 다른 하나는 risky security이다. risk-free는 은행 예치금이나 정부, 공공금융기관 또는 회사에서 발행한 채권이다. risk recurity는 형식적으로 어떤 주식이 될 것이다. 미래가격이 현재에 정해지지 않은 외화, 금, 상품이나 무형자산을 말한다. 지금 indroduction에서는 시간 크기를 2가지로 오늘은 t = 0, 미래의 어떤 시점, t = 1 나눈다. 더 정제되고 실제적인 상황은 나중 챕터에서 다르게 될 것이다. risky securities에서 투자자들이 가지고 있는 주식 점우율의 수로 명시되어 질 수 있다. 어떤 시점의 한 주의 가격을 S(t)라.. 2019. 6. 8.
최소값 찾기 - 11003번 해결방법 세그먼트 트리로 안 풀렸다.세그먼트 트리로는 정말 힘들다그래서 우선순위큐로 풀었다. 근데 이것도 겨우겨우 시간 통과했다. 우선순위큐는 최대값을 반환하므로 최소값을 찾기 위해 {-값, index}를 input으로 받는다. priority_queue pq; // { -값, index } 그리고 최솟값의 인덱스가 i - L + 1라면, pq.top().first를 출력하고 아니라면 해당 인덱스가 나올때까지 반복한다. 전체코드 #include #include using namespace std; priority_queue pq; int N, L, A; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> N >> L; for.. 2019. 5. 19.
탑 - 2493번 해결방법 stack을 이용하여 해결 할 수 있다. stack에는 index를 넣는다. if num[stack.top()] input보다 큰 값이 stack이 나올때 까지 pop한다. -> stack이 empty라면 0을 출력 -> 아니라면 stack.top()을 출력 -> stack에 index를 푸쉬한다. else -> st.top() 출력 -> stack에 index 출력 전체소스 #include #include using namespace std; int N, num[500001]; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); stack st; cin >> N; for (int i = 1; i > num[.. 2019. 5. 19.
나머지 합 - 10986번 해결방법 SUM(0 ~ i) % M의 개수를 받는다. i > M; while(N--) { cin >> a; sum += a; num[sum % M]++; } ll ans = num[0]; for (int i = 0; i < M; ++i) ans += (num[i] * (num[i] - 1)) / 2; cout 2019. 5. 19.
시계열 데이터란 무엇인가? 정의 시계열(time series) 데이터는 관측치가 시간적 순서를 가진 데이터이다. 이 데이터는 변수간의 상관성(correation)이 존재하는 데이터를 다루며, i.i.d, 연속(continous)하거나 불규칙적(irregular)데이터는 다루기 않는다. 시계열 데이터는 과거의 데이터를 통해서 현재의 움직임 그리고 미래를 예측하는데 사용된다. 일반적인 label데이터는 input과 label간의 상관관계를 다루는 반면에 시간에 따라 어떻게 움직이는 과거의 자료를 가지고 예측하게 된다. 데이터 옆의 데이터는 AirPassengers라는 데이터로 R에 기본적으로 내장되어있는 데이터이다. x축은 Time이고, Y축은 고객의 수를 의미하는 것으로 볼 수 있다. 여기서 label 데이터처럼 시간과 고객의 수 .. 2019. 5. 12.
타일채우기 - level 4 해결방법 dp를 이용하여 풀었다. $$ dp[N] = dp[N-1] + 2*dp[N-2] $$ N번째 경우의 수는 dp[N-1]번째에서 1 X 2 직사각형을 채울 경우와 dp[N-2]에서 2 X 1 직사각형과 2 X 2 직사각형을 채울 경우의 수를 합친것이다. 소스코드 #include using namespace std; int dp[1001]; int N, M; int main() { cin >> N >> M; dp[1] = 1; dp[2] = 3; for(int i = 3; i 2019. 5. 12.
3개의 숫자를 더하여 술래가 원하는 숫자를 만드세요 - level 2 해결 방법 문제 자체가 어렵다기 보다는 예외 케이스가 많아서 힘들었다. 일단 이 문제 반례를 찾으시는 분은 아래 케이스를 해보길 바랍니다. input 5 5 5 2 12 12 output 2 5 5 전체 소스 #include #include #include #include using namespace std; typedef long long ll; ll num[30], cnt, T, n; vector check; ll sum(vector v) { ll ret = 0; for(int i = 0; i < v.size(); ++i) ret += v[i]; return ret; } void dfs(vector v, int here, int c) { if(c == 3) { if(T == sum(v)) { for(.. 2019. 5. 11.
여행경로 - level 3 해결방법 dfs, bfs문제이고 솔직히 쉬운 문제였는데 오래걸렸다. 첫 번째는 문제에 대한 오해였다. 이 티켓을 사용해서 모든 도시를 다 방문해야만한다. 단순히 dfs를 통해서 사용하는 것이 아니라 실제 다 모든 도시 방문 && 모든 티켓 사용인지를 확인해줘야만 한다. 전체 소스 #include #include #include #include #include using namespace std; int T; vector v; vector dfs(string s, vector t, vector ans, int cnt) { ans.push_back(s); if (cnt == T) return ans; vector tmp; for (int i = 0; i < t.size(); ++i) { if (t[i][0].. 2019. 5. 8.
체육복 - level 2 해결방법 좀 더 신중히 고민하면 쉬운문제이다. 여벌 옷은 가지고 온 아이들은 수업에 참여 할 수 있다. 그래서 lost, reserve에서 같은 번호가 있다면 두 곳 모두에서 제거해주는 전처리가 필요하다. Time Complexity sort과정이 두번 있다. $$ O(2NlogN) $$ 전처리 과정은 reserve와 lost같은 것을 찾으므로 for문 2개로 돌아간다. $$ O(2N^{2}) $$ 마지막 계산 같다. $$ O(2N^{2}) $$ 따라서 $$ O(2NlogN + 4N^{2}) $$ 전체 소스 #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { sort(lost.be.. 2019. 5. 6.
단속카메라 - level 3 해결방법 왜 2점 밖에 안주는지 모르겠지만 쉽지 않았다. 아이디어 위의 그림은 예시를 그림으로 한 것이다. 그림을 보면 알 수 있듯이 겹치는 것들 중 진출 좌표(r[i][1])이 가장 작은 것이 가장 많이 겹치게 할 수 있다. 하지만 안 겹치는 선은 안 겹치는 선들 중 가장 처음 것을 기준으로 다시 몇개 겹칠 수 있는지 계산하면 된다. 알고리즘 r[i][0], r[i][1] 오름차순으로 정렬 변수 end : i번째까지 중 가장 작은 r[i][1] $$ end\ =\ min(end,\ r[i][1]) $$ 만약 end < r[i][1]이면 answer증가시키고, end = r[i][1]해준다. $$ end\ =\ r[i][1] $$ Time Compexity 정렬은 O(NlogN)이고, 업데이트는 O(N).. 2019. 5. 6.
1931번 - 회의실 배정 해결방벙 그리디 방법으로 해결하였다. 증명 회의실을 가장 많이 사용 할 수 있는 경우는 1. 끝나는 시간이 빠른 것, 2. 시작시간이 빠른 것 순으로 정렬 하고 가능한 시간의 개수를 탐색하면 된다. $$ END_{i} >= END_{j} \ (단, \ i는\ 가장\ 빨리\ 끝나는\ 회의, \ j는\ i제외한\ 회의, \ END는\ 이후\ 가능한\ 회의의\ 개수)$$ 그러므로 끝나는 회의의 수가 가장 빠르면 더 많은 회의를 할 수 있다. 전체 소스 #include #include #include using namespace std; int N; vector time; bool cmp(pair a, pair b) { if (a.second == b.second) return a.first < b.first;.. 2019. 5. 5.
줄 서는 방법 - level 3 해결방법 쉬운듯 어려운 문제였다. 해결방법은 머리 속으로 바로 생각났는데 처음 구현해보는 알고리즘이라 고생을 많이 했다. 충분히 프로그래머스를 이용하여 코딩테스트를 보는 회사에서 나올 수 있는 문제라고 여겨진다. k번째의 경우의 수를 구하는 문제이다. 만약 아래와 같이 next_permutation으로 푼다면 효율성 테스트를 통과하지 못해 효율적인 방법을 생각해내야 한다. do { k--; if(k == 0) break; } while(next_permutation(answer.begin(), answer.end())); factorial을 이용하여 문제를 푼다면 더 빠르게 풀 수 있다. 예를 들어 보자! n = 10이라고 가정한다. 만약 첫 번째 자리수가 바뀌기 위해서는 k > 9! 하므로, k < 9.. 2019. 5. 4.
6549번 - 히스토그램에서 가장 큰 직사각형 해결방법 라인 4번 문제와 흡사한 문제로 보인다. 이상하게 요즘 문제들이 쉬운듯 어려운 문제가 많이 보이는데 여러가지 자료구조를 안써보았기 때문이라고 생각한다. 무작위로 풀면서 사고력을 길러야 겠다. 내가 푼 방법은 2가지 이다. segment tree + conqure & divide방법과 stack방법이다. Segment Tree + conquare & divide Segment Tree는 각 구간에서 가장 높이가 낮은 index를 저장해준다. int init(int leftn, int rightn, int node) { if (leftn == rightn) return tree[node] = leftn; int mid = (leftn + rightn) / 2; int leftv = init(left.. 2019. 5. 2.
동전0 - 11047번 해결방법 알고리즘은 그리디를 사용하였다. 하지만 그리디를 사용해도 최적인지 증명과정이 필요하다. 증명 문제에서는 i개의 동전이 있고, 오름차순으로 주어진다. N을 금액이라고 할 때 동전이 N보다 작다면 항상 아래와 같다. $$ N / C_{i} K >> N; int ans = 0; for (int i = 0; i > c[i]; for (int i = K - 1; i >= 0; --i) if (N >= c[i]) { ans += N / c[i]; N -= (N / c[i] * c[i]); } cout 2019. 4. 29.
동물원 - 1309번 해결방법 O을 배치한 경우, X를 배치 하지 않은 경우라고 할 때 O X | X O | X X 3가지 경우의 수로 둘 수 있다. 그래서 dp를 N * 3개의 배열을 두고 시작하였다. int dp[100001][3] 점화식은 어떻게 될까? 점화식도 3가지로 나눌 수 있다. 만약 O X경우라면 이전의 경우의 수는 X O | X X가 되어야만 하기 때문에 아래와 같아진다. 나머지도 똑같은 방식으로 구해본다면 점화식을 구할 수 있다. $$ dp[i][0] = dp[i-1][1] + dp[i-1][2] $$ $$ dp[i][1] = dp[i-1][0] + dp[i-1][2] $$ $$ dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] $$ 전체코드 #include using n.. 2019. 4. 29.
3980번 - 선발명단 해결방법 bitmask dp로 해결하였다.dp를 2차원 배열로 (position, state)를 담을 수 있게 정의하였다. int dp[11][1 > t) % 2 == 0은 t라는 포지션이 0일 경우 아직 배정이 안됬으므로 배정을 해야한다는 조건이다. 더해서 포지션의 능력치가 0이 되면 안되기 때문에 s[p][t] != 0아닌 것도 포함해줘야 한다. sub를 둔 이유는 조건에 맞는 포지션이 없을 경우 -1를 리턴하는데, 이 경우는 포지션을 모두 배정하지 못한 경우의 수므로 제외시켜줘야 한다. if ((state >> t) % 2 == 0 && s[p][t] != 0) { int sub = solution(p + 1, state | 1 t) % 2 == 0 && s[p][t] != 0) { int sub .. 2019. 4. 20.
1102번 - 발전소 해결방법 해당 문제는 bitmask dp로 풀었다. bit가 켜지면 발전소가 켜진 것이고, bit가 꺼지면 발전소가 꺼진 것이다. bitmask dp로 푼 이유는 a번째 발전소가 j번째 가동시킬때와 b번째 발전소가 j번째 발전소를 가동시킬때가 다르기 때문이다. 문제를 풀 때 유의할 점은 0개 이상일 경우이다. 0개 이상일 경우 0을 리턴해야하지 -1를 리턴하게 하면 안된다. int dp[1 > i) % 2 == 1) cnt++; if (cnt >= T) return 0; T보다 작다면 비트가 0인 수를 찾은 다음 비트가 1인 수들 중에서 비용 값을 더해주고 0비트를 1로 바꿔 재귀시켜준다. for (int i = 0; i > i) % 2 == 0) { // 안켜진 발전.. 2019. 4. 19.
튜브의 소개팅 - level 4 해결방법 고려해야 변수는 y, x, d(거리)이다. 따라서 3차원 배열로 dp를 정의했다. ll dp[51][51][2510]; 점화식은 아래와 같이 된다. newy, newx는 다음번에 이동할 좌표를 의미한다. 다음 좌표는 해당 좌표의 +1이므로 d+1번째에 저장한다. 이전까지의 s + time_map[y][x]를 저장하면 된다. $$ dp[newy][newx][d+1] = min(dp[newy][newx][d+1], dp[y][x][d] + time_map[y][x]) $$ 당연히 수다시간은 제한이 있으므로 제한 시간 넘으면 못가게 해야 한다. if(dp[y][x][d] + time_map[y][x] 2019. 4. 14.
서울에서 경산까지 - level 4 해결방법 2차원 dp로 해결하였다. i는 도시, j는 시간을 의미한다. int dp[101][100010]; 점화식은 아래와 같다. k는 이전도시까지의 시간이다. 이전도시 시간과 + 현재도시 시간(걷는 방법과 자전거 2가지 모두)에 이전 도시까지 + k번째 기부금(걷는 방법과 자전거 2가지 모두)값의 넣는다. $$ dp[i][k + 현재도시 시간] = max(dp[i][k + 현재도시 시간], dp[i-1][k] + k번째 기부금) $$ 하지만, K(전체시간)을 넘으면 안되므로 예외처리를 해줘야 한다. if(k + travel[i][0] 2019. 4. 14.
GPS - level 4 해결방법 먼저 점화식을 세워보자! $$ dp[i][j] = min(dp[i][j], dp[i-1][here] + error) $$ 여기서 i는 시간을 의미하고, j는 각 노드를 의미한다. here은 j노드와 연결된 인접노드를 의미한다. dp[i][j]는 이전 시간 인접노드들의 에러들 중 최소를 + error(1 또는 0)을 의미한다. int dp[110][210]; // 시간과 노드로 구성된 dp int error = gps_log[i] == j ? 0 : 1; // gps_log[i]와 현재 노드가 같다면 0 아니면 1 초기화 과정이다. adj[i].clear()는 꼭 써주자! 아무래도 프로그래머스는 전역변수도 초기화가 안되는 모양이다. for(int i=0;i 2019. 4. 13.
코틀린 타입추론! 타입추론이란 무엇인가? 변수의 type을 생략 해도 컴파일러가 자동적으로 type을 유추해주는 방식이다. 코틀린에서 타입추론 할 시 유의할 점 fun main(args: Array) { val answer answer = 42; // 컴파일 오류 val answer2: Int // 타입 지정 answer2 = 42; val answer3 = 42; // 초기화 } 만약 변수를 초기화 하지 않는다면 타입추론을 할 수 없으므로 타입을 지정해주거나 초기화를 시켜줘야한다. 2019. 4. 12.
단체사진 찍기 - Level 4 해결방법 경우의 수를 구하는 문제이다. 다행히 n의 최대크기가 8이므로 8! = 40,320개로 모든 경우의수를 세면서 풀 수 있는 문제이다. 이 문제를 풀면서 next_permutation이라는 함수를 새로 배웠다. 그 동안 재귀나 반복으로 풀었는데, 한결 쉬워질거 같다. 먼저 vector에다가 8개의 수를 모두 넣었다. 그리고 pos배열을 하나 만들어 해당 알파벳의 index번호를 넣었다. vector f = {&#39;A&#39;, &#39;C&#39;, &#39;F&#39;, &#39;J&#39;, &#39;M&#39;, &#39;N&#39;, &#39;R&#39;,&#39;T&#39;}; int pos[26]; 그 다음 do ~ while문을 통해 나오는 다음 경우의 수를 통해 문제의 조건과 일.. 2019. 4. 6.
게임 맵 최단거리 - Level 4 해결방법 문제는 (0,0)부터 (n-1, m-1)까지 가는 거리 중 최소값을 구하는 것이다. 이런 문제는 항상 BFS가 답이다! DFS로 구현해도 되지만 DFS의 TimeComplexity가 너무 크기 때문에 시간초과가 된다. 다익스크라 알고리즘도 BFS를 쓰는 이유로 사용되고 있다! 삼성에서 이런 문제가 출제되기도 하는데 무조건 BFS다! 나는 struct로 (y,x)위치와 거리가 있는 구조체를 만들었다. struct node { int y, x, d; node(int yy, int xx, int dd) : y(yy), x(xx), d(dd) {} node() {} }; 그 다음 BFS로 구현하였고 먼저 (n - 1, m - 1)도착한 거리를 answer에 대입하고 break해주었다. BFS는 먼저 도.. 2019. 4. 6.

티스토리툴바