이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..
https://www.acmicpc.net/problem/27728 27728번: 개구리와 쿼리 $N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리들이 모여있다. 각 개구리들은 초기 위치 $\left(S_{x},S_{y}\right)$에서 배열의 오른쪽 끝$\left(X,N+1\right)$에 있는 육지에 도착해야 한 www.acmicpc.net 문제는 누가봐도 dp + 누적 합으로 해결하는 문제이다. 나도 처음에는 간단하다고 생각했는데, 막상 머릿속으로 시간을 계산해보니까 x좌표 N개, y좌표 N개, 개구리 Q마리 ->O(N^2*Q)가 걸렸다. 이는 당연히 시간초과이고, 시간을 줄일 방법을 찾아야했다. 먼저 dp[i][j]에 dp[i][n]까지 가기 위해 남은 시간을 저..
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시간 풀로 집중하고 노트 열심히 써가면서 구현했다 처음에는 별 것 없다고 생각했는데, 의외로 벽을 튕기고 나온 상어를 구현하기가 까다로웠다. 나머지 연산을 이용해서 상어의 위치를 업데이트 해주려 했으나, 상어가 양수 방향으로 이동할 때는 별 문제가 없었지만 상어가 음수 방향으로 이동할 때 과부하가 걸려서 엄청 헤맸던 문제 그리고 구현하고 보니까 같은 공간에..
N개의 동전을 가지고 K원을 만드는 경우의 수를 구하는 방법 N = 3, K = 10이며, 1원, 2원, 5원을 무한히 가지고있을때 동전을 사용하여 10원을 만드는 경우의 수를 구하는 문제이다. 단, 중복되는 경우는 제외해야한다 예를 들어, 3원을 만들 때 1원 + 2원 == 2원 + 1원인 경우를 의미한다. 처음에는 2차원 배열을 통해 구현했다 dp[N][K] 에서 N은 각 동전까지 사용했을 때 얻을 수 있는 K원의 경우의 수를 의미한다. dp[0][0] = 1 0원을 만드는 경우의 수는 아무 동전도 사용하지 않을 때라고 생각하면 1가지이다. 또한, 1원까지 사용했을 때 만들 수 있는 K원의 개수 역시 1가지이다. 이를 표로 정리하면 아래와 같다. N | K (i | j) 0 1 2 3 4 5 6 7 ..
