현명한 소의 기록장

방학동안 혼자 공부하는 것도 좋지만 기록으로 남길 수 있는 공부를 하고싶어 무엇을 할 지 고민하다가 파이썬을 공부하기로 결정했다. 

파이썬 공부는 코드아카데미(https://www.codecademy.com/)에서 할지, 코세라(https://www.cousera.org/)에서 할지 고민하다가 풍부한 자료와 기초부터 차근차근 알려주는 코세라를 선택했다. 

오늘 첫 수업은 코세라에서 가장 유명한 파이썬 강의인 Python for everyone(https://www.coursera.org/learn/python)을 신청하여 1단원을 들었다. 영어로 수업하는데 어려운 표현도 잘 없고 영어자막도 있어 이해하는데 전혀 어려움이 없었다. 무엇보다 좋았던 점은 교수님이 내용을 설명해주는데 풍부한 예시와 재밌는 농담을 섞어 수업 내내 웃으면서 봤다.

내용적인 측면도 정리를 해보자면, Chapter 1. Why we Program? 단원 명 그대로다. 왜 우리가 프로그램을 하는지와 컴퓨터 하드웨어에 관한 아주 기초적인 설명이 주 내용이다. 이 course는 컴퓨터에 대한 지식이 없는 사람들을 대상으로 하기 때문에 매우 기초적인 내용부터 시작한다. 인상 깊었던 부분은 프로그래밍이란 무엇이며 왜 필요한가에 대해 설명해 주는데 컴퓨터 프로그래밍을 춤을 배우는 과정과 연결시켜 설명하는 부분이었다. 컴퓨터가 코드를 순서대로 실행하듯 인간도 춤을 배울 때 순서에 맞춰 한다는게 주 내용이었는데 이 내용을 옛날에 유행했던 마카레나 춤을 예시로서 사용했는데 이런 강의에서 마카레나 영상을 보니 강의가 더 친숙하게 느껴졌다. (마카레나 춤 주소 ㅋㅋ https://www.youtube.com/watch?v=vlzwuFkn88U). 또한 프로그래밍이라는 작업은 컴퓨터의 언어(파이썬)로 컴퓨터가 이해할 수 있는 한편의 이야기를 만드는 작업이라는 비유도 인상깊었다. 프로그래밍을 한편의 이야기를 만드는 작업이라 생각하니 코딩이 뭔가 더 낭만적이고 흥미로운 것으로 새롭게 느껴졌다. 

 오늘 들은 1강은 작년부터 C프로그래밍, 어셈블리, 자료구조 등등을 수강한 나에게 특별히 새로운 내용은 아니었지만 딱딱하고 어렵게 생각했던 코딩을 좀더 재밌고 부드러운 작업으로 새롭게 느끼게 해 준 수업이었다. 이번 주 중으로 2강도 들어야지!

총 7주차의 수업.

오 마케레나~

1주차 완료!

이번에는 정렬의 기본인 거품정렬(Bubble Sort) 문제를 풀어보았습니다!! 

기본이라지만 저에겐 역시나 어려웠습니다ㅠㅜ

다음 애플릿은 버블 소트가 이루어지는 과정이다.

//// [동작보기 클릭] //////

데이터 수 , 스텝 수가 주어질 때 위와 같이 동작하도록 한 후 주어진 스텝 후의 배열의 상태를 출력하는 것이다.

예를 들어 7 개의 데이터가 주어지고 , 2 스텝 후의 상태는

             6 2 9 8 3 4 7
1 번째 스텝: 2 6 8 3 4 7 9
2 번째 스텝: 2 6 3 4 7 8 9

2 6 3 4 7 8 9 를 출력하면 된다.

입력

입력의

• 첫 줄은 데이터의 개수 n, 스텝 수 s 가 주어진다. ( 1 <= s < n )
• 다음 줄에는 n 개의 데이터가 입력으로 주어진다. 각 수는 -1000 에서 1000 사이 정수이다.

n 은 1000 이하의 양의 정수이다.

출력

s 스텝 후의 상태를 한 줄에 출력한다.

입출력 예

입력

7 2
6 2 9 8 3 4 7

출력

2 6 3 4 7 8 9

즉 min[i]로 1과 2, 2와 3, 이렇게 두개씩 묶어 비교하는 코드를 짜면 됩니다.

완성된 코드는 다음과 같습니다.

#include <stdio.h>

 int main(){

        int sort[1000];

        int temp, count = 0;

        scanf("%d %d", &n, &s);

        for (i = 0; i < n; i++){

                 scanf("%d", &sort[i]);

        }

        while (count < s){

                 for (i = 0; i < n - 1; i++){

                         min = sort[i];

                         if (min > sort[i + 1]){

                                  temp = sort[i];

                                  sort[i] = sort[i + 1];

                                  sort[i + 1] = temp;

                                  }

                         }

                 count++;

                 }

                 printf("%d ", sort[i]);

        }

        return 0;

}

결과는??

통과~~

처음엔 밑과 같이 이중for문으로 풀려했으나, 그러면 안쪽 for문이 한바퀴 돈 뒤에 sort[0]부터 시작할 수가 없어 위의 코드와 같이

while-for문을 사용하여 문제를 풀었습니다.

                         min = sort[i];

                         if (min > sort[i + 1]){

                                  temp = sort[i];

                                  sort[i] = sort[i + 1];

                                  sort[i + 1] = temp;

                                  }

                         }

                 }

기본적인 버블정렬도 2시간만에 코드를 짰습니다ㅠㅠ 앞으로도 갈길이 멀군요. 더욱 노력해야겠습니다

평평하게 하기 문제는 5단계임에비해 쉬운 편이라 한번에 해결하였습니다. 다른 분들도 문제를 읽어보시면 쉽게 해결하실 수 있을 것이니 따로 자세히 적지는 않겠습니다.

---- 문제 -----

프로그램 명: box_brick

밥은 벽돌 쌓기놀이를 좋아한다.

"봐!! 내가 벽을 만들었어" 그는 누이 앨리스에게 이야기 했어. 그러자 누이는 "벽돌의 높이가 같아야지 제대로 된 벽이지"라고 되받았어.

밥이 곰곰 생각해보니 그녀의 말이 맞는 것 같아 높이를 같게 하기위해 벽돌을 하나하나 옮기기 시작했어.

밥은 게을러서 최소한의 벽돌을 옮겨서 같은 높이를 맞추기를 원해. 밥을 도와 줄수 있겠니?

입력

첫수는 벽돌 무더기의 수 n ( 1 <= n <= 50 ) 이고 , 다음 n 수는 각 무더기의 벽돌의 수(벽돌의 높이) hi 이다. 각 hi 는 1 에서 100 사이이다.

높이를 같이 맞출수 없는 데이터는 입력으로 주어지지 않는다.

출력

아래와 같은 형식으로 출력한다.

The minimum number of moves is k.

입출력 예

입력

6
5 2 4 1 7 5

출력

The minimum number of moves is 5.

보충 설명

출처:Southwestern European Regional Contest 1997

--- 해석 ---

이 문제는 즉 (블럭의 총 갯수 / 무더기의 개수)로 평균 갯수를 구하여 ( 평균보다 많은 블럭 갯수 - 평균 ) 를 출력하면 

되는 간단한 문제입니다.

--- 코드 ---

#include <stdio.h>

int main(){

        int a; //벽돌 무더기 수.

        int x[50], sum = 0, avg, sub = 0; //각 무더기의 갯수, 총 벽돌 수, 평균,   이동해야하는 벽돌 수.

        scanf("%d", &a);

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

                 scanf("%d", &x[i]);                       //각 무더기의 갯수 입력.  scanf("%d", x + i)이렇게 써도 됨.

                 sum += x[i];                              // 총 벽돌 갯수

        }

        avg = sum / a;           

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

        }

        printf("The minimum number of moves is %d.", sub);

        return 0;

}

이상입니다~!

2번째 과제인 최대수 연결문제... 개인적으론 정말 어려웠습니다..ㅋㅋㅋㅋㅋ헣 최대수 연결문제는 다음과 같습니다.

두 양의 정수가 주어질 때 두 수의 길이는 다음과 같이 약속

• 앞수에서 뒤수를 빼가는 과정을 반복.
• 뺀 값이 음수이면 종료 아니면 반복

예를 들어 , 두 수가 5 3 이면

5 3 2 1 1 0 1

5 3 의 길이는 이어지는 수의 개수 7 .

n 이 입력으로 주어질 때 두 번째수를 1 , 2 , .. n 으로 줄 때 최대 길이를 구하는게 문제이다.

n 이 5 이면

• 5 1 4
• 5 2 3
• 5 3 2 1 1 0 1
• 5 4 1 3
• 5 5 0 5

최대 길이는 5 3 일 때 7 이다.

입력

n 은 1000 이하의 자연수이다.

출력

최대 길이를 출력한다.

입출력 예

입력

5

출력

7

어제 소인수분해 문제를 푼 경험을 바탕으로 하나의 숫자를 정해 자세히 분석하였으나 빨리 이해되지는 안더군요ㅜㅜ 그래도 내가 

휴리스틱으로 쉽게 계산한 것을 하나하나 정리하여 그것을 코드로 정리하면 문제를 풀 수 있다는 진리를 바탕으로 다음과 같이 첫 코드를 짰습니다.

#include <stdio.h>

int main(){

        int a, b, temp, x, y = 1, MAX = 0;

        long double c[1000][10000] = { 0 }; //2차원배열로 각 경우의 길이 저장.

        int i = 0, j = 0;

        scanf("%d", &x); 

        a = x;

                 for (i = 0; i < x; i++){

                         j = 0;

                         b = y;

                         while (a - b >= 0){

                                  c[i][j] = a - b;

                                  temp = a;

                                  a = b;

                                  b = temp - b;

                                  j++;

                         }

                         y++;

                 }

        for (i = 1; i < x; i++){

                 if (sizeof(c) / sizeof(c[i - 1]) < sizeof(c) / sizeof(c[i])){

                         MAX = sizeof(c) / sizeof(c[i]);

                 }

        }

        printf("%d", MAX);

        return 0;

}

하하... 보이시는대로 쓸데없이 복잡하기만하고 돌아가지도 않는 똥을 창조하였습니다.. ㅋㅋㅋ 그러나 이렇게 만드는데도 몇시간 걸렸다는게

함정.. 하하

완전 열심히 만들었는데 이름은 겁나 많이 들었지만 개인적으론 처음보는 stackoverflow 때문에 아무리 코드를 수정해도 빌드도, 당연히 

디버깅도 안되서 2시간 반이 지나서야 미련을 버리고 코드를 싹 밀어버렸습니다ㅜㅜ 

(대체 왜그런걸까요? 심심할 때 stackoverflow 구체적으로 찾아봐야지)

절망은 잠시 뒤로한체 후배들과 제 집에서 맜있는 카레 밥과 카레 라면까지 4명서 총 8인분을 먹고나니 다시 시작할 힘이 생기더군요.

전 코드를 밀고 다시 천천히 생각해보니 꼭 2차원 배열을 쓸 필요는 없다고 생각이 들더군요. 그래서 다음과 같이 코드를 짰습니다.

#include <stdio.h>

int main(){

        int a, b = 1, c;

        int x = 0, y, temp = 0, count = 0, MAX[1000], M;

        scanf("%d", &x);

        a = x;

        c = a - b;

        for (y = 1; y <= x; y++){

                 c = x - y;

                 b = y; //while문 안에서 바뀐 b 값을 y에 맞춰 하나씩 증가하게 함.

                 while (c >= 0){

                         count++;

                         temp = a;

                         a = b;

                         b = temp - b;

                         c = a - b;

                 }

                 MAX[y] = count; // 각 경우의 길이들을 배열에 담아줌.

                 if (MAX[y] > MAX[y - 1]){  //배열의 원소들을 비교해 제일 큰 값만 저장.

                         M = MAX[y];

                 }

        }

        return 0;

}

결과는??????????????

하하ㅏㅎ하하하하하하ㅏ핳하ㅏ핳하하하하하ㅏㅎ하하하ㅏ하 정말 너무 기뻤습니다 하하하ㅏㅏㅜㅜㅜㅠㅠㅜ

오늘 하루종일 고민했던 문제를 혼자힘으로 풀다니ㅜㅠㅜㅜㅜㅜ으어어ㅜㅜㅜ 행복합니다ㅠㅜㅜ

2번 문제를 풀면서 뭔가 이런 방향으로 하는게 맞는 것 같은데 답이 애매하게 안나온다면, 한단계 씩 디버깅을 꼭꼭꼭꼭!!!!

하자는 교훈을 얻었습니다. 여태까진 겁나 쉬운 문제밖에 안풀어서 (물론 이것도 그런축에 속하는 것 같긴 하지만..ㅠ) 디버깅을 따로 안써도 해결됬는데

이번문제는 정말 디버깅의 도움을 많이 받았습니다. 

결국 2번 문제 결론 ------- 디버깅 차냥해~

최근 중앙대학교 알고리즘 학술 동아리 CAULISM 기초반에 가입하였습니다. 과제로

http://www.Dovelet.com 4단계인

1. 소인수분해 문제

자연수 n 이 입력으로 주어진다. 이 수를 소인수 분해하는 프로그램을 작성하시오.

입력 n 은 2 이상 1 000 000 000 이하의 자연수이다.

출력 소인수를 크기 순으로 공백을 사이에 두고 한 줄에 출력한다.

입출력 예

입력

20

출력

2 2 5

입력

7

출력

7

와 최대수연결 문제가 과제로 나왔는데 두번째 문제는 내일 포스팅하도록 하겠습니다.

처음엔 간단하게 입력 받는 수 a와 2를 나머지연산하여 나눠떨어지면 출력하고, 그렇지

않으면 계속 1씩 더하면 되겠다!라고 생각하여 다음과 같이 코드를 짯습니다.

 이렇게하니 출력에는 전혀 문제가 없었지만 체점에서 96690과 같이 큰수가 여러번 들어가니 소인수 b를 1씩 올린다고 while문이 쓸데없이 너무 많이 돌아가 timeout이 뜨더군요ㅜㅜ 처음에 너무 쉽게 생각해서 여기서 맨붕ㅜㅜ 그래서 소인수를 어떻게 증가시키면 될까 하다가 20의 경우를 생각해보니 

2  20

2  10

5  5

   1

소인수 2에서 5로 증가하는 것은 2 + 5%2 이고 다른 경우에서도 성립할 것 같으니 소인수를

b += a %b라 하면 되겠다! 라고 생각하며 소인수의 증가를 확인할 printf와 함께 밑과 같이 수정하였지만

94690의 소인수는 2, 5, 17, 557인데 이렇게 부정확하게 나오더라구요 ㅜㅜ

소인수를 하나하나 올려주자니 running time이 너무 길어지고, 다르게 표현하자니 정확한 표현 방법을 모르겠고 답이없는 상황이 되었습니다.ㅠ 그러나 몇십분동안 차근차근 생각해보니 소수는 2, 3에서만 1만큼 증가하고 3에서 5, 19에서 23과 같이 모두 2n(짝수)만큼 증가한다는 것을 깨달았습니다!!ㅋㅋㅋ 그래서 다음과 같이 코드를 수정하였습니다.

과연 실행 결과는???

핰 통과!!! ㅋㅋㅋㅋ 그렇게 어려운 문제는 아니였지만 부족한 실력으로 열심히 생각해서 나온 결과라 정말 기쁘더군요 ㅋㅋㅋㅋㅋㅋㅋ하하핳하 

1번을 풀면서 코드를 간단하게 짜는 것도 좋지만 running time 생각하면서 좀 더 직관적으로 짜는게 좋을 수도 있다는 것과 문제가 안풀리면 아주 기초적인 단계부터 하나하나씩 예시들을 써보면 도움이 된다는 것을 깨달았습니당.

내일 최대수연결 문제도 힘내서 풀고 포스팅하겠습니다 오예~