https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 제목 그대로 CCW 알고리즘을 이용하여 푸는 문제이다. CCW 알고리즘은 벡터의 외적을 활용해 푸는 알고리즘으로, 학창시절에 배웠던 신발끈 공식을 적용하면 된다. 선분 AB를 u라 하고, AC를 v라 할 때, 위와 같은 외적 공식을 적용할 수 있다. θ 가 180 < θ < 360 이면 시계방향이고, sin θ 값이 음수이다..
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 다른 사람들의 풀이보다 시간복잡도가 뒤쳐지지만, TLE도 아니고 스스로 풀었으니까 만족한다 ㅋㅎ 우선 입력범위에 해당 하는 소수들은 모조리 골라준다. 그리고 bfs를 시작하여, 현재 기준이 되는 소수와 단 한자리만 다르면서 아직 방문하지 않은 '소수'를 큐에 넣고 탐색을 이어간다. 한마디로 소수 판정 + bfs 이다. import sys from collections import deque #sys.set..
목차 0. Abstract 1. Introduction 2. Encoder and Decoder Stacks 3. Attention 4. Why Self-Attention 5. Result Abstract 등장 배경? 이전 방식들 ( RNN, LSTM, GRU ) 등등은 인코더-디코더 기반의 sequential한 모델입니다. (sequential 하다는 것은 모델이 입력을 순차적으로 받고, 연산 또한 이전 결과의 입력을 받아야 한다는 특징을 가지는 것을 의미) 즉, 내부에 RNN, CNN을 사용하는 구조입니다. 연구진들은 RNN, CNN 없이 오직 ‘Attention’ 기법만을 이용한 Transformer 제안하였습니다. 이것이 바로 이번에 다룰 내용입니다. Transformer의 이점으로는 기존 모델 ..
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 재귀 순회 문제이다. 이런 문제를 몇번 풀어보긴 했지만, 익숙하지 않아서 꽤 애를 먹었다. 알고리즘은 뭔가 답답할 땐 항상 그림을 그리며 직접 손으로 따라가보자! --설명-- 1. (0,8)을 넘겨준다 2. mid는 end+1로 설정하고, ( 아래 for문에서 mid값이 갱신되지 않는다면, end를 그대로 넘겨야 하는데 넘길 때 -1을 해주므로 ) 3. start를 pivot 삼..
텝스 첫 시험을 보고 왔다 다행히도 시험장이 모교라서 엄청 가까웠고, 익숙했다. 하지만 문제는 그게 아닌 점,,, 컨설텝스의 노란색 텝스의 정석 교재를 한바퀴 돌리고, 해커스 텝스 리딩, 리스닝을 공부하던 중에 시험을 본 것이다. 어차피 여러 번 봐야할 것 같아서 ㅋㅋ 맛만 보고 오자는 느낌으로 가볍게 보았다. 모의고사는 250~270점 정도 나왔었다. 327점만 넘기면 되기 때문에 공부도 더 하고 시험도 더 볼 생각이지만, 그래도 사람 마음이라는게 이왕 본 시험에서 한번에 327이 넘는 점수가 나오길 감히 바란다.. 그냥 느낌이지만, 왠지 모르게 독해를 잘 푼 것 같다. 독해 150 청해 110 단어 30 문법 40 해서 330점 나왔으면 좋겠다 ㅎㅎ 청해는 아무리 듣고 들어도 너무 어려운 것.. 수능..
https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 가장 기본적인 최장 거리 거리 수열 문제이다. O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다 현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다. import sys #from collections import deque #import heapq #sys.setrecursion..
