안 쓰던 블로그

알고리즘에서 나머지 연산은 연산의 값이 너무 커져서 자료형으로 담기 어려울 때, 각 연산마다 나머지 연산을 하여 자료형 안에 담기 위하여 사용한다 덧셈, 곱셈, 뺄셈은 성립하지만 나눗셈의 경우 성립하지 않는다. (나눗셈의 경우는 modular inverse를 구해야 한다) 그리고 주의할 점은 뺄셈의 경우 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 한 번 더하는 과정이 필요하다 $(A-B) mod M = ((A mod M) - (B mod M) + M) mod M$ 그 이유는 무엇일까? M을 더해도 전체 식에 영향은 없는 것인가? 나머지 연산에서 음수가 나오는 예시를 먼저 본다 $(6-5) mod 3 = 1 mod 3 = 1$ 이다 만약 $(6 mod 3-5 mod 3) mod..

수학 수학2에서는 수학1에서 다뤘던 내용을 기반으로 조금 더 응용하는 문제를 다뤄보겠습니다. 수학1 게시글(https://foxtrotin.tistory.com/95)을 보고 오면 도움이 되실 겁니다. 1. 나머지 연산 나머지 연산을 쓰는 유형에는 몇 가지가 있습니다. 나머지의 값이 필요할 때, 특정 수의 배수인지 판별, 짝수인지 홀수인지 판별, 몇 개의 수를 계속 돌리고 싶을 때, 너무 큰 수가 정답일 때 나머지 연산 후 정답을 출력할 때 등등.. 여기서는 몇 개의 수를 계속 돌리고 싶은 경우 어떻게 해야 하는지 알아보겠습니다. #include int main(){ int a[3] = { 1,2,3 }; for (int i = 0; i < 6; i++) { printf("%d ", a[i % 3]); ..

수학 입출력 글(https://foxtrotin.tistory.com/90)에서 알고리즘 문제풀이의 과정을 (1)문제를 읽고 (2)입력을 받아서 (3)계산하고 (4)결과를 출력한다 라고 했었습니다. 하지만 엄밀히 따지면 이 과정은 전체 과정 중 ‘구현’ 부분에 해당합니다. 그러면 ‘구현’ 이전에 해야 하는 과정은 또 뭐가 있을까요? 바로 문제를 해결할 방법을 생각하는 것입니다. 위에 네 단계에서는 (1)과 (2) 사이에 들어가는 과정이겠네요. 아무리 뛰어난 코딩 실력이 있어도 어떻게 풀지 모른다면 코딩 실력은 무의미해질 것입니다. 그래서 ‘문제 해결 능력’이 보통 문제 풀이에서 가장 중요한 능력으로 여겨집니다. 이번 주에는 우리가 잘 알고 있는 수학 몇 가지를 다루면서 문제를 어떻게 해결하는지, 어떻게 ..