" 범위를 입력받고, 해당 범위에 존재하는 서로소 쌍의 개수를 구하는 프로그램 작성
이때 (A, B)와 (B, A)는 같은 것으로 간주한다. "
위 문제에 대해 3가지의 방법으로 코드를 만들어보았다.
3가지 코드를 쉽게 비교하기 위해 '범위를 입력받고 프로그램 실행하고 결과를 출력하는 것'은
main함수에 포함시켜 main부분은 모두 같게 만들어준다.
실제 서로수의 개수를 구하는 코드는 coprime함수로 작성하고,
main함수에서 coprime 함수를 실행하기 위해 main함수 앞에 coprime함수를 먼저 선언해준다.
각각의 방법에서 추가로 만든 이 외의 함수 또한 main함수 앞에 모두 선언하고 시작한다.
▶ 서로소? 임의의 두 정수에 대해, 두 수의 공약수가 1만 존재하는 수
< main 함수 >
- 범위 입력받고 결과 출력
Algorithm 1.
2부터 (범위의 끝 값 /2)까지 모든 수 중에
두 정수 A, B가 동시에 나누어 떨어지는 수가 있다면 count하지 않고
두 정수 A, B가 동시에 나누어 떨어지는 수가 없다면 count++
< Result >
시간이 가장 오래 걸리는 반면, 두 수 모두 작은 수부터 큰 수까지 하나씩 비교해 나가기 때문에
출력되는 서로소 쌍의 순서도 작은 값부터 큰 값까지 차례로 출력됨
▶ 유클리드 호제법: 두 수의 최대공약수를 구하는 알고리즘
유클리드 호제법 예시 (나머지 연산 이용)
x=252, y=105
① z = x % y = 252 % 105 = 42(결과 x=105, y=42)
② z = x % y = 105 % 42= 21(결과 x=42, y=21)
③ z = x % y = 42 % 21= 0(결과 x=21, y=0)
=> 나머지가 0이면 *제수의 값이 최대공약수이다
( *제수: 나눗셈에서 어떤 수를 나누는 수 )
Algorithm 2.
'어떤 두 수의 최대공약수가 1이면 두 수는 공약수'임을 이용
정수 A는 범위의 시작부터 A++, 정수 B는 범위의 끝부터 B--
최대공약수가 1이면 count++, B가 A보다 작아지면 반복문 종료
< Result >
'유클리드 호제법 이용 + 범위를 반으로 나누어 비교'하였기 때문에 시간 단축
A는 작은 수부터 큰 수로 비교해 나가고 B는 큰 수부터 작은 수로 비교해나갔기 때문에
(A, B)에서 A의 값은 작은 수부터 큰 수로 출력되었고 B는 큰 수부터 작은 수로 출력된 것을 확인 가능
Algorithm 3.
값의 범위를 반으로 나누어서 작은 값의 범위와 큰 값의 범위를 비교
순환 호출을 이용해 각각의 부분을 다시 나누어서 서로 비교
최대공약수가 1이면 count ++
< Result >
'유클리드 호제법 이용 + 범위를 반으로 나누어가며 비교'하였기 때문에 시간 단축
범위를 반으로 나누어 서로소를 구하고, 각각의 조각을 또 반으로 나누어 구하는 과정을 반복했기 때문에
출력된 서로소 쌍의 순서는 뒤죽박죽임
실행 시간의 차이 - 효율성 문제
작은 범위에서 값을 구할 때는 시간의 차이가 크게 없지만,
구하고자 하는 범위가 커지면 실행 시간에 큰 차이가 생긴다.
범위가 커지면 출력되는 서로소가 너무 많기 때문에 서로소를 출력하는 부분은 제외하고 개수만 출력한다.
Algorithm 1.
Algorithm 2.
Algorithm 3.
Self - feedback
처음 내가 작성했던 코드는 algorithm 1이었는데,
풀어야 했던 문제인 1000부터 5000을 넣었을 때 그 값이 너무 크게 나와서 당연히 내가 틀린 줄 알고
다른 사람들에게 물어보고 다른 방법을 계속 찾아봤는데 알고 보니 그것도 맞는 코드였다..!
작은 숫자를 넣어서 테스트해보면 될 거라는 생각을 했더라면 이렇게까지 돌고 돌아서 풀진 않았을 텐데..
하지만 for문이 3번이나 중첩되면서 실행시간이 너무 오래 걸렸기 때문에
범위가 작을 때는 괜찮지만 범위가 커진다면 수정이 필요한 코드이긴 했다!
교수님이 알려주신 유클리드 호제법 알고리즘을 이용하면 그 시간을 단축할 수 있었다.
문제는 여기서 쉽게 풀 수 있는 걸 어렵게 생각하느라 돌고 돌아 생각해 낸 방법이 algorithm 3이었다.
결론부터 말하자면 algorithm 3 방법에서 굳이 divide를 순환 호출할 필요는 없었다..
처음에 풀었던 algorithm 1이 틀린 코드는 아니었다는 것을 알았다면
굳이 이렇게 재귀 함수를 통해서 풀 생각까지는 안 했을 텐데...
만일 숫자가 더 커졌을 때 algorithm 3이 algorithm 2보다 더 시간적 효율이 좋다면 더 좋은 코드이겠지만
2부터 10000까지의 범위를 입력했을 때 두 알고리즘의 실행 시간도 비슷했다.
아마도 두 알고리즘 다 for문을 2번 이용했다는 점과 비교하는 횟수가 똑같기 때문일 테지.
같은 맥락으로 만일 algorithm 1도 'for ( idx = 2; idx <= end/2 ; idx++)'를 빼고
cd(a, b)를 이용한다면 algorithm 2, 3의 실행시간을 가지게 된다.
이렇게 되면 algorithm 1도 마찬가지로 for문은 2개만 가지고 비교 횟수가 다른 함수들과 같아지기 때문이다.
비교 횟수가 같아진다는 것을 algorithm 2와 비교하여 예로 들면
아래와 같이 비교하는 방향이 다를 뿐 비교하는 횟수는 같다.
Algorithm 2
A= 100, B= 500 일 때
A= 100일 때 B= 500~101 비교
A= 101일 때 B= 500~102 비교
.
.
A= 300일 때 B= 500~301 비교
.
.
A= 498일 때 B= 500, 499 비교
A= 499일 때 B= 500 비교
반복문 종료
Algorithm 1
A= 100, B= 500 일 때
A= 100일 때 B= 101~500 비교
A= 101일 때 B= 103~500 비교
.
.
A= 300일 때 B= 301~500 비교
.
.
A= 498일 때 B= 499, 500 비교
A= 499일 때 B= 500 비교
반복문 종료
Algorithm 3 또한 divide를 순환 호출하지 않고 count_num 함수 안에 다음과 같이 작성한다면
정상적으로 실행되고 위의 algorithm 1, 3과 같은 실행 횟수를 가지게 될 것이다.
int mid=0;
for ( A= start; A <= mid; A++){
for ( B= mid+1; B <= end; B++){
if ( gcd(B, A) == 1 ){
cnt++;
}
}
return cnt;
}
결국 main함수뿐 아니라 coprime의 코드/ 실행 원리도 똑같고
두 정수의 범위를 어떻게 지정해주느냐만 달라지는 것이다.
이렇게 보면 크게 어렵지 않은 문제를 한참을 붙잡고 이렇게 돌고 돌아 답을 낸 것은
아직 코딩에 익숙하지 않아 실력이 부족하고 여러 노하우가 없기 때문이겠지
하지만 이번 문제 풀이를 통해서 새로운 것도 배우고 깨달았다!
1. 코드가 맞는지 확인해보고 싶을 때는, 쉽게 구할 수 있는 작은 값을 넣어서 테스트해보기
2. /* code */ -> 해당 코드 무시
3. algorithm 3의 경우 divide를 순환 호출하면서 count 하려면 main 앞에 전역 변수로 선언하여 모든 함수에서 유효하도록 한다
'IT 기타 > C programming' 카테고리의 다른 글
| C언어 코딩 연습 (0) | 2021.02.04 |
|---|
댓글