알고리즘 (377) 썸네일형 리스트형 [C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи https://www.acmicpc.net/problem/11440https://www.acmicpc.net/problem/28749 25/03/04 25/03/09 두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다. 문제 접근 방식: 피보나치 수의 거듭 제곱의 합을 구하는 문제이다. $F_{n} = F_{n-1} + F_{n-2}$를 생각해보자. 제곱을 하면 다음과 같다. $$\begin{align}{F_{n}}^{2} &= (F_{n-1} + F_{n-2})^{2} \\ &= {F_{n-1}}^{2} + {F_{n-2}}^{2} + 2F_{n-1}F_{n-2}\end{align}$$ 제곱 항은 공통이 되는데, 뒤에 붙은 $2F_{n-1}F_{n-2}$항이 공통이 되지 않.. [Python] 33756번 88888 https://www.acmicpc.net/problem/33756 25/04/05 실버 문제인데 재밌다고 느꼈던 문제라서 소개하고자 한다. 문제 접근 방식: 모든 자리수가 8인 수를 8-넘버라고 할 때, 어떤 수 $N$이 8개 이하의 8-넘버의 합으로 표현될 수 있는가를 물어보는 문제이다. 좀 생각하다가, 실버 3치고는 살짝 어려운데? 라고 생각이 들 때쯤 쉽게 아이디어가 떠올랐다. 생각을 해보면 모든 자리수가 8인 수는 모든 자리수가 1인 수 $\times$ 8 의 형태를 가지고 있다. 즉, 8의 배수라는 소리고, 8의 배수끼리 더해도 8의 배수이기 때문에, 일단 $N$은 8의 배수여야만 할 것이다. $N$이 8의 배수라면, 8로 나눠보자. 그러면 나눈 수가 모든 자리수가 1인 수들의 합으로 표현.. [C++] 14267번 회사 문화 1 https://www.acmicpc.net/problem/14267 25/04/11 간단한 트리 문제다. 여러 방면으로 풀 수 있는 좋은 문제인 것 같아서 소개한다. 문제 접근 방식: 먼저 문제에서 요구하는 것을 한줄로 살펴보자. 각 노드의 값은 상위 노드에 있었던 값(정확히 말하면 직속 상사가 해당 노드(부하)에게 주었던 칭찬)들의 누적 합이다. 이를 여러 가지 방안으로 구현할 수 있는데, 기본적으로 누적합이기 때문에 DP라고 볼 수 있다. 근데 트리다. 따라서 넓게 보면 트리 DP다! 이를 구현하는 방안은 1. BFS, 2. DFS, 3. 기타 등등 DFS의 변형 근데 나는 BFS가 가장 먼저 떠올라서 BFS로 했다. BFS로 루트부터 탐색 시작해서, 노드랑 현재까지의 값(근데 이건 DP 배열에 .. [Python] 2533번 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 24/03/30 예전에 해결했던 문제인데, 복습하는 겸 글을 적어본다. 문제 접근 방식: 문제의 요구사항은 트리가 주어질 때 얼리 어답터의 수를 최소화하는 문제다. 얼리 어답터가 아닌 사람들은 주변의 모든 사람들이 얼리어답터인 경우에 아이디어를 수용한다. 목표는 모든 사람이 아이디어를 수용하도록 하고 싶을 때, 얼리 어답터의 수를 최소화하는 것이다. 전형적인 트리 DP로 해결할 수 있는데, 다음과 같이 DP테이블을 정의하자. $DP[i][0]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$번째 노드가 얼리 어답터가 아닐 때 서브 트리 전체의 최소 얼리 어답터 수$DP[i][1]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$.. [C++] 7118번 Ones https://www.acmicpc.net/problem/7118 25/02/26 예전에 문제를 보고 잘 안풀려서 북마크에 넣어두고 나중에 풀어봐야지 했던 문제인데, 오랜만에 다시 꺼내서 태그를 까고 해결했다. 지수승강 보조정리(LTE Lemma)의 기초를 배울 수 있었던 좋은 문제였다. 문제 접근 방식: 문제는 다음과 같다. $a = \underbrace{111 \ \dots \ 111_{(t)}}_{n}$ $n$개의 $1$로 구성된 $t$진수로 표현된 수 $a$가 주어진다고 하자.이때, $2^{u}, 3^{v}$가 각각 $a$를 나눈다고 하면 그때의 $u$와 $v$의 최댓값을 구하자. $t$와 $n$의 제한은 각각 $10^9$임을 생각해보면, 나이브하게 곱하면 숫자가 너무 커질 것이라는 생각이 들.. [C++] 5658번 [모의 SW 역량테스트] 보물상자 비밀번호 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo 25/02/07 16진수 변환을 곁들인 귀찮은 구현문제다. 문제 접근 방식: 주어진 숫자들이 16진수로 주어진 수들이기 때문에, 16진수로 주어진 수를 10진수로 변경하는 함수를 구현하는 것이 핵심이다. 이 문제에서 유의할 점은, 범위가 int범위를 넘어갈 수도 있다는 점이다. $N$이 최대 28까지이고, 그 말은 최악의 경우 FFFFFFF라는 16진수 수를 10진수로 변경해야하는 일이 있을 수 있다. 실제로 10진수로 변경해보면 int범위를 조금 넘어가기 때문에 long long으로 받아야 한다.(2억이랑 21억이랑 헷갈려서 잘못된 .. [C++] 3234번 준환이의 양팔저울 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw 25/02/06 가지치기를 "잘"해야 하는 백트래킹 문제다. 나이브하게 무지성으로 탐색하면 시간 초과의 늪에 빠지기 쉽다. 그래서 최적화를 두 번 해야하는데, 내가 풀었던 흐름대로 해설하고자 한다. 문제 접근 방식: 문제를 확인하면 특정 조건을 만족하는 순열의 수를 구하는 것이 목적이다. 또한 문제의 제한도 $N = 9$까지로 매우 작아서 백트래킹이 잘 동작할 것이라는 어떤 믿음이 존재할 것이다. 백트래킹 문제를 좀 풀어봤다면 나이브한 백트래킹 코드는 금방 짤 수 있을 것이라고 확신한다. 나이브한 코드는 다음과 같다.// SWEA323.. [C++] 1952번 [모의 SW 역량테스트] 수영장 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 25/02/06 전형적인 DP문제이다. 제한이 작아서 백트래킹으로도 해결할 수 있다. 문제 접근 방식: 문제의 요구 사항은 각 달의 이용횟수가 주어지고, 하루 이용권, 한 달 이용권, 세 달 이용권, 1년 이용권의 가격이 주어질 때 수영장을 이용할 수 있는 최소 비용을 구하는 것이다. 나는 다음과 같이 생각했다. 어차피 1달, 3달, 1년 이용권은 중간에 사용할 수 없다. 정확히 말하면 중간에 사용하는 것이 손해이다. 예를 들어, 내가 1월에 5번 이용해야 하는데 하루는 하루 이용권을 사서 이용하고, 나머지 4일은 1달 이용권으로 이용.. 이전 1 2 3 4 ··· 48 다음
