Joonas' Note

문제 이번 문제는 문제적남자 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://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..

성능 테스트 코드를 작성하다가, 평균을 실시간으로 구하는 방법을 글로 정리해볼까 한다. (직관으로) 어렸을 적에 이게 당연한 줄 알았다. 근데 몇개의 반례를 찾고는 틀렸다고 생각했다. 그런데 학부 시절에 교수님께서 '그런 것이 있다'고 말씀해주셨다. 이름은 Moving average이고, 한국어로는 모르겠다. 나는 데이터 범위에 따라 점진적으로 평균을 구해간다는 느낌으로 점진적 평균 또는 실시간 평균으로 부르고 싶지만, 통계쪽에서 "이동 평균"으로 부르는 모양이다. 아무튼, 본디 평균을 구하는 식은 전체 합 \(S_n\)에서 데이터의 개수 \(n\)만큼 나눈 \(S_{n} / n\) 이다.그럼 이것이 뭐가 문제인가?\(n\)개를 전부 더하거나 카운팅 하지 않으면 평균을 구할 수 없다. 어떤 실험 \(X_..

링크: https://www.acmicpc.net/problem/1699문제주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다. 문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다. 백준 온라인 저지에 문제로도 등장했다. BOJ 3933 - 라그랑주의 네 제곱수 정리 요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다. \(x^a + y^b + z^c + w^d = N\) 에서 \(a,~b,~c,~d\) 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 \(a,~b,~c\)를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다. 즉, 3중첩 반복문으로 해결 가능하다.코드

링크: https://www.acmicpc.net/problem/11447문제문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에, 마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다. 처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.풀이다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다. 이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점..

링크: https://www.acmicpc.net/problem/15719문제자료형의 비트를 이용하여 배열을 압축하여 사용하는 방법과, 수학으로 푸는 2가지 풀이를 소개하려 한다.풀이 1 (비트)표현할 정수의 범위는 [0, 10000000]이다. 그리고 필요한 정보는 각 숫자들이 사용되었는가/아닌가 이다.사용되지 않았다면 0, 사용되었다면 1로 표현한다면 숫자 하나의 사용 여부를 하나의 비트로 관리할 수 있다. 즉, 32비트 정수 하나에 32개의 수의 상태를 담을 수 있다.그럼 배열의 크기는 \(\lceil 10~000~000 / 32 \rceil = 312~500\)만큼 필요하다. 코드는 훨씬 간단하다.코드 풀이 2 (수학)1부터 \(n-1\)까지의 수가 골고루 등장한다. 등장한 모든 수의 합을 \(S..

링크: https://www.acmicpc.net/problem/12755 2016 전북대학교 프로그래밍 경진대회 A번 비슷한 문제로는 BOJ 1748 - 수 이어 쓰기 1이 있는데, 거기에 조건을 하나 더 얹었다. 앞에서부터 \(N\)번째 자리에 있는 수를 출력하는 것이다. 1부터 \(N\)까지 전부 확인하는 건 시간적으로도 메모리적으로도 무리다. 따라서 탐색 범위를 좁힐 필요가 있는데 이 문제에서는 자리수별로 인덱스를 자르면 좀 낫다. 1자리 수는 1부터 9까지 9개가 있으며, 전부 이어 붙이면 길이가 9이다.2자리 수는 10부터 99까지 90(=99-10+1)개가 있으며, 전부 이어 붙이면 길이가 180(=90*2)이다.3자리 수는 100부터 999까지 900(=999-100+1)개가 있으며, 전부..

[이전 블로그에서 글 옮김] https://www.acmicpc.net/problem/2022 https://uva.onlinejudge.org/...&problem=1507 \(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다. 피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다. 우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다. \( \begin{cases} A = \sqrt{a^2 - k^2} \\ B = \sqrt{b^2 - k^2} \end{cases} \) \( \begin{cases} f(x) = \frac{B}{k}x..