코드저장소

이번 문제는 A,B,C 세가지 수가 주어지면 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제이다. 입력의 최대값은 2,147,483,647로 큰 값을 Long의 범위 안에서 어떻게 처리 할지가 핵심이었다. 그럼 어떻게 풀지 살펴보자. 수학적 지식이 필요하다 이번 문제를 풀기 위해선 수학적 지식이 조금 필요한데, 첫째는 지수 법칙이고 두번째는 모듈러 성질이다. 1. 지수 법칙 2. 모듈러 성질 이 2가지를 이용하여서 문제를 해결한다. 그럼 위의 공식과 분할 정복이 문제와 무슨 연관이 있느냐? 위 문제를 그냥 A*B %C로 푸는 경우 입력값이 최대인 2,147,483,647인 경우 Long의 범위를 넘어가게 된다. 따라서 지수를 보다 작은 값으로 나눠 줄 필요가 있는데, 이를 위하여 분할 정복과 지수..

이번 문제는 2차원 행렬에 담긴 데이터를 판단하여 0,1,-1로 분류하여 같지 않으면 9등분 하고 맞으면 갯수를 구하는 문제이다. 문제 자체가 크게 어렵지 않아 금방 풀어낼 수 있었다. 그럼 어떻게 풀었는지 살펴보자. 분할 정복이란? 분할 정복이란 큰 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체의 답을 계산하는 알고리즘이다. 언뜻 봐서는 재귀호출과 비슷해 보이지만, 일반 재귀 호출과 분할 정복의 가장 큰 차이는 일반 재귀 호출은 문제를 한 조각과 나머지 전체로 나눈다면 분할 정복은 문제를 거의 같은 크기의 부분 문제로 나눈다는 점이다. 분할 정복은 3가지 과정으로 이루어 지는데 1. 문제를 더 작은 문제로 분할하는 과정 2. 각 문제에 대한 답을..