{(l,n,m) | l * n * m = C(상수) }를 만족하는 집합을 구하고 싶은데요.
아래와 같은 너무 뻔한 방법 말고
for l in range(C): for n in range(C): for m in range(C): blah.. blah
좀 쌈박한 방법 있을까요? :p
예 제목과 그대로...
소인수 분해를 한후에 구하는게 빠를것이라고 생각됩니다.
일단 C의 모든 약수를 찾습니다. 그걸 c1, c2, c3, ... , cn 이라고 하죠.
C = ci*(C/Ci) = ci*A (i = 1~n)
그리고 A의 모든 약수를 찾습니다. 다시 이걸 a1, a2, ... , am이라고 하죠. A = aj*(A/aj) (j = 1~m)
p*q*r=C라고 하면, p = ci, q = aj, r = C/(p*q)죠.
따라서 약수 찾는 연산을 n+1번 하면 됩니다. 위의 조건을 만족하는 집합의 원소의 수는 n*m이 되겠죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
나누어떨어지는지 판단 함수를 int aaa( int a, int b ) 인풋:a 나눌대상 b나눌값 , 리턴: 나누어떨어지는 몫 -는실패
for를 돌리면서 aaa()가실패면 continue 성공이면 또 for 돌면서 몫으로 aaa()실행 성공이면 답을찾음(2중for)
큰숫자일수록 기존보다 루핑이 크게 줄어들지 않을까 예상해봅니다.
저는 그게 글 쓰신 분이 본문에 적은 "뻔한 방법"이라는 생각이 듭니다.
아닙니다. 다시 잘 보세요..아마 님이 제시한 방법보다 (성능적)조금나을겁니다.
저도 쓰고난후 님이 적은내용을 봤습니다만 그보단 이게 더 나을꺼라봅니다.
(물론 구현원리가 결과적으론 비슷하게 흘러갈수 있습니다.)
님이 약수를 찾는다는 로직을 생각해보시면 이해되실겁니다.
부연 설명해 드리자면..
나누어 떨어지는지 판단 함수 라는것은 "약수" 라는 의미와 같습니다. 1차로 for 문을 돌며 찾았으니..
님의 "일단 C의 모든 약수를 찾습니다. 그걸 c1, c2, c3, ... , cn 이라고 하죠." 부분과 같습니다.
성공이면 또 for 돌면서 몫으로 aaa()실행 이라고 했으니... 이부분은 또 그들의 약수를 찾는다는 뜻입니다.
이것은 님의 "그리고 A의 모든 약수를 찾습니다. 다시 이걸 a1, a2, ... , am이라고 하죠." 라는 부분에 해당하는 것입니다.
그리고 님은 다시한번 ."r = C/(p*q)죠."로 마지막 세번째 값을 구했습니다...
하지만 저는 이미 int aaa( int a, int b ) 의 결과값이 세번째값으로 구해져있습니다.
또한 약수를 찾는과정에서.. 님은 약수를 찾지만..저는 나누어 떨어지는지를 판단하는 함수 입니다. 결론은 약수를 찾는 로직보다는 (이업무?의)최소한의 필요한 로직만을 갖춘 함수입니다. (최소한 약수찾는 함수 보다는 같거나 작아질수 있겠죠?)
또한 마지막 부분에서도 3번째요소를 구하는 부분에서도 다시한번 연산을 해야하는 것과 이미구해져 있는 부분에서도 차이가납니다.
음...제가 select99님의 로직을 정확히 이해했는지 확인하기 위해 제가 이해한 대로 pseudo code를 써 보겠습니다.
aaa(a, b){ c=a%b if(c==0) return a/b else return -1 } for(i=0;i<C;i++){ n=aaa(C,i) if(n>0){ for(j=0;j<n;j++){ m=aaa(n,j) if(m>0) print(n, m, C/(n*m)) } } }
제가 이해한 바로는 위와 같고, 제가 제안한 방법 중 약수를 구하는 부분이 아예 내장되었다고 생각합니다. 말씀하신대로 더 효율적인 듯 싶네요.
제가 말씀드리고 싶은건, 처음에 글을 썼던 분이 "뻔한 방법"이라고 쓴 방법이 이 방법이 아닐까 하는 것입니다. 비효율적이라는 뜻도 아니고 유치하다는 뜻도 아니고 그냥 그 방법이라는 말입니다.
네..말의 의도는 알겠습니다.
작성하신 코드가 좀 잘못(for부분)되어 수정겸 C코드 함수는 매크로로 넣어봤어요.
#define aaa(a,b) ((a%b)? -1:a/b) for( i=0; i<C; i++ ) { n = aaa( C, i ); if( n > 0 ) for( j=0; j<n; j++ ) { m = aaa( n,j ); if( m>0 ) print( i, j, m ); } }
snowall 님의 방식이 루프하나는 빼줄수 있을것 같네요..
생각보다 느려서 알고리즘을 지웁니다... -_-;
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
...소인수 분해를 먼저해서 푸는게 낫지않을까요...
예 제목과 그대로...
소인수 분해를 한후에 구하는게 빠를것이라고 생각됩니다.
일단 C의 모든 약수를 찾습니다. 그걸 c1, c2,
일단 C의 모든 약수를 찾습니다. 그걸 c1, c2, c3, ... , cn 이라고 하죠.
C = ci*(C/Ci) = ci*A (i = 1~n)
그리고 A의 모든 약수를 찾습니다. 다시 이걸 a1, a2, ... , am이라고 하죠.
A = aj*(A/aj) (j = 1~m)
p*q*r=C라고 하면, p = ci, q = aj, r = C/(p*q)죠.
따라서 약수 찾는 연산을 n+1번 하면 됩니다. 위의 조건을 만족하는 집합의 원소의 수는 n*m이 되겠죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
나누어떨어지는지 판단 함수를 int aaa( int
나누어떨어지는지 판단 함수를
int aaa( int a, int b )
인풋:a 나눌대상 b나눌값 , 리턴: 나누어떨어지는 몫 -는실패
for를 돌리면서 aaa()가실패면 continue 성공이면 또 for 돌면서 몫으로 aaa()실행 성공이면 답을찾음(2중for)
큰숫자일수록 기존보다 루핑이 크게 줄어들지 않을까 예상해봅니다.
저는 그게 글 쓰신 분이 본문에 적은 "뻔한
저는 그게 글 쓰신 분이 본문에 적은 "뻔한 방법"이라는 생각이 듭니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
아닙니다. 다시 잘 보세요..아마 님이 제시한
아닙니다. 다시 잘 보세요..아마 님이 제시한 방법보다 (성능적)조금나을겁니다.
저도 쓰고난후 님이 적은내용을 봤습니다만 그보단 이게 더 나을꺼라봅니다.
(물론 구현원리가 결과적으론 비슷하게 흘러갈수 있습니다.)
님이 약수를 찾는다는 로직을 생각해보시면 이해되실겁니다.
부연 설명해 드리자면..나누어 떨어지는지 판단 함수
부연 설명해 드리자면..
나누어 떨어지는지 판단 함수 라는것은 "약수" 라는 의미와 같습니다.
1차로 for 문을 돌며 찾았으니..
님의 "일단 C의 모든 약수를 찾습니다. 그걸 c1, c2, c3, ... , cn 이라고 하죠."
부분과 같습니다.
성공이면 또 for 돌면서 몫으로 aaa()실행 이라고 했으니...
이부분은 또 그들의 약수를 찾는다는 뜻입니다.
이것은 님의 "그리고 A의 모든 약수를 찾습니다. 다시 이걸 a1, a2, ... , am이라고 하죠."
라는 부분에 해당하는 것입니다.
그리고 님은 다시한번 ."r = C/(p*q)죠."로 마지막 세번째 값을 구했습니다...
하지만 저는 이미 int aaa( int a, int b ) 의 결과값이 세번째값으로 구해져있습니다.
또한 약수를 찾는과정에서.. 님은 약수를 찾지만..저는 나누어 떨어지는지를 판단하는 함수 입니다.
결론은 약수를 찾는 로직보다는 (이업무?의)최소한의 필요한 로직만을 갖춘 함수입니다.
(최소한 약수찾는 함수 보다는 같거나 작아질수 있겠죠?)
또한 마지막 부분에서도 3번째요소를 구하는 부분에서도 다시한번 연산을 해야하는 것과 이미구해져 있는 부분에서도 차이가납니다.
음...제가 select99님의 로직을 정확히
음...제가 select99님의 로직을 정확히 이해했는지 확인하기 위해 제가 이해한 대로 pseudo code를 써 보겠습니다.
aaa(a, b){ c=a%b if(c==0) return a/b else return -1 } for(i=0;i<C;i++){ n=aaa(C,i) if(n>0){ for(j=0;j<n;j++){ m=aaa(n,j) if(m>0) print(n, m, C/(n*m)) } } }제가 이해한 바로는 위와 같고, 제가 제안한 방법 중 약수를 구하는 부분이 아예 내장되었다고 생각합니다. 말씀하신대로 더 효율적인 듯 싶네요.
제가 말씀드리고 싶은건, 처음에 글을 썼던 분이 "뻔한 방법"이라고 쓴 방법이 이 방법이 아닐까 하는 것입니다. 비효율적이라는 뜻도 아니고 유치하다는 뜻도 아니고 그냥 그 방법이라는 말입니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
네..말의 의도는 알겠습니다. 작성하신 코드가 좀 잘못되어
네..말의 의도는 알겠습니다.
작성하신 코드가 좀 잘못(for부분)되어 수정겸 C코드 함수는 매크로로 넣어봤어요.
#define aaa(a,b) ((a%b)? -1:a/b) for( i=0; i<C; i++ ) { n = aaa( C, i ); if( n > 0 ) for( j=0; j<n; j++ ) { m = aaa( n,j ); if( m>0 ) print( i, j, m ); } }snowall 님의 방식이 루프하나는 빼줄수 있을것
snowall 님의 방식이 루프하나는 빼줄수 있을것 같네요..
댓글을 달았는데...
생각보다 느려서 알고리즘을 지웁니다... -_-;
댓글 달기