배경 수 많은 노래들이 있었다. 그 중에서 가장 중독적인 노래는 무엇이었을까. 아마도 후크송이 뽑히지 않을까싶은데, 그 이유는 가사 반복이 많은 이유라고 추측한다. 그렇다면 노래의 "중독성", 엄밀히는 "가사가 반복된 정도"를 어떻게 수치로 계산할 수 있을까? 라는 고민에서 출발한 글이다. 정의부터 모호한 문제이지만 한번 계산해보고자 하던 여러 시도를 글로 남겨보고 납득할 수 있는 지 결과도 함께 기록한다. 단순하게 빈도 세기 처음에는 단순하게 노래마다 (공백으로 구분된) 동일한 구절이 반복되는 횟수를 세고, 가장 많이 반복된 횟수가 높은 노래가 더 반복을 많이 하는 노래라고 생각했다. 공백 단위로 구분한 이유는, 문장 단위로 자르기에는 "La La La" 와 "La La La La" 가 서로 다르게..

문제 이번 문제는 문제적남자 4화에 나온 뇌풀기문제이다. 6개의 9를 사용해서 100을 만드는 수식을 찾는 문제인데, DFS로 모든 경우의 수를 탐색하면 되는 전형적인 문제로 보인다. 숫자들 사이에 수식을 끼워 모든 경우의 수를 만들어보고, 파이썬의 eval 함수로 계산한 결과가 100 이 되는 경우만 세어보면 될 것 같다. 9와 사칙연산만 사용하기 6개의 9 사이마다 사칙연산을 끼워넣어서 100이 만들어지는 경우를 찾아본다. 4개의 연산자를 5개의 공간에 끼워넣으므로 경우의 수는 $4^5 = 1024$ 가지밖에 되지 않는다. 정답은 12개로 생각보다 많은데, 이건 순열이 달라서 세어진 것이고 조합으로 보면 단 하나이다. (정답 아래에 적음) 정답 9+9+9/9+9*9 = 100.0 9+9+9*9+9..

https://stackoverflow.com/questions/11103683/euler-angle-to-quaternion-then-quaternion-to-euler-angle Euler angle to Quaternion then Quaternion to euler angle I'm using lib glm (http://glm.g-truc.net/) for test quaternion but I've a problem; when I convert euler angle to quaternion then immediatly quaternion to euler angles, my result are totally different stackoverflow.com http://marc-b-reynold..

문득 그런 생각이 들었다. 사람들이 자신의 자동차 번호판을 고를 때, 외우기 쉬운 배열을 많이 고르지 않을까? 그럼, 숫자가 겹치면 외우기 쉬우니까 그런 차량이 많이 있으려나? 위는 근거 없는 추측일뿐이지만, 실제로 도로 위에서 숫자가 겹치는 번호판은 정말 많다. 그럼 정말로 도로 위의 차량 중에서 숫자가 겹치는 번호판을 만날 확률은 얼마나 될까? 먼저 번호판은 0 으로 시작하지 않으므로, 1000 부터 9999 까지 등장할 수 있다. 그럼 뒤 4자리(XX가 YYYY 중에서 YYYY)가 겹칠 확률만 계산해보자. def collide(n): a = {} for i in n: if i in a: return 1 a[i] = 1 return 0 cnt = 0 s = 0 for i in range(1000, 1..

링크: https://www.acmicpc.net/problem/13976 문제 2133번 문제와 같이 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이지만, N의 범위가 $10^{18}$ 이다. 풀이 이전에 작성한 2133번 문제의 2번째 풀이 방법과 같지만 그것을 빠르게 계산해야한다. 피보나치 수를 빠르게 구하는 방법과 마찬가지로, 행렬을 이용한 거듭 제곱 트릭을 사용하면 된다. 수열의 값은 같으므로, 편의상 OEIS A001835 수열 $f(n) = 4 \cdot f(n-1) - f(n-2)$ 을 사용하겠다. 이것을 행렬로 나타내면 아래와 같다. $$\begin{eqnarray} \left( \begin{array}{ccc} f_{n} \\ f_{n-1}..

링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 $f(n)$, 한 칸이 빈 3×N 벽을 채우는 경우를 $g(n)$ 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. $g(0)$와 $g(2)$는 타일을 채울 방법이 없으므로 $g(0) = g(2) = 0$ 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..

문제 소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다. New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다. UVa 136 - Ugly Numbers POJ 1338 - Ugly Numbers 정올 1318 - 못생긴 수 풀이 빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다. 파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다. 수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2..

https://www.acmicpc.net/problem/11012 문제 2차원 평면에서 점들의 위치가 주어지고, [left, right]×[bottom, top] 으로 그려지는 사각형 내에 있는 점의 개수를 쿼리마다 출력하는 문제이다. 이 문제는 PST(Persistent Segment Tree)로 해결할 수 있다. PST의 이해를 위해서는 Segment Tree를 먼저 알아야한다. 이 글에서는 자세한 설명은 생략하고, 도움이 될 만한 글로 대체한다. 사실 같은 내용을 이 문제에 대해서만 다시 정리하는 것이라 봐도 무방하다. 혼동이 있을 수 있지만, 이 글에서는(필자는) 세로/수직 방향을 $y$축으로 가로/수평 방향을 $x$축으로 한다. 즉, $(0,~0)$은 왼쪽 아래를 의미한다. y축을 ..