반응형

하노이탑 문제는 이산수학이나 프로그래밍의 재귀 함수에서 자주 나오는 유형의 문제입니다.

오늘은 하노이탑의 원리에 대해 알아 보도록 하겠습니다.

하노이탑이 유래된 것은 인도 베나레스에 있는 한 사원에 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세개의 다이아몬드 바늘이 동판 위에 세워져 있습니다.

이 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 

가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기 까지 쌓아 있습니다.

이것이 신성한 브라흐마의 탑입니다.

브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮기는데요.

해당 규칙은 다음과 같습니다.

1. 한번에 하나의 원판만 옮길수 있다.

2. 작은 원판 위에 큰 원판을 올릴 수 없다.

이 규칙에 따라 원판을 하나씩 옮기는데 이 일이 끝날 때 탑은 무너지고 세상은 종말을 맞게 된다는 전설이 있는 문제인데요.

아직까지 세상의 종말을 맞이 하지 않았다는 것은 현재도 하나씩 옮기고 있는 중인지도 모르겠네요.^^

원리를 살펴 보면 위와 같이 3개의 원판을 세번째에 옮기기 위해서는 맨 아래를 세번째로 옮겨야 합니다. 

그러기 위해서는 다음과 같이 두개의 원반이 가운데에 가 있어야 합니다.

 이렇게 이동 한 후에 1번의 가장 큰 원판을 3번에 이동 후에 2번에 있는 2개의 원판을 규칙에 맞게 3번에 옮겨 주면 되는데요.

이러한 문제는 전형적인 귀납적인 사고를 필요로 합니다.

귀납적인 증명을 하기 위해서는 단위가 가장 작은 원판의 갯수가 하나일때 한번의 이동으로 1번 바늘에서 3번 바늘로 움직일 수 있다는 것을 확인 할 수가 있습니다.

이때 F(1) = 1 

그렇다면 원판의 갯수가 2개 인 경우에는 한개의 원판을 2번 바늘에 옮긴 후에 1번에 있는 원판을 3번에 옮긴 후 다시 2번에 있는 원판을 옮깁니다.

이때 F(2) = F(1) (1개를 2번으로 이동횟수) + 1 (1번의 원판을 3번으로 이동횟수) + F(1)(2번의 원판을 3번으로 이동 횟수) = 3 이 됩니다.

그 다음 3개 짜리를 생각해 봅니다.

3개 짜리는 2개를 2번 원판에 옮긴 횟수 F(2) + 1(1번의 가장 아래를 3번으로 옮긴 횟수) + F(2) (2번에 있는 원판 2개를 3번으로 이동하는 횟수) 가 됩니다.

이렇게 계산을 하면 다음과 같은 식을 유도할 수 있습니다.

F(n) = F(n-1) + 1 + F(n-1) = 2 * F(n-1) + 1 이 됩니다.

그렇다면 위의 식에 값을 대입해 보면 다음과 같이 식을 유도해 볼수가 있습니다.

F(1) = 1

F(2) = 2 * 1 + 1 = 2 + 1 = 3

F(3) = 2 * 3 + 1 = 4 + 2 + 1 = 7 

F(4) = 2 * 7 + 1 = 8 + 4 + 2 + 1 = 15

...

어떤 규칙이 보이시나요?

어떤 수 n 에 대해서 2^n - 1 의 규칙을 찾게 됩니다.

 

따라서 신이 말한 64개의 원판을 옮기기 위해서는 2^64 - 1 의 시간이 걸릴 텐데요.

이 값은 무려 18,466,744,073,709,551,615 의 값이 되기 때문에 1번의 이동시간을 1초로 계산 하여도 약 5000 억년이 된다고 하니 아무리 빠른 승려라고 해도 1초에 하나씩 옮기기는 어렵지 않을까 생각 되네요.^^

 

이러한 문제를 C언어로 구현하면 다음과 같이 구현 할 수가 있는데요.

void hanoi(int n,int from, int to, int temp) // n개의 원판을 from 에서 to로 보내는데 ,temp 를 거쳐서 보내자.
{

        if(n==0) return; //보낼 원판이 없다면 빠져 나가자.

        hanoi(n-1,from,temp,to); //n-1개의 원판을 거쳐가는 temp에 보내자 이때는 to를 이용해서 보내면 재귀적이기 때문에 알아서 보내 준다.^^

        printf("%d번째 원판 : %d번 바늘 -> %d번 바늘\n",n,from,to); //from 에 있는 가장 아래 원판을 to 에 보내는 것을 확인 하자.

        hanoi(n-1,temp,to,from); //temp 에 있는 n-1개의 원판을 from을 거쳐서 to 에 보내면 끝난다.

}

메인에서 호출은 다음과 같이 호출하면 되겠네요.

hanoi(3,1,3,2);// 3개의 원판을 1번에서 3번으로 보내는데 2번을 거쳐서 보내라...

 

64개를 보내는데 1초에 1억번을 계산 한다고 해도 엄청난 시간이 걸릴테니... 64개는 실험을 안 해 보셔도 될것 같아요.^^

하노이탑 - 프로그래밍 언어에서 재귀 함수를 배울때 자주 나오는 문제이기도 하고 이산수학에서 귀납적 사고 부분에서 자주 나오는 유형의 문제였는데요... 

이런 유형의 문제를 해결 하다 보면 실생활에 있는 문제들에서 어떤 규칙을 끌어 내는 것에 많은 도움이 될것이라 생각 되네요.

오늘도 열심히 공부하고 있는 우리 학생들을 응원합니다.

인천 서구 알고리즘 학원 - 인천 원당 컴퓨터 학원

 

 

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2019.09.03 13:16 신고

    하노이탑, 대학다닐 때 배운 배운기억이 납니다.
    알고리즘 구현항때 꼭 배우는 기술인듯 합니다.

  2. Favicon of https://richwnaak.tistory.com BlogIcon 평강줌마 2019.09.04 01:13 신고

    고등학교 때 선생님께서 잠시 보여주신 적이 있네요.
    그 때도 어려웠는데... 나이가 든 지금도 어렵네요.^^

  3. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2019.09.04 06:21 신고

    프로그래밍언어에서 재귀 함수에 관한 문제로 하노이탑이 자주 나오는군요..
    제겐 어려운 문제입니다..ㅎ

  4. 핑구야날자 2019.09.04 07:00

    하노이 탑은 학생들에게는 좀 어려운 문제일 수도 있겠군요

  5. Favicon of https://appadal.tistory.com BlogIcon 아빠달 2019.09.04 19:59 신고

    지금 봐도 어렵습니다....^^;;;

반응형

 

오늘은 2020 카카오 블라인드 채용 소식을 올려 드립니다.

현재 카카오와 같이 코딩 테스트로 인재를 뽑는 회사가 많아 지고 있는 것을 보면 알고리즘의 중요성을 알 수가 있는데요.

알고리즘의 힘은 기업에 입사하여 그 빛을 발하지 못하는 경우도 종종 있을 수 있습니다.

하지만 기업의 입장에서는 최소한의 안전 장치와 같이 알고리즘을 잘 하는 사람이라면 어떤 업무에서도 적응을 잘 할 수 있기 때문에 알고리즘을 잘 한다고 하면 일단은 믿을 수 있을 것입니다.

같은 기업에 입사를 하여도 부서 혹은 업무에 따라서 이 알고리즘 능력이 빛을 발 할 수도 있고 발하지 못할 수도 있습니다.

처음 개발자로 입사하지만 대기업에서는 부서 로테이션에 따라서 관리직으로 갈 수도 있기 때문입니다.

따라서 IT 기업에 입사하기 위해서는 알고리즘을 어느정도는 공부를 해 둔다면 분명히 유리 한것은 사실인것 같네요.

2020 카카오 블라인드 채용 소식을 보면 다음과 같습니다.

접수 기간은 9월 4일까지 접수를 하시면 됩니다.

모집회사는 카카오 계열의 회사입니다.

지원 자격은 학력, 전공이 모두 무관합니다.

하지만 이렇게 블라인드 채용이 학력,전공 무관하다고 해서 우리 학생들이 큰 꿈을 포기하고 고등학교만 졸업하고 바로 취업 하겠다는 생각은 하지 않았으면 좋겠네요.

제가 아직은 고지식해서인지 모르겠지만...

간혹 학부모님들에게 꼭 대학교를 가야 할 필요가 있을까요? 라는 문의를 받는데요.

저는 정말 가정형편 때문이 아니라면 학생을 대학교에 보내시길 권해 드립니다.

학생들이 사회에 진출하기 이전에 배우고 준비할 수 있는 기간은 초.중.고 입니다.

하지만 초.중.고 때는 자기 스스로 준비하는 학생도 많겠지만 대부분의 학생들은 학부모님 혹은 어른들 때문에 어쩔 수 없이 공부하는 학생들이 대다수 인 것으로 알고 있습니다.

하지만 대학교는 성인이 되어서 다니는 학교 입니다.

이 때부터는 학부모님의 간섭이 거의 없는 시간이 되기 때문에 오로지 자신의 몫으로 다니는 유일한 배움의 기간이 아닐까 생각이 들더라구요.

이렇게 스스로 생각하면서 자신의 위치를 생각하고 어떤 진로를 결정해야 하는지를 4년의 기간을 통해서 성숙해 가면서 더 많은 것을 보고 듣게 됩니다.

따라서 정말 어쩔 수 없는 환경이 아니라면 대학교는 꼭 보내시라고 말씀을 드리고 있는데요.

 

대학교를 취업을 위한 목표라기 보다는 학생의 성장을 할 수 있는 몫으로 남겨 주셨으면 하는 바램이 들더라고요.

 

현재 대학교 졸업을 앞두셨거나 혹은 고등학교 졸업 후 취업을 목표로 하시는 분들 중에 카카오 기업에 관심이 있는 학생들이라면 카카오 블라인드 채용 조건을 잘 확인 하시고..

자신이 원하는 기업에 성공적인 취업을 기원합니다.

 

채용사이트 : https://www.welcomekakao.com/competitions/102/2020-kakao-blind-recruitment

 

저희 원의 학생들이 더 큰 꿈을 꾸고 더 큰 사람이 되기를 응원합니다.

인천 서구 원당 컴퓨터 학원

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2019.08.26 10:33 신고

    요즘 블라인드 채용이 대세인가봅니다.
    실력이 채용의 우선이 되는 건 당연해 보이네요.

  2. Favicon of https://ramideunioni.tistory.com BlogIcon 라드온 2019.08.26 18:10 신고

    코딩실력만보겠단건데, 실력만큼이나 인성이 중요하다고 생각하는데 뭐가 맞는건지 모르겠어요ㅎ

    • Favicon of https://wondangcom.com BlogIcon 원당컴 2019.08.26 18:26 신고

      실력으로 1차 통과 하면 면접이 따로 있습니다. 먼저 실력을 검증하고 인성을 별도로 보는거죠.^^

  3. Favicon of https://enomoosiki.tistory.com BlogIcon 행복사냥이 2019.08.26 23:08 신고

    역시나 실력이 있어야 되는군요. ^^

  4. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2019.08.27 05:17 신고

    2020 카카오 블라인드 채용 소식을 공유해주셧군요? 카카오가 정말 요즘 대세인 것 같습니다

  5. 핑구야 날자 2019.08.27 06:47

    하반기에 대기업 공채 소식이 없다고 하던데 반가운 소식이네요

  6. Favicon of https://moldone.tistory.com BlogIcon 청결원 2019.08.27 06:55 신고

    비오는 아침 이지만 좋은 하루 시원한 하루 보내세요~

    포스팅 잘 보고 갑니다~

  7. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2019.08.27 06:59 신고

    요즘은 유수의 기업들이 블라인드 채용을 많이 하는군요^^

  8. Favicon of https://richwnaak.tistory.com BlogIcon 평강줌마 2019.09.01 20:22 신고

    좋은 정보이네요.
    카카오에 채용되고 싶은 사람이 많을 듯 해요.
    저도 15년 전으로 돌아간다면 이 회사에 취직을 하고 싶네요.^^

반응형

출처: 과학기술인재진로지원센터

이 자료의 출처는 https://www.sciencecareer.kr/board/board/archives/ 입니다.

여기서 자세한 자료를 다운 받아 보실 수 있는데요.

과학기술에 따른 미래직업의 그림 연계도가 잘 되어 있어서 참고를 해 보았습니다.

먼저 삶의 질 향상 부문에서 삶의 균형 제고 분야에서 실감형 콘텐츠 개발자(문화,예술 콘텐츠 개발), 자율주행 전문가 를 꼽고 있네요.

또한 삶의 질 향상 부문에서 건강/환경개선 분야에서 소셜로봇전문가(부정적상황,감정공유 및 치료수단의 활용),뇌파분석전문가(뇌질환 진단 및 치료),재생장기조직개발자(3D프린터등을 이용한 인체장기조직의 대체 소재 개발),착용로봇개발자(노인,장애인,근로자의 근력 증감 및 신체적 건강개선),정밀의료전문가(원격의료지원을 통한 효율성제고) 등을 꼽고 있습니다.

사회적 신뢰제고 분야에서 사회적관계개선 분야에서는 사회위험예측전문가(빅데이터,IoT등을 통한 사회위험 예측 및 분석 개발),블록체인전문가(정보보안으로 개인,기업,국가간 사회적 신뢰제고),BCI전문가(ICT,웨어러블 장비를 통한 고령인구,장애인의 의사소통기술),IoT보안전문가(IoT장비의 보안 취약성의 보안기술 발전으로 사회적 신뢰기반 마련) 등을 꼽고 있습니다.

사회적 신뢰제고 분야에서 소득과 자산보호 분야에서는 핀인사이터(빅데이터 기반의 금융정보 분석 및 처리기술개발로 정확한 금융정보 제공을 통한 소득과 자산보호),핀테크 보안 전문가(금융정보 유출등에 따른 보안기술 구축에 따른 금융자산 보호 및 사회적 신뢰구축),사이버금융 프로파일러(전산망해킹,사이버테러등 사이버 금융범죄의 지능화 등에 따른 금융범죄 예측및 방지를 통한 안전한 금융거리 서비스 제공) 등을 꼽고 있습니다.

 

이렇게 보니 대부분의 미래직업은 빅데이터 가공과 정보보안에 중점이 되어 있는 직업인것 같네요.

물론 노약자(저도 조만간에 저 혜택들을 받고 살아야 할것 같은데요.)나 장애인들의 편의성을 제공해 주는 기술개발 등에 관점을 두는 직업도 있는데요.

지속적으로 IoT 의 개발과 증가에 따른 보안 취약점은 지속적으로 대두 되고 있는 사안 중 하나 일것입니다.

최근 러시아에서 개발한 앱으로 인하여 얼굴 정보가 러시아에 있는 서버에 모두 업로드 된다는 사실로 인해 뉴스에서 떠들썩하게 나오더라구요.

사실 그러한 일이 뭐가 대수야 얼굴 편집을 위해서 서버에서 업로드 하고 서버에서 얼굴을 편집해 주어야 하는 것이 정상 아니야? 라고 반문 하실 수도 있는데요.

그러한 모든 데이터 수집만으로도 나중에 잘 가공한다면 그것을 악용할때 치명타를 입게 된다는 점이 문제이기 때문에 그러한 부분을 염두에 두고 업로드 하는 것이 문제가 되는 것이거든요.

 

미래직업이 위에서 나와 있는 직업이 전부는 아닐 것입니다.

더욱더 다양하게 아직 세상에 나와 있지 않은 직업이 70프로라고 하는데요.

오감을 활용하여 미래의 변화되는 모습을 상상하고 무엇이 어떻게 변할지 촉각을 세우고 고민하시면서...

어떤 것을 준비해 나가야 하는 것이 좋은 것인지 한번쯤 고민을 해 보실 수 있는 계기가 될것 같아서 과학기술인재진로센터의 미래직업 자료를 인용해 보았습니다.

 

항상 성공하는 삶이 되기를 기원합니다.

인천 서구의 학생 전문 컴퓨터 학원 - 원당컴퓨터 학원

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2019.08.23 04:56 신고

    나중에 시간이 날때 공유해주신 링크에
    들어가서 과학기술인재진로센터의 미래직업 자료를 읽어봐야겟어요^^

  2. Favicon of https://ramideunioni.tistory.com BlogIcon 라드온 2019.08.23 05:51 신고

    빅데이터 가공이 아무래도 유망한 것 같습니다. 저도 요즘 마케팅쪽에 관심을 갖고 들여다보다보니, 빅데이터를 가공해서 소비자들에게 다가가는 방법에 대해 배우고 있는데 재미있더군요.ㅎ

  3. 핑구야날자 2019.08.23 06:50

    미래 직업을 잘 보고 준비하면 되겠군요

  4. Favicon of https://moldone.tistory.com BlogIcon 청결원 2019.08.23 06:53 신고

    오늘 하루도 즐거운 하루 보내세요~
    오늘 역시 포스팅 잘 보고 가네요~

  5. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2019.08.23 08:27 신고

    과학을 좋아하고 적성에 맞는다면 앞으로 다양한 직업을 선택할수가
    있겠군요^^

  6. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2019.08.23 08:38 신고

    미래 4차산업의 기술을 보면 거의가 it를 기반으로 하고 있다는것입니다.
    인공지능과 빅데이터도 마찬가지구요.

  7. Favicon of https://appadal.tistory.com BlogIcon 아빠달 2019.08.23 16:25 신고

    앞으로 어떤 산업이 발전할지 한눈에 볼 수 있네요.
    즐거운 주말 보내세요~ ^^

반응형

대회 사이트 - https://contest.nypc.co.kr/

 

오늘부터 순차적으로 문제가 공개 됩니다.

아직 신청하지 않은 학생도 바로 신청하셔서 참여 할 수 있으므로 관심있는 학생은 신청후 참여 하시면 됩니다.

 

어제 연습문제 공개 되어서 확인을 해 봤는데 다음과 같이 두가지 유형의 문제가 나왔습니다.

 

소스코드 유형과 실행결과 유형이 있는데요.

소스코드 유형은 여태까지 보아 왔던 프로그래밍 코딩을 해서 소스코드를 제출하는 유형이구요.

실행결과 유형은 꼭 소스코드를 제출하는 것이 아니고 입력 예제를 확인 하고 그 값이 무엇인지...

손으로 계산을 하던가 프로그램으로 만들어서 결과값을 만들던가 해서 그 결과값만 제출하는 유형이었네요.

 

어제 연습문제 유형 중에 재미 있는 문제가 출제 되어서 확인을 해 보았습니다.

 

이것이 어떤 숫자인지 판단하라는 문제였습니다.

눈으로 확인하기에 너무 쉽게 5라는 숫자가 나옵니다.

하지만 이걸 프로그래밍 하기에는 정말 많은 경우의 수가 나오기 때문에...

쉽지 않은데요.

요즘 딥러닝 알고리즘을 이해하고 그것을 이용해서 이미지를 분석하는 형태가 존재하기는 하는데...

그것 또한 경우의 수가 너무 많기 때문에 사실 프로그래밍으로 처리하기에는 학생들에게는 많은 벽에 부딪히게 되더라구요.

 

하지만 이러한 문제가 출제 되었을때 그냥 정답 5만을 제출하는 것 보다는...

프로그래밍으로 구현할 때는 어떤 식으로 구현하면 될까를 고민해 보는 것도 좋은 접근인것 같아요.

 

NYPC 참여하는 학생들이 이 문제들을 모두 풀어야 돼~~~ 라기 보다는...

이런 문제도 있었네...

너무 재미있네.... 라고 접근을 해 주면 재미 있는 대회가 될것 같네요.

 

여름방학 동안 재미있는 NYPC 와 함께 시원한 여름 보내시길....

 

인천 서구 알고리즘 학원 - 원당컴퓨터학원

 

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://enomoosiki.tistory.com BlogIcon 행복사냥이 2019.08.07 23:11 신고

    개인적으로 어려운 대회 같아 보여요.^^

  2. Favicon of https://uhastory.tistory.com BlogIcon 유하v 2019.08.07 23:33 신고

    많은 학생들이 좋은 결과를 얻길 바랍니다!!^^

  3. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2019.08.08 04:49 신고

    NYPC 2019 예선 대회가 열리는군요?
    많은 학생분들이 참여하셔서 경험을 쌓으셨으면 좋겟습니다^^

  4. 핑구야날자 2019.08.08 06:43

    처음 보는데 오네요 학생들이 좋은 결과를 얻으면 좋겠어요

  5. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2019.08.08 07:12 신고

    넥슨에서 청소년들을 대상으로 한 프로그램 대회가 있군요.
    관심있는학생들이 많이 참여하면 좋겠습니다.

  6. Favicon of https://padmasambhava.tistory.com BlogIcon 생명마루한의원 2019.08.08 15:49 신고

    청소년 프로그래밍 대회가 열리는군요~
    학생들이 좋은 결과를 얻길 바랍니다^^

  7. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2019.08.09 09:48 신고

    잘 보고 갑니다.
    오늘도 덥네요.
    즐거운 하루 되세요~^^

+ Recent posts