복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11444번 : '피보나치 수 6' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold IV에 해당하며, 문제를 풀이하기 위해 분할정복을 이용한 거듭제곱과 행렬 식 조작에 대한 이해가 필요합니다. 11444번 : 피보나치 수 6 N번째 피보나치 수를 구하되, N이 엄청나게 큰 경우 이를 구하는 문제입니다. O(N) 시간에는 해결이 불가능한 범위로 N을 주었으므로, O(log N) 시간 즉 빠른 거듭제곱을 반드시 활용해야 하는 문제입니다. 깔끔한 풀이를 위해 다른 분들의 풀이를 조금 읽어봤는데 유도 과정을 자세히 정리한 사람은 없는 것 같아 다음과 같이 따로 정리하여 첨부합니다. 점화식이 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11401번 : '이항 계수 3', 10830번 : '행렬 제곱' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 분할 정복(Divide and Conquer) 알고리즘에 대한 이해가 필요합니다. 11401번 : 이항 계수 3 N과 K가 400만 이하일 때 N C K를 구하는 문제입니다. 주어진 범위가 아주 크고 N!을 K!(N-K)!으로 나누어야하기 때문에 모듈로 연산을 해주기도 쉽지 않습니다. 따라서 여기서는 페르마의 소정리 및 빠른 거듭제곱 알고리즘을 사용하여 문제를 해결해주어야 합니다. [백준/BOJ] 13977번 : 이항 계수와 쿼리 (..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1992번 : '쿼드트리', 1780번 : '종이의 개수', 1629번 : '곱셈' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 분할 정복(Divide and Conquer) 방법에 대한 이해가 필요합니다. 1992번 : 쿼드트리 영상 면적을 4분할하여 모두 같은 데이터면 압축해서 표현하고, 그렇지 않으면 다시 4등분하는 과정을 반복하여 쿼드 트리 구조로 입력을 표현하는 문제입니다. 재귀함수를 활용하여 함수를 4개로 분할하여 돌리는 과정을 반복해주면 쉽게 해결할 수 있습니다. #include using namespace std; char ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 18258번 : '큐 2', 1021번 : '회전하는 큐', 5430번 : 'AC' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당하며, 문제를 풀이하기 위해 큐, 덱에 대한 이해가 필요합니다. 18258번 : 큐 2 큐를 직접 구현해보는 문제입니다. 이전의 강의글이었다면 큐를 직접 구현해보았겠지만, 여기서는 큐 라이브러리를 사용할 줄 안다고 가정하고, 바로 활용해보도록 하겠습니다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.t..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 4949번 : '균형잡힌 세상', 17298번 : '오큰수' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당하며 문제를 풀이하기 위해 스택에 대한 이해가 필요합니다. 4949번 : 균형잡힌 세상 대괄호와 소괄호가 적절히 열고 닫혔는지를 검사하는 문제입니다. 단순 괄호 여닫이만 따지면 안되고, 대괄호가 닫히기 전에 소괄호가 닫히거나, 소괄호가 닫히기 전에 대괄호가 닫히면 안됩니다. 따라서 스택을 써서 문제를 풀어주는 것이 가장 바람직합니다. #include using namespace std; int main() { ios_base::sync_with_std..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11051번 : '이항 계수 2', 9375번 : '패션왕 신해빈', 2004번 : '조합 0의 개수' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 조합론과 경우에 수에 대한 배경 지식이 있으면 좋습니다. 11051번 : 이항 계수 2 단순히 N Combination K를 구하는 문제입니다. 다만 N이 최대 1000까지 주어질 수 있으므로 10007로 나눈 나머지를 구해주면 되며, 시간 초과를 방지하기 위해 DP를 활용하여 계산해주어야 합니다. #include using namespace std; int comb[1005][1005] = ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2981번 : '검문', 3036번 : '링' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당하며, 문제를 풀이하기 위해 정수론 및 조합론에 대한 배경 지식이 있으면 좋습니다. 2981번 : 검문 N개의 수를 M으로 나누었을 때 나머지가 모두 같도록 하는 M들을 오름차순으로 출력하는 문제입니다. 모든 M에 대한 나머지를 일일이 구해보는 방법도 있겠지만 이 문제에서는 N이 10억 이하이므로 그렇게 되면 시간 초과에 걸리게 됩니다. 같은 나머지에 해당하는 b를 없애기 위해 수식을 조작하여 두 식을 빼보면, b를 없앨 수 있고 이 과정에서 공약수 M만이 남게 됩..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1019번 : '책 페이지' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 수학에 대한 기본 지식이 있으면 좋습니다. 1019번 : 책 페이지 1부터 N까지의 수들 중에서 각 자릿수에 나오는 0~9들의 개수를 구하는 문제입니다. 단순히 counting을 해주면 N의 범위가 10억 이하이기 때문에 시간초과가 발생하므로, 빠르게 계산해줄 수 있는 공식을 구해서 풀이해주어야 합니다. 이런 Counting 문제는 과정을 결국 그려서 생각해보아야 하기 때문에 어쩔 수 없이 위와 같이 적어보았습니다. 예를 들어 N = 283이라고 가정하고 생각해보겠습니다...

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17371번 : '이사' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 그리디 알고리즘과 기하학에 대한 기초적인 이해가 필요합니다. 17371번 : 이사 N개의 편의시설에 대한 좌표가 주어졌을 때, 가장 가까운 편의시설과 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표를 구하는 문제입니다. 가능한 좌표가 여러 가지일 수 있으므로, 그들 중 하나의 답을 출력하면 정답으로 인정될 수 있습니다. 이해를 돕기 위해 간단히 그림을 그려 설명해보면, 여러 개의 편의시설 중 가장 먼 편의시설의 거리가 최소인 편의시설의 위치를 집의 위치로 잡으면, 가장..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 16565번 : 'N포커' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 동적 프로그래밍(DP), 조합론, 포함과 배제의 원리에 대한 이해가 필요합니다. 16565번 : N포커 52장의 트럼프 카드에서 N장을 뽑았을 때 나올 수 있는 포카드 조합의 수를 구하는 문제입니다. 단순한 확률과 통계의 경우의 수 문제임을 알 수 있고, Combination을 어떻게 계산할 수 있을지만 생각해보면 쉽게 해결할 수 있습니다. 그래서 풀이를 깔끔하게 정리해보면, 위와 같이 됩니다. 포카드를 뽑는 경우의 수는 포카드를 1세트 이상 뽑는 경우의 수 - 2세트 이상 뽑..