$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

알고리즘 문제풀이/Project Euler

(3)
Project Euler Problem 577 https://projecteuler.net/problem=577 난이도 : 20% 다음 그림처럼 한 변의 길이가 $n$ 인 정삼각형을 한 변이 $1$인 정삼각형 $n^2$ 개로 나눈 상황을 생각해 보자. 이때, 저 중 6개의 점을 이어서 만들 수 있는 정육각형의 개수를 $H(n)$ 이라고 하자. $\sum H(n)$ 을 구하는 문제. $H(3) = 1$이 주어졌는데, 이는 어렵지 않게 알 수 있다. 그림도 나와 있고. 그리고 나서도 $H(4) = 3$, $H(5) = 6$ 까지는 확실하고... 삼각수 $T_n$을 이용하면, 한 변의 길이가 1인 정육각형이 $T_{n-2}$ 개 있다는 것을 알 수 있다. 몇 개 더 그려 보기로 하자. $n = 6$ 케이스의 그림을 열심히 그려 보면, 한 변의 길이가 1인..
Project Euler Problem 587 와-! 시험 끝났다-! 종강하고 문제 다시 풀기 시작하려고 하는데... 빡센 문제도 풀어봐야겠지만, 역시 랭작하는 재미는 또 다른 얘기니까 Project Euler에서 쉬운 문제를 하나 먹고 지나가자. 엥간하면 PE는 15% 이상부터는 포스팅을 다 해두려고 한다. https://projecteuler.net/problem=587 난이도 : 20% 문제 설명 그림에서, 파란색 영역을 L-section이라고 하자. 그리고, 오른쪽 그림처럼 선을 그었을 때 잘리는 아래 부분(주황색)을 Concave triangle이라고 하자. 원이 한 개일 때는 그림에서 볼 수 있듯이, Concave Traingle이 L-section의 50% 넓이를 갖는다. 그러나, 원이 2개일 때는 위 그림처럼 넓이의 비율이 50%가 되..
Project Euler 포스팅 시작 + Problem 75 Project Euler 는 수학 계열의 고난도 알고리즘 (사실 알고리즘이랑 크게 상관 없는 문제도 있지만) 문제들을 연습할 수 있는 나름 좋은 문제 소스이다. 문제 유형이 PS랑 약간 다른데, 이런 식이다. PS (백준, Codeforces 등) : 1초 내에 $N$ 이하의 소수를 전부 찾는 코드를 짜라. $N \leq 100,000$. Project Euler (PE라고 줄이자) : 10만 1번째 소수는? 어쨌든 프로그래밍을 이용해서 해결하는 문제긴 하다. 난이도는 %로 표시되는데, 5%~10%문제 : 단순 구현 문제 (에라토스테네스의 체 구현 같은거), 적당한 생각으로 풀 수 있는 문제들이 있다. 15%~ : 펜과 종이를 꽤 많이 써야 하는 문제가 나오기 시작한다. 25%~ : 수식을 잘 정리하거나..