BigJeon Android 개발 블로그

오늘은 알고리즘 풀이를 하기 위해 알아야 하는 공식들 중 모듈러 연산, 페르마 소정리, 분할 정복이 3가지 공식에 대하여 알아보도록 하자.$해당 공식을 모두 적용해야 하는 문제는 백준 11401번 문제이다$ 1. 모듈러 연산의 분배법칙.정수의 합과 곱을 어떤 주어진 수의 나머지를 이용하여 정의하는 방법모듈러 연산 법칙이란 다음과 같은 공식을 의미한다.$A + B$ % p = $(A % p$ + $B % p$) % p 알고리즘 풀이를 하다보면 자주 보이는 문구가 있다.ex) 특정 제곱근의 값을 구하는데, 그 수가 너무 클 수 있으니 1000000으로 나눈 나머지를 출력하시오. 이러한 경우 우선적으로 떠올려야할 공식 중 하나이다. 해당 공식에 대한 증명 방식은 다른 블로그에 나와있지만, 그 수고로움 조차 덜..

오늘은 DP 알고리즘에 대하여 알아볼까 한다! 1. DP$Dynamic Programming$ 이란?DP는 동적 계획법이라고도 불리는 알고리즘이다.해당 알고리즘은 기본적으로'큰 문제를 작은 단위의 문제로 분할하여 작은 문제에 대한 결과값을 저장하여 점차 큰 문제를 해결해 나가는 알고리즘' 이다.즉 큰문제 -> 작은 단위의 문제로 분할 -> 작은 문제 결과값 저장 및 다음 단계 반복 풀이 -> 최종 큰 문제에 대한 결과 반환의 단계로 구성이 된다. 2. DP사용 목적DP를 사용해야 하는 상황은 무엇일까?일반적인 재귀함수$*재귀함수란 함수에서 자기 자신을 다시 호출해 특정 조건이 맞을때까지 같은 작업을 반복하는 알고리즘$ 사용 시 만약 반복적으로 항상 일정한 결과값이 나오는 작은 문제가 있다고 하더라고 해당..