간단해 보이지만..사실은 정말 어려운 문제에 봉착했습니다. C언어..

ldknick의 이미지

정말 어려운 문제에 봉착했습니다.

한번 풀어 보세요.. 아무리 생각해봐도 해결이 안나네요.

주어진 인덱스 값에 따라서 문자열을 얻어 오는 루틴을 작성중인데...

예를 들어 편의상, 문자셋이 "0", "1", "2" 라고 3개가 주어졌을때, 중복 및 반복을 허용해서 인덱스 번째 위치를 찾는 겁니다.

3번째라고 한다면 "0 0" 을 가져 오는 거고... 6번째가 "1 0" 입니다.

뭐, 제공되는 문자셋의 개수는 변하겠지만.. 어째튼...

중복 조합인줄 알았는데, 보니깐.. 그것도 아니네요...

뭐 메모리 블록 한참 잡아서 배열로 만들어 놓을 수도 있겠지만...그건 최후의 방법으로 하고... 더구나 문자셋의 개수가 많으면..힘들어지니깐..

어쨰튼 어떤 공식이 있을거 같아서...

혹시라도 명쾌하게 해결해 주실분 계시면... 밤세도록 제가 고민해야할 것을 해결해주신 댓가로...

아이폰 기프트 카드라도.. 문자로 쏴드릴께요...ㅠㅠ..... 이거 해결되기전까진 잠도 못자...

조합이 어떤 식으로 되냐면...

0 --> 0번째
1 ---> 1번쨰
2
0 0 --> 3번쨰..
0 1
0 2
1 0 ---> 6 번째
1 1
1 2
2 2
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
....
.....

neocoin의 이미지

모호한 부분

뭐 메모리 블록 한참 잡아서 배열로 만들어 놓을 수도 있겠지만.

그럼 저 데이터들이 파일에 있다는 건지요.

일반적인 프로그래밍 문제들처럼 'in, out, 제약조건' 을 명확하게 해주시면 다른 분들이 도움 드리기 편할 겁니다.

klyx의 이미지

k개의 숫자가 주어졌을 때, 중복을 허용하여 r개의 숫자를 뽑아서 나열하는 가지수는 중복순열(k^r)로 구할수 있습니다.
등비수열이므로, 최대 r개까지 뽑아서 만들수 있는 총수
S(r) = k + k^2 + k^3 + ... + k^r
은 쉽게 구할수 있구요. 공식은 아마 k(1-k^r)/(1-k) 였던거 같은데, 지금 확실히 기억하는 건 아니고,
도출도 간단하므로, 고등학교 수학1에서 등비수열의 합(등비급수)을 찾아보세요.
S(r)이 주어진 인덱스보다 커지는 최초의 r을 구해서, S(r-1)에 인덱스까지 남은 갯수 구해서 더하면 될것 같습니다.

지금보니, 인덱스에 해당하는 문자열을 반환하는 것이므로, 그냥 남은 갯수 그 자체가 반환할 문자열이 되겠군요.
0부터 세고 있어서 남은 갯수 그 자체인지, +1이나 -1되는지 지금 생각해보기가 귀찮지만 그건 조금해보시면 금방 알수 있을 거 같구요...
남은 갯수에 앞에 0채워서 내보내면 될거 같습니다.

ldknick의 이미지

중간에 000 이라든지 111 이라든지 하는 값이 들어가서 도저히 수열이나 조합으로는 안될거 같은데요...

제가 머리가 나쁜지.. 이해가 안되요...ㅠㅠ

klyx의 이미지

수열(sequence)이나 조합(combination)이 아니라 '순열(permutation)'입니다.

ldknick의 이미지

저 데이터들은 n 번째 스트링을 가져오라고 했을떄,
계산 되어 지는 순서를 나타내준 겁니다.
즉, 파일이나 메모리에도 없다는 거죠...

input 은 두가지 입니다.
문자셋 과 인덱스...

그러면.. 문자셋의 개수와 인덱스를 이용하여 n 번째 문자열의 조합을 반환하면 됩니다.

compute(char charset[], int nIndex)
{
int len = strlen(charset);
char result[];
....
...

return result[];
}

compute('012', 3) 했을떄 반환 값이 "00" 이라는 말입니다.
compute('012', 6) 했을떄 반환값(result) 는 "10" 이고요...
요런식이 되겠죠...

kaeri17의 이미지

3진수로.. n번째 군의 시작위치는 3(3^(n-1)-1)/2 이고요. 따라서 k번째 위치의 수를 알고 싶으면 3(3^(n-1)-1)/2 <= k < 3(3^n-1)/2 인 n을 찾고 그 군에서 k의 위치를 찾아서 3진수로 만들고 앞에 0을 붙이면 됩니다. 이때 n은 로그연산으로 상수시간에 찾을 수 있고요. 3말고 임이의 개수에 대해서도 같은 방법으로 하면 되고요.

비슷한 문제로 http://121.182.65.78/30stair/luckynum/luckynum.php?pname=luckynum&stair=3 이게 있고요, 이 문제에 대해 다음과 같은 풀이가 가능합니다.

#include <iostream>
#include <cmath>
int main(){
int a;
std::cin >> a;
int n=(int)(log(a)/log(2));
int m = a-pow(2,n)+1;
std::string s(n,'4');
int i=0;
while(m)
{
if(m&0x01){
s[n-i-1]='7';
}
m>>=1;
i++;
}
std::cout << s;
return 0;
}

더 원하신다면 여기에 댓글 달아 주세요. 자고 일어나서 도와 드리겠습니다. 근데 글의 예제에서 9번째 이후에 2 0, 2 1, 2 2 이어야 할것 같은데 맞나요?

ldknick의 이미지

0 1 2 를 넣은 것은 3진수가 아니라.. 임의로 넣은 것이고
입력 문자셋은 0 1 2 3 4 5 6 7 8 9 이렇게 10개를 넣을 수도 있고,
0 1 a b c d 이런식으로 넣을 수도 있습니다.

9번째 이후에 2 0, 2 1, 2 2 맞습니다...

입력된 모든 문자셋에 대해 중복과 반복 허용가능한 완전 조합을 해야 하는데,
재귀 함수같은걸 이용하지 않고 특정 공식으로 유도 하려고 합니다...

휴... 정말 어렵네요..

snowall의 이미지

앞에 0이 있는 것과 없는 경우가 구별된다는 것만 제외하면 진수변환 문제로 보이는데요

피할 수 있을때 즐겨라! http://melotopia.net/b

kaeri17의 이미지

다음과 같이 하면 되는것 같은데... 아 언어는 D언어 입니다. 하지만 뭐 C랑 비슷하게 생각하시면 됩니다.

import std.stdio;
import std.math;
char[] compute(char[] chars, int k)
{
    immutable int radix = chars.length;
    int n =  cast(int)(log((radix-1)*k/cast(double)radix+1)/log(cast(double)radix)+0.00001) +1; // n번째 군
    int r = cast(int)(k-radix/(cast(double)radix-1)*(pow(radix, n-1)-1));// n군에서 k의 위치 r
    char[] result = new char[n];
    foreach(ref x; result)
    {
        x = chars[0];
    }
    int i=0;
    while(r != 0)
    {
        result[$-1-i] = chars[r%radix];
        r/=radix;
        i++;
    }
    return result;
}
int main()
{
    for(auto i=0; i<20; i++)
    {
        char[] result = compute(['0', '1', '2'], i);
        writeln(result);
    }
    return 0;
}

compute에서 입력만 바꾸면 되요. 잘 이해 안가시면 제가 쓴 위 댓글을 잘 읽어보세요. '군'수열로 생각하고 n번째 군의 r번째 값은 n길이의 r의 진법변환입니다. 3진수든 몇진수든 일단 진법 변환 한 다음 그에 맞게 치환하면 됩니다. 예를들어 100까지 compute를 ['0', '1', '2', '3']에 대해 돌리면 다음과 같이 나옵니다.
0
1
2
3
00
01
02
03
10
11
12
13
20
21
22
23
30
31
32
33
000
001
002
003
010
011
012
013
020
021
022
023
... 중략
223
230
231
232
233
300
301
302
303
310
311
312
313
320
321
322
323
330
331
332
333
이럼 되는거 아닌가요?
ldknick의 이미지

정말 훌룡하십니다...
메일 따로 보내겠습니다.... 아이폰 키프트카드 보내드릴꼐요...

근데, n이 11107 부터 값에 오차가 생기나 봅니다.
잘나가다가... 엉뚱한 값이 튀어 나오는 것은.. log 같은 함수떄문인가요?....
ㅠㅠ...

snowall의 이미지

kaeri17님 말씀대로 3진수네요.
10진수->3진수 변환기 만드시면 될 듯.

n : 10진수, 정수.

while(n/3!=0){
a[k]=n%3;
n=n/3;
k++;
}

그럼
a[m]a[m-1]a[m-2]...a[2]a[1]이 10진수를 3진수로 변환한 수가 됩니다.
필요한 만큼 0을 붙여서 쓰면 되겠네요.

피할 수 있을때 즐겨라! http://melotopia.net/b

snowall의 이미지

음...중간에 0이 있는 것과 0이 없는 것을 구분해야 하는군요 -_-

알 것 같긴 한데 이것까지 처리하는 루틴은 시간이 없어서 나중에 시간 나면 해봐야겠군요..

피할 수 있을때 즐겨라! http://melotopia.net/b

jick의 이미지

근데 이거 숙제 아니에요?

helloneo의 이미지

문자셋이 3개면 3진수일테고.. 5개면 5진수일테고..
그냥 진수 변환으로밖에 안보이는데
문제가 잘 이해가 안되요..;;

WHAT'S UP

sangwoo의 이미지

xylosper 님이랑 kaeri17 님이 말씀하신 대로 하시면 됩니다.
kaeri17 님께서 k=3인 경우를 예로 들어 주셨네요.

----
Let's shut up and code.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <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].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.