BigJeon Android 개발 블로그

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

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