https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 처음에는 상당히 애를 먹었던 문제 처음에 접근했던 방식은 (+) 연산자나 (-) 연산자는 (*) 연산자와 (/) 연산자보다 우선순위가 밀리기때문에 바로바로 출력하지 않고 뒤에 나오는 연산자를 기다리다가 출력을 하는 형식으로, (*)연산자와 (/)연산자는 우선순위는 높지만 뒤에 또 (*)연산자나 (/)연산자가 나오게 된다면 연속적으로 이루어지기에 역시 저장을 한 후 출력을 하는 형식으로, 괄호가..
분류 전체보기
https://www.acmicpc.net/problem/27725 27725번: 지수를 더하자 서로 다른 $N$개의 소수로 이루어진 집합 $P=\{p_{1}, p_{2}, \cdots, p_{N}\}$이 있다. 양의 정수 $i$에 대하여 $\frac{i}{p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times \cdots \times p_{N}^{a_{N}}}$의 값이 양의 정수가 되도록 하는 www.acmicpc.net 문제가 너무 어렵게 생겨서 지레 겁을 먹었던 문제 그런데 읽다보니 그냥 소인수분해를 이용한 문제 풀이라는 것을 알고 나름 간단하게 해결했다. 다만 문제 조건 K > n; ll k, y, ans=0; for(int i=0; i> x; v.push_back(x); } ci..
피보나치 수열을 M으로 나누었을 때, M으로 나눈 나머지가 일정한 주기를 이룬다는 것을 증명했다고 한다. 여기에는 여러가지 있는데, m > 2인 경우에 k(m)은 짝수이다. 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다. k(m) ≤ m2 - 1 k(2^n) = 3×2(n-1) k(5^n) = 4×5n k(2×5^n) = 6n n > 2라면, k(10^n) = 15×10(n-1) 이는 아래 링크에서 자세히 볼 수 있다. https://www.acmicpc.net/problem/9471 이를 이용해 N번째 피보나치 수열을 계산할 수가 있는데, N번째 피보나치 수열의 주기를 구해주고 이를 P라고 하면, dp[N] == dp[N%P]와 같으므로 N%P번째 피보나치 수열의 값을 구..
CCW 알고리즘은 두 선분이 어떤 방향을 이루고 있는지, 더 나아가 두 선분이 교차하는지 판단하는데 주로 쓰이는 알고리즘이다. 두 선분이 어느 방향으로 꺾여 있는지는 외적의 값을 통해 알아낼 수 있다. 외적의 값이 양수면 반시계 방향으로, 음수면 시계방향으로 꺾여 있다는 것을 의미하는데, 이는 오른손 법칙을 통해 쉽게 생각할 수 있다. 외적의 값이 양수라는 것은 엄지손가락이 위로 향했을 때에는나머지 네 손가락이 감기는 모습이 반시계 방향이고, 음수라는 것은 엄지손가락이 아래로 향했을 때에는 나머지 네 손가락이 시계방향으로 감기는 모습이다. 이를 통해 선분이 시계방향, 혹은 반시계 방향으로 꺾여있는지 알 수 있다. 간혹 외적 값이 0이 나올 수가 있는데, 이는 두 선분이 같은 평면상에 위치한다는 것이고, ..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 그야말로 빡구현.. 3시간 풀로 집중하고 노트 열심히 써가면서 구현했다 처음에는 별 것 없다고 생각했는데, 의외로 벽을 튕기고 나온 상어를 구현하기가 까다로웠다. 나머지 연산을 이용해서 상어의 위치를 업데이트 해주려 했으나, 상어가 양수 방향으로 이동할 때는 별 문제가 없었지만 상어가 음수 방향으로 이동할 때 과부하가 걸려서 엄청 헤맸던 문제 그리고 구현하고 보니까 같은 공간에..
