코딩 테스트 문제를 풀다 보면 overflow에 종종 마주합니다. 이 문제를 보아도 A, B, C 값이 최대 2,147,483, 647 자연수 값이 될 수 있어 일반적인 반복문을 통한 풀이로는 long long 타입을 붙여도 overflow 가 되는 것을 알 수 있습니다. 모듈러 연산은 이러한 문제의 해결 방법 중 하나가 될 수 있습니다. 모듈러 연산이란? 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산(mod) 정수론에서 모듈러 연산(modular arithmetic) 이란, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법입니다. c++ 에서 mod는 %로 표현됩니다 모듈러 연산 사칙 연산 덧셈, 뺄셈, 곱셈에 대해서 다음 식이 항상 성립합니다. (mod M 을 % M으로 표현..
코딩테스트
순열과 조합은 경우의 수를 기반으로 푸는 코딩 테스트 문제에 많이 활용됩니다. 여러가지 경우의 수를 생각해야 하는데 순서를 바꿔서 몇 개를 뽑는다.몇 개를 설정한다. 라고 했을 때는 순서가 상관 있으니 순열을 써야 하고, 순서를 바꾸지 않고 몇 개를 뽑는 게 중요하다. 설정하는게 중요하다 라는게 있다면 조합을 써야 합니다. 조합 조합에 '순서'는 없습니다. 순서 상관없이 오로지 몇명을 '다양하게' 뽑을 때 사용합니다. for 문 안에 재귀함수와 push/pop이 일어나는 과정만 이해하면 됩니다. 재귀함수를 통한 조합 구현 방법도 유용하지만 r이 작을 때에는 중첩 for문을 이용하는 게 더 효율적입니다. r이 10이거나 20이라면 재귀함수를 이용하는게 좋습니다. #include using namespace..
cnt 변수 값으로 메인 로직의 반복 횟수를 확인합니다. #include using namespace std; int n, cnt; int main() { cin >> n; int a = 0; for(int i=0; i < n ; i++){ for(int j=0 ; j < i ; j++){ a += i + j; cnt ++; } } cout
누적합은 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장하여 새로이 배열을 만들어 이를 활용하는 것을 말합니다. 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum 이 있지만, 코딩 테스트에서는 prefix sum만 나오니 prefix sum만 배우면 됩니다. 코드 적용하기 승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주면서 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해보자. 입력 > 수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. ..
python보다 메모리 관리가 좋은 c++도 종종 시간 초과 문제가 발생합니다. ios_base::sync_with_studio(false); cin_tie(NULL); cout_tie(NULL); 이를 해결하기 위해, 위 코드로 해결하는 사례를 종종 볼 수 있습니다. 이 코드가 어떻게 시간 초과 문제를 해결해 주는지 궁금했습니다. 참고로 아래의 방법은 정공법이 아닌 일종의 편법이므로 통하지 않을 수 있습니다. 1. ios_base::sync_with_studio(false); 헤더를 보면 C++의 표준 입출력은 C와 다르게 구현되어 있음을 알 수 있습니다. C++에서 입출력 작업을 할 때마다 C의 표준 입출력과 동기화 되도록 설정되어 있는데, 이 과정에서 딜레이가 발생합니다. 따라서, ios_base:..
