개발/알고리즘

문제 접근 입력으로 주어지는 n의 최대 크기는 100경이므로, $O(n)$으로는 절대 풀이하지 못한다. 피보나치 수열의 식 $F(n) = F(n-1) + F(n-2)$을 변형해서 접근하자. 일반항 $F(n) = \frac{1}{\sqrt{5}} \times (\frac{1+\sqrt{5}}{2})^2 - \frac{1}{\sqrt{5}} \times (\frac{1-\sqrt{5}}{2})^2$로 변형하여 바로 풀이하자. https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 코드 : 일반항으로 시도 - 부동 소수점 이슈로..

목적 : 가설을 세우고 수학적, 논리적으로 무결한 근거를 마련할 수 있는 문제 대응력 키우기. 목표 : Class 5 기본 문제를 풀이하며 증명하는 과정을 기록하기. 전략 : 문제를 해결했다는 결과에 집중하기보다는 접근 과정에 집중하며 기록한다. 주의점 재미있게 하자. 습관적으로 강박을 갖는 경향이 있는데 이렇게 되면 단기적으로 어떤 성과를 거둘 수는 있어도 장기적인 관점에서는 손해다. 결정적으로 금세 지루해지고 재미가 없어진다. 동기 작년에 2023 알고리즘 레콩키스타라는 프로젝트를 시작하고 일주일만에 흐지부지됐던 경험이 있다. 이 프로젝트에 올해 다시 한번 도전해보려고 한다. 단, 조건을 조금 바꿔서! 이전 알고리즘 레콩키스타의 목적은 PS 감각의 회복(쥐뿔도 없지만..)이었으며, 목표는 Class ..

문제 접근 연산자를 저장하는 stack을 만들자. 표기식의 우선 순위를 고려해서 stack와 상호 작용하자. 괄호 표기식이 최상위, 곱셈과 나눗셈 표기식이 그 다음, 덧셈과 뺄셈이 최하위다. 따라서, 표기식을 stack에 push하기 전에 stack의 top에 해당하는 표기식의 우선 순위가 push하려는 표기식의 우선 순위보다 상위에 있거나 같다면, 우선 순위가 낮은 표기식이 top이 될 때까지 출력하고 pop한다. 예 : 괄호는 곱셈보다 우선 순위가 높기에 stack에 push해도 되기만, 덧셈은 곱셈보다 우선 순위가 낮기에 stack된 계산인 곱셈을 출력 및 pop한 뒤에 더 이상 덧셈에 우선해 처리할 계산이 없을 때 push한다. https://www.acmicpc.net/problem/1918 1..

문제 접근 BFS로 풀이한다. 최단 거리는 별다른 특이사항이 없다면 BFS로 푸는 게 깔끔하다. 이 문제 역시 BFS로 단순하게 해결할 수 있는 문제였다. 목표 지점에서부터 탐색한다. 이번에는 시작점과 목표점이 N:1이어서 쉽게 목표점부터 탐색하자고 생각할 수 있었다. 만약 1:1이라고 하더라도 역으로 탐색을 하는 게 이로운 상황이 있으니 잘 살펴보고 설정하도록 하자. https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.ac..

문제 접근 값을 입력받을 때 합 배열을 만들어 간단하게 부분 합을 구하자. 별 다른 특이 사항은 없다. 입력받을 때 각 인덱스까지의 합을 저장하는 배열을 만들고, 추후 끝에서 시작을 빼는 방식으로 사이의 부분 합을 구할 수 있다. https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 코드 #include #include using namespace std; int main(void) { ios_base::sync_with..

문제 접근 Factorial 계산 과정에서 필요 없는 것들은 날리자. N이 500이면 오버플로우가 생길 것 같아서 계산 과정에서 날릴 수 있는 것들은 날리기로 했다. 이에 뒷자리가 0인 경우, 어떤 수와 곱해도 0은 유지된다는 특성으로부터 계산 과정의 뒷자리에 0이 올 때마다 자릿수를 내리고, 답에 1을 추가하는 방식으로 구현했다. 문제 : 500이면 0을 제외해도 자릿수 자체가 크기 때문에 여전히 오버플로우가 발생한다. 10을 만드는 수를 필터링해서 아예 곱셈을 하지 않아도 되게 나머지를 다 날리자. 중학교 때쯤 배웠던 지수 곱셈이 생각났다. 1부터 N까지의 어떤 수든 분해하면 $x^{a}\times y^{b}\times z^{c}$ 와 같은 형태로 표현된다. 이때 10을 만드는 수는 2와 5이므로, ..

문제 접근 기본 BFS에서 평범한 좌표 이동 대신에 수식 계산을 대입한 문제로 생각하자. 기본적인 BFS 문제는 주변 좌표의 값을 탐색하는 문제다. 이번 문제는 좌표 탐색 대신에 수식이 주어졌기 때문에, 수를 vertex로, 수식 계산을 하나의 edge로 생각하며 문제를 풀었다. https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 코드 #include #include #include #include using namespace s..

문제 접근 조건을 잘 확인하자. 문제 자체는 BFS로 최단 거리를 구하는 간단한 문제다. 시작 칸과 도착 칸도 최단 거리에 포함되는지, 입력은 어떤 방식으로 되는지 등의 조건을 잘 확인하기만 하자. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 코드 #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); c..