사과하는 제라스

​모듈러 연산은 간단히 말하자면 나머지를 이용한 계산식이지만 여러 성질들이 있어 잘 사용하면 큰 수에 대한 연산 시 수고를 덜어준다. 다음은 모듈러 연산에 대한 증명 방법이다. 1. (A+B) % C = (A%C + B%C) % C A mod C = a B mod C = b 라고 하자. A = a + iC B = b + jC (A+B) % C = (a+b+(i+j)C) % C = (a+b) % C = (A mod C + B mod C) % C 2. (A-B) % C = (A%C - B%C) % C (1.과 같은 방식으로 증명 가능) 3. (A*B) % C = ((A%C) * (B%C)) % C A mod C = a B mod C = b 라고 하자. A = a + iC B = b + jC (A*B) % C..

[정렬 방법] 정렬에 앞서, 이 정렬을 이용하고자 할 때 조건은 정해진 범위 내의 숫자들만을 배열의 원소값으로 가져야 한다는 것이다. 이렇기에 나중에 타 정렬들과 비교했을 때 상대적으로 시간 복잡도가 작고 빠른 특성을 띤다. 먼저, 임의의 배열 arr에 정해진 범위의 숫자들(ex)0~20)을 넣는다. 이후 20 크기의 배열 c_arr을 만들고 arr을 for문을 돌리면서 원소값과 같은 index의 c_arr의 값을 1씩 증가시킨다. 이후 결과로 사용할 result 배열에 arr의 값들을 정렬시킬 것인데, arr의 가장 마지막 원소값(k)부터 시작해서 그 원소값과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result 배열의 원소값에 k를 넣는다. 이 과정을 거치면 사용된 c_arr의 원소값을 -1..

합병정렬은 분할 정복(Divide and Conquer) 알고리즘을 이용하여 푸는 방식이다. 1. 먼저, 주어진 배열을 절반의 크기로 나누는데 그 크기가 2짜리 배열이 될 때까지 계속해서 반복한다. 2. 이후, 길이가 2인 각 배열들 내에서 크기 순으로 정렬하고, 이웃한 2개의 배열을 합쳐서 또 정렬한다. 이를 모든 배열들이 합쳐져 원래 크기의 배열의 길이가 될 때까지 반복한다. 3. 이때, 정렬은 다음과 같은 방식으로 진행한다. ex) arr[0~3] arr[4~7]을 비교하여 정렬 시. arr[0]와 arr[4]를 비교하고 작은 수를 먼저 temp[0~7]라는 임의의 배열의 temp[0]에 넣는다. 그 수가 만약 arr[0]이었다면, 다음엔 arr[1]과 arr[4]를 비교한다. 이런 식으로, 두 배..

유클리드 호제법의 기능부터 살펴보자면 2개의 자연수에 대해서 최대공약수(GCD)를 구하고 이를 바탕으로 최소공배수(LCM)를 구할 수 있다. 두 수 A, B에 대해서 큰수 A를 작은 수 B로 나누는데 이때 나머지가 0이면 작은 수가 최대공약수이다. 만약 나눠떨어지지 않으면 B를 A/B의 나머지로 다시 나눈다. 이때 나눠 떨어지면 A/B의 나머지가 최대공약수가 된다. 이 과정을 나눠떨어질 때까지 반복을 하는데 간단히 보자면 두 수를 서로 나누는 과정을 나눠떨어질 때까지 반복하고 나눠떨어질 때 나누는 수가 최대공약수가 된다. 유클리드 호제법을 간단히 예시를 통해 풀이해보자면... 1. 다음과 같이 두 수가 주어진다. 231, 84 2. 이 두 수를 유클리드 호제법을 이용하면 231를 84로 나누면 나머지는 ..

[정렬 방법] 전체(n개의 값)에서 arr[1], arr[2], ..., arr[n-1] 순으로 기준값(key)으로 두고 바로 왼쪽 값부터 왼쪽에 있는 값들이 key보다 클 경우 한칸씩 오른쪽으로 옮긴다. 작을 경우엔 멈추고 비교대상이던 값의 오른쪽에 key값을 넣어준다. 이 과정을 arr[n-1]까지 진행하면 정렬된다. [정렬 과정] n 크기의 임의의 배열 arr에서 - 1번의 비교 arr[1] 값을 key값으로 둔 후, arr[0]와 비교해서 key값이 작으면 arr[1] = arr[0], arr[0] = key, key값이 크면 arr[1] = key - 최대 2번의 비교 arr[2] 값을 key값으로 둔 후, arr[1]와 비교해서 key값이 작으면 arr[2] = arr[1]로 한 후 (1), ..

[정렬 방법] 전체(n개의 값)에서 가장 왼쪽 이웃한 두 값부터 오른쪽 끝까지 비교하는데 왼>오이면 swap, 아닐 경우 continue한다. 이후 가장 max값을 픽스하고 나머지 값에 대해 이 과정을 진행,... 마지막으로 남은 두 값을 비교하고서 정렬하면 정렬이 완료된다. [정렬 과정] n 크기의 임의의 배열 arr에서(이때, 코드에서 key는 min과 max로 작성하였음.) - n-1번의 비교 arr[0]과 arr[1]을 비교 후 ( arr[0] > arr[1] )이면 arr[0]과 arr[1] swap, ( arr[0] arr[2] )이면 arr[1]과 arr[2] swap, ( arr[1] arr[n-1] )이면 arr[n-2]과 arr[n-1] swap, ( arr[n-2] arr[1] )이면..

정렬 방법 전체(n개의 값)에서 가장 큰 값을 맨 오른쪽 값과 바꾸고, 그 다음엔 맨 오른쪽 칸을 제외한 나머지 값들 중 가장 큰 값을 맨 오른쪽값과 바꾸고, ... 이렇게 바꾸는 과정을 진행하다가 마지막으로 2개가 남으면 그 둘을 비교 후 정렬하면 정렬이 완료된다. 정렬 과정 n 크기의 임의의 배열 arr에서(이때, 코드에서 key는 min과 max로 작성하였음.) - n-1번의 비교 arr[0]의 인덱스 값을 key값으로 둔 후, arr[key]와 arr[1] 비교 후 큰 값의 인덱스 값을 key에 넣고, arr[key]와 arr[2] 비교 후 큰 값의 인덱스 값을 key에 넣고, ... arr[key]와 arr[n-1] 비교 후 큰 값의 인덱스 값을 key에 넣는다. 그 후, 그 arr[key]와 ..

소수를 구하는 문제에서 가장 흔히, 쉽게 찾아낼 수 있는 방법으로는 에라토스테네스의 체가 있다. 에라토스테네스의 체를 코드에서 적용하는 방법을 설명하자면... 1. 먼저, 구하고자 하는 범위의 boolean형 배열을 만든다. (만약 구하고자 하는 범위가 1~150 중의 소수라면 arr[151]) 2. 이 arr 배열을 true나 false로 초기화시켜주고 그것을 소수라고 생각하자. (boolean형 배열은 정의만 해둔다면 내부 element들은 모두 false로 초기화되어 있다. 그러므로 이를 고려해서 false를 소수라고 두면 간편할 수 있다.) 3. 이때, false를 소수로 정의해두고(즉, 모든 수가 소수라고 설정을 해둔 후) arr[1]만 true(소수X)로 변경해준다.(1은 소수가 아니니까) 4..