알고리즘/백준 문제 풀이 (344) 썸네일형 리스트형 [C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи https://www.acmicpc.net/problem/11440https://www.acmicpc.net/problem/28749 25/03/04 25/03/09 두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다. 문제 접근 방식: 피보나치 수의 거듭 제곱의 합을 구하는 문제이다. Fn=Fn−1+Fn−2를 생각해보자. 제곱을 하면 다음과 같다. Fn2=(Fn−1+Fn−2)2=Fn−12+Fn−22+2Fn−1Fn−2 제곱 항은 공통이 되는데, 뒤에 붙은 2Fn−1Fn−2항이 공통이 되지 않.. [Python] 33756번 88888 https://www.acmicpc.net/problem/33756 25/04/05 실버 문제인데 재밌다고 느꼈던 문제라서 소개하고자 한다. 문제 접근 방식: 모든 자리수가 8인 수를 8-넘버라고 할 때, 어떤 수 N이 8개 이하의 8-넘버의 합으로 표현될 수 있는가를 물어보는 문제이다. 좀 생각하다가, 실버 3치고는 살짝 어려운데? 라고 생각이 들 때쯤 쉽게 아이디어가 떠올랐다. 생각을 해보면 모든 자리수가 8인 수는 모든 자리수가 1인 수 × 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=111 … 111(t)⏟n n개의 1로 구성된 t진수로 표현된 수 a가 주어진다고 하자.이때, 2u,3v가 각각 a를 나눈다고 하면 그때의 u와 v의 최댓값을 구하자. t와 n의 제한은 각각 109임을 생각해보면, 나이브하게 곱하면 숫자가 너무 커질 것이라는 생각이 들.. [C++] 17597번 Zipline https://www.acmicpc.net/problem/17597 25/01/12 간단한 기하학 문제다. 케이스를 나눠서 접근하면 쉽게 해결할 수 있다. 문제 접근 방식: 먼저 두 기둥을 잇는 케이블의 가장 짧은 길이는 두 기둥의 끝을 서로 이은 선분의 길이라는 사실은 쉽게 확인할 수 있다. 이제 케이블의 길이를 점점 늘린다고 해보자.문제에서 주어지는 그림이 케이블을 점점 늘린 상황이라고 가정해보자. 우리는 이 때의 경우에도 케이블 카가 지면으로부터 r만큼 위에 있어야 한다는 사실을 알고 있다. 근데 문제는 최저점을 찍었을 때의 상황이 언제인지를 모른다. 케이블 카가 x만큼 오른쪽으로 간 상황이라고 해보자. 그러면 케이블의 길이가 다음과 같다. $$l = \sqrt{(g-r)^2 + x^2}.. [C++] 2143번 두 배열의 합 https://www.acmicpc.net/problem/2143 25/01/11 이전에 북마크에 넣어두었다가 해결했던 문제다. 두 가지 해결 방법으로 해결할 수 있는데, 일단 나는 첫번째 해결 방법으로만 해결했고, 나머지 하나는 아이디어만 생각해두어서 적어보려고 한다. 문제 접근 방식: 부 배열의 합은 그냥 연속된 구간 합이다. 당연히 나이브하게 하면 시간초과가 날게 뻔하므로, 각각의 누적 합 배열을 AA,BB라고 하자. 이제 문제는 T가 주어질 때 AA[i]−AA[j]+BB[p]−BB[q]=T를 만족시키는 i,j,p,q를 구하는 경우의 수 문제로 바뀌게 되었다. 인덱스를 총 4개 뽑아야 되는데, 당연히 나이브하게 이걸 4개 뽑아서 조건을 만족시키는 것을 .. [C++] 32999번 Ribbon on the Christmas Present https://www.acmicpc.net/problem/32999 25/01/06 간단한 그리디+구현 문제다. 문제 접근 방식: 그니깐, 쉽게 생각하면 덧칠한다고 생각하면 된다. 한 번의 붓질로 같은 밝기를 쭉 칠할 수 있는데, 덧칠하면 덧칠할 수록 더 어두워지는 것이다. 근데, 붓질 횟수가 최소가 되려면, 한 번 쭉 붓질할 때 최대한 많은 칸을 칠하는 것이 이득일 것이다. 예를 들어 [50,100,50,50,100,50]이라면 맨 처음 50칠할 때 처음 칸부터 끝 칸까지 칠하고, 이후 2번째, 5번째 칸에 50만큼 더 덧칠하면 3번으로 완성할 수 있다. 이걸 코드로 구현해본다면, 기존 주어진 A가 있고, 그 배열의 0에 의해 끊어지지 않은 연속된 구간이 있다면 그 구간의 최.. 이전 1 2 3 4 ··· 43 다음 목록 더보기
