메뉴 건너뛰기

BLENDING

자유 게시판

개미수열

01오치문2014.10.31 11:01조회 수 5718댓글 11

  • 1
    • 글자 크기

01' 기장, 02년 회장, 지금은 그냥 마이너스 존입니다.

  • 1
    • 글자 크기
회장님 보세요 (by 03김남균) 엔진 라이브러리 토론 (by 99곽용우)

댓글 달기

댓글 11
  • 01오치문글쓴이
    2014.10.31 20:01 댓글추천 0비추천 0
    문제의 핵심은 연속되는 숫자를 어떻게 카운팅할 것인가? 같군요. 그렇죠?
    더 깔끔한 방법 공유해주세요. ^^

    c (재귀)
    ------------------
    #include <stdio.h>
    #include <string.h>

    const int MAX_DEPTH = 10;

    int getLength(char *pChar)
    {
        char ch = *pChar;
        int count = 0;

        while(*pChar && *pChar == ch) {
            count++; pChar++;
        }

        return count;
    }

    void solve(char *pChar, int depth)
    {
        printf("%sn", pChar);

        if (depth >= MAX_DEPTH) return ;

        char output[64];
        memset(output, 0, sizeof(output));

        while(*pChar) {
            int len = getLength(pChar);
            sprintf(output, "%s%c%d", output, *pChar, len);
            pChar += len;
        }

        solve(output, depth+1);
    }

    int main()
    {
        solve("1", 0);
        return 0;
    }
    -------------------


    python (반복문)
    -------------------

    MAX_LOOP = 10

    def get_length(num_str):
        first_char = num_str[0]
        for i in range(0, len(num_str)):
            if num_str[i] != first_char:
                return i
        return len(num_str)

    def solve(num_str):

        new_str = ""
        start_pos = 0

        while start_pos < len(num_str):
            length = get_length(num_str[start_pos:])
            new_str += num_str[start_pos] + str(length)
            start_pos += length

        return new_str

    if __name__ == '__main__':
        num_str = "1"
        for i in range(MAX_LOOP):
            print str(i) + ": " + num_str
            num_str = solve(num_str)
    ----------------------------------



    --------------------
    import itertools

    def next_morris(number):
        return ''.join('%s%s' % (digit, len(list(group)))
            for digit, group in itertools.groupby(str(number)))

    def morris_generator(maxlen, start=1):
        num = str(start)
        while len(num) < maxlen:
            yield int(num)
                num = next_morris(num)

    for n in morris_generator(10):
        print n
  • 01오치문님께
    당첨! 01오치문님에게 10포인트 팡팡 쏩니다!
  • void main(){
     char w=2,s[1024]="1n11";
     for(int i=0;i<100;i++)
     if(s[i]==s[i+1])
      s[w+1]++;
     else{
      s[w++]=s[i],w++,s[w+1]='1';
      if(s[i+1]=='n')
       s[w++]='n',s[w+1]='1',i++;
     }
     printf(s);
    }

  • 현재 학교에서 진행하고 있는 문제해결프로그래밍 과목에서 나왔던 문제네요..

    이 과목은 현재 2시간내에 3문제를 해결해야 하는 과목으로 바뀌었는데요..

    재귀는 생각하지 않았었는데.. 다시한번 생각해봐야겠습니다 ㅠㅠ

    일단 그당시 제가 해결할때 사용했던 자바 코드를 올려보겠습니다.

    import java.util.Scanner;


    public class test {

     public static void main(String[] args) {
      String str = "1";
      Scanner in = new Scanner(System.in);
      int n = in.nextInt();
      for(int k=1; k<=n; k++){
       if(k==1){
        System.out.println(str);
       }
       else if(k==2){
        str += "1";
        System.out.println(str);
       }
       else{
        String tmp = "";
        int a = 1;
        char ch = str.charAt(0);
        tmp += ch;
        while(!str.substring(1).equals("")){
         str = str.substring(1);
         if(ch == str.charAt(0)){
          a++;
         }
         else{
          ch = str.charAt(0);
          tmp += a;
          tmp += ch;
          a = 1;
         }
        }
        tmp += Integer.toString(a);
        System.out.println(tmp);
        str = tmp;
       }
      }
     }

    }

  • void ant(char *dest, char *src)
    {
    char c, t[3];
    int i, l, n;

    dest[0]=0;

    c=src[0];
    n=0;

    l=strlen(src);
    for(i=0; i<l; i++){
    if(c != src[i]){
    sprintf(t, "%c%d", c,n);
    strcat(dest, t);
    c=src[i];
    n=1;
    }
    else {
    n++;
    }
    }
    sprintf(t, "%c%d", c,n);
    strcat(dest, t);
    }

    int main()
    {
    char a[1000]="1", b[1000]="";
    char *in, *out;
    int i=0;
    printf("%sn", a);
    for(i=0; i<10; i++){
    if(i%2==0){
    in=a;
    out=b;
    }else{
    in=b;
    out=a;
    }
    ant(out, in);
    printf("%sn", out);
    }

    return 0;
    }
  • 01오치문글쓴이
    2014.11.3 13:16 댓글추천 0비추천 0

    @용우형 - 와우~ 코드 이해가 쉽지 않네요 @_@ 


    @김시형 - 최초의 자바버전이군요 ^^ 

    1) 변수 이름을 직관적으로 지으면 코드 이해가 더 쉬울것같아요. => 물론 알고리즘성 문제에서는 종종 무시하곤 하죠. 저도 그렇고 -_-;

    2) 규칙을 잘 정리하면 k=1일때와 2일때, 예외로 뺀 부분을 없앨 수 있을 것같네요 ^^



    댓글이 늘어나니 재밌네 



  • 01오치문글쓴이
    2014.11.3 14:54 댓글추천 0비추천 0

    JAVA 버전 

    (중간에 구분자를 넣어서 가공한 후 나중에 한번에 처리, 이런 방법도 있겠군요)


    public class MorrisGenerator {


        private final String PARTITION_MARK = " ";


        public void generate(int limit) {

            String str = "1";

            for(int i = 0; i < limit; i++) {

                System.out.println(str);

                str = makeMorrisNumber(makePartitionedStr(str).split(PARTITION_MARK));

            }

        }


        private String makeMorrisNumber(String[] strs) {

            String morris = "";


            for(String s : strs) {

                morris += (s.charAt(0) + String.valueOf(s.length()));

            }


            return morris;

        }


        private String makePartitionedStr(String str) {

            String newStr = "";

            char bChar = str.charAt(0);


            for(int i = 0; i < str.length(); i++) {

                char nChar = str.charAt(i);

                if (bChar != nChar) {

                    newStr += PARTITION_MARK;

                }

                bChar = nChar;

                newStr += nChar;

            }


            return newStr;

        }


        public static void main(String[] args) {

            MorrisGenerator mg = new MorrisGenerator();

            mg.generate(10);

        }

    }

  • 재미있을거같아서 저도 한 번 해봤어요~~
    지금 14학번들은 1학년동안 자바를 배워서 자바로 만들어봤습니다.
    아직 api도 많이 모르고 아는 지식이 부족해서
    수업시간에 배운 컬렉션을 이용해서 만들어봤는데 제대로 작동해서 감동먹었어요 ㅠㅠ... 
    이런 문제 많이올려주시면 감사하겠습니다!! 한가할때하니까 재미있네요 ㅎㅎㅎ


    package Practice;
    import java.util.*;
    public class Num1 {

    public static void main(String[] args) {

    Scanner input = new Scanner(System.in);
    System.out.println("-----개미수열 프로그램-----");
    System.out.print("몇 행까지 출력할까요? : ");
    int lineN = input.nextInt(); 

    ArrayList antMom = new ArrayList(); // 엄마 개미수열 (바로 위에 수열)

    int firstN = 1; // 첫번째 엄마수열을 만듬.
    antMom.add(firstN);

    for (int i=0; i<lineN; i++) {
    ArrayList ant = new ArrayList(); // 한 행이 지날때마다 새로운개미수열을 만든다.

    int number = (int)antMom.get(0); // 엄마 개미의 첫번째 방에 있는 숫자부터 검사한다.
    int count = 0;
    for (int j=0; j<antMom.size(); j++) {
    if(number==(int)antMom.get(j)) // 첫번째숫자(Number)부터 검사해서
    count++; // 같은숫자가 연속된만큼 count 해준다.
    else { // 만약 다음 방의 숫자가 number가 아니라면
    ant.add(number); // (숫자의 연속이 끊긴다면)
    ant.add(count); // number와 count를 개미에 저장하고
    number = (int)antMom.get(j); // number는 다음에 검사할 새로운 숫자가 되고
    count = 1; // 그 숫자는 이미 한번 있는것이니 
    } // 카운트를 1부터 시작한다.
    }
    ant.add(number);
    ant.add(count);
    for (int k=0; k<antMom.size(); k++) { //출력
    System.out.print(antMom.get(k));
    }
    System.out.println();
    antMom = ant; // 이제 이 개미가 엄마개미가 된다.
    }

    }

    }

  • 14박지훈님께

    아빠개미는 어딨어?

  • 14박지훈님께

    엄마개미 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

  • 14박지훈님께
    01오치문글쓴이
    2014.11.14 14:24 댓글추천 0비추천 0

    ㅋㅋㅋㅋㅋ 작명센스 ㅋㅋ

    굿잡~~~~~!! 앞으로 가끔씩 올릴께요~

번호 제목 글쓴이 날짜 조회 수
공지 [난해한코딩대회] 예시4 16황지우 2020.08.31 385
공지 회장님 훈화말씀16 16황지우 2020.03.16 8603
공지 스맛폰으로 BLENDING홈피 새글 알림 받기1 BLENDING 2011.06.25 195332
3362 내일 군대가네요 하하......3 13전성혁 2015.01.19 4011
3361 [알고리즘 문제] 풀어보세요~5 01오치문 2014.12.27 4253
3360 회장님 보세요 03김남균 2014.11.21 4382
개미수열11 01오치문 2014.10.31 5718
3358 엔진 라이브러리 토론 99곽용우 2014.10.28 4691
3357 재영아 화이팅!4 09이혜성 2014.10.06 4812
3356 예전 팩맨게임 보기 싫어서 다시올려요.10 11이은정 2014.09.23 5021
3355 유니티 공부 하는것 같아서4 07최윤수 2014.09.16 4982
3354 홈페이지가 죽었구나..4 10박태수 2014.09.01 5124
3353 8월18일날 군대갑니다 ㅠ4 13황정우 2014.08.09 5212
3352 잊고 있던 것 수정! 08정호열 2014.06.11 4945
3351 iconshop??6 14최중원 2014.04.17 5435
3350 03학번 오태원선배가 결혼하네요5 08이혜린 2014.04.01 5875
3349 간만에 퀴즈 하나18 01오치문 2014.02.11 7135
3348 2014년 새해 복 많이 받으세요4 07최윤수 2014.01.01 5163
3347 2013년 12월 4일 히터 구매 했습니다.1 13전성혁 2013.12.04 5264
3346 홈페이지 새벽 4시쯤에 약간 느려질 수도 있습니다.1 08정호열 2013.11.21 7215
3345 2013년 엔씨소프트 하반기 신입사원 공개채용이 시작되었습니다.!!! 03김상헌 2013.10.10 8772
3344 다들 아는지는 모르겠지만..4 97김민경 2013.09.11 8851
3343 굽신굽신 블렌딩 흥신소..4 00한우람 2013.07.09 11816
이전 1 ... 17 18 19 20 21 22 23 24 25 26... 190다음
첨부 (1)
개미수열.jpg
106.5KB / Download 53
위로