원당컴퓨터학원

과목 : 이산수학

수업시작일 : 2019.9.8(일)

수업기간 : 2019.9.8~2019.12.1(약 3개월)

수업시간 : 매주 일요일(오후 5:00~6:10 -1시간 10분)

비용 : 무료

모집인원 : 10명 내외

모집대상 : 원당컴퓨터 학원 원생 

수업내용 : 집합,행렬,순열,그래프,트리 등

준비물 : 교재( 수업전 각자 구입 - 교재는 신청자에 한해서 공지해 드립니다.)

모집기간 : 2019년 9월 1일까지

내용 : 컴퓨팅 사고력을 키우기 위한 이산수학 특강을 진행합니다.

연초에 계획했던 부분은 큰 틀을 잡기 위해 계획을 하지만 학생들의 성향과 진도에 맞춰 무료 특강 내용이 약간씩 변경이 발생하고 있습니다. 이 점 양해 부탁 드립니다.

이번에 진행하는 이산수학은 문제풀이 과정이 아닌 이산수학의 집합,행렬,순열,그래프 등 컴퓨팅 사고력과 밀접한 수학의 개념을 이해하기 위한 과정입니다.

일대일 수업이 아닌 강의식 수업이므로 이 수업을 참여하기 위해서는 어느정도 수학적인 지식을 가지고 있는 학생이 유리합니다.

따라서 중등부 이상 학생과 초등부 학생중 중학 수학이 어느정도 선행 되어 있는 학생이 신청을 해 주시면 좋을것 같습니다.

인천 서구  원당 컴퓨터 학원

https://programmers.co.kr/competitions/104/siliconvalley-jobfair2019?utm_source=mailchimp&utm_medium=newsletter_siliconValley&utm_campaign=siliconValley2019

프로그래머스에서 실리콘벨리 잡페어 소식이 있어서 링크를 걸어 보았습니다.

저희 원에서 열심히 공부하는 이유 중 가장 큰 것은 자신이 알고리즘 공부를 하는 것을 좋아해서 이겠지만 이렇게 좋아하는 알고리즘 공부가 좋은 학교, 좋은 직장 혹은 좋은 직업과 연계 된다면 훨씬 더 도움이 될것 같아서...

이렇게 알고리즘을 이용한 학교 입학정보, 혹은 취업정보 혹은 직업정보 들이 있으면 공유를 하려고 합니다.

먼저 잡페어 개요를 살펴 보면 다음과 같습니다.

국내의 실력 있는 개발자와 미국 실리콘밸리의 유망한 스타트업을 연계하여 개발자에게는 기술력과 커리어 성장을, 스타트업에게는 인재 확보의 기회를 제공합니다.

미국의 실리콘밸리에는 유망한 스타트업이 많기 때문에 더 넓게 배우고 공부할 기회가 되는것 같습니다.

실제로 처음 발을 어느 분야에 디딛는지에 따라 알고리즘을 사용하는데 그 업무에 한정적이기 때문에..

처음 디딛는 회사가 평생의 업무 중에 방향성이 되는 경우가 대부분인것 같습니다.

이런 면에서 실리콘밸리의 최첨단 IT 업무에 발을 디딘다면 배울것도 많을 것이라 생각되는데요.

지원자격으로는 위와 같이 대학교 3년 이상 졸업후 1년 이내 대상을 인턴 자격이 되고 트레이니는 경력 1년 이상의 현직 개발자 입니다.

진행단계는 온라인 접수 후 코딩테스트와 과제테스트 등을 거치게 되는데요.

코딩테스트는 인턴과 경력직 모두 공통사항이구요. 과제테스트는 인턴에만 해당합니다.

요즘에는 IT 기업에서 코딩테스트로 입사시험을 보는 경우가 많기 때문에...

아무래도 알고리즘 공부를 해 놓는다면 IT기업에 입사할 때 도움이 될 수도 있을것 같은데요.

하지만 알고리즘 공부 누군가에게 억지로 떠밀려서 공부하는 것은 바람직해 보이지 않네요.

알고리즘 공부를 하다 보면 정말 자신이 도전의식이 생기고 도전하면서 자신의 계발이 되는 그 깨우침을 깨달으면서 그 곳에서 재미를 느끼는 것이 가장 좋은 공부 방법이라고 생각이 드네요.

오늘도 열심히 공부하고 있는 학생들이 알고리즘 공부만이 아니라 모든 공부에서 자신이 하나 하나 깨우치면서 깨우치는 재미를 느끼면서 스스로 성장하는 학생이 되시길 바랍니다.

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

문제를 풀다 보면 비둘기집의 원리에 의해서 이렇게 된다고 정의를 하는 문제 유형들이 많이 나오는데.

오늘은 비둘기집의 원리가 무엇인지 확인을 해 보겠습니다.

비둘기집의 원리는 정말 단순합니다.

비둘기집은 2개이고 비둘기는 3마리입니다.

비둘기가 저녁에 잠을 자기 위해 비둘기 집에 들어가야 되는데...

그렇다면 반드시 한개의 비둘기집에는 비둘기가 2마리 이상이 존재하게 된다는 원리입니다.

가령 1번집에 비둘기 3마리 2번집에 0마리, 혹은 1번집에 2마리 2번집에 1마리, 1번집에 1마리 2번집에 2마리,1번집에 0마리 2번집에 3마리 이렇게 4가지 경우의 수 밖에 없는데 이 4가지 경우의 수에서 반드시 한개의 집에는 2마리 이상이 존재 하게 된다는 것인데...

이러한 정의를 위키백과에서는 다음과 같이 귀류법으로 정의 하고 있습니다.

이것을 일반화된  원리로 정의를 하면 다음과 같이 정의를 합니다.

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 n/m이상의 사물을 담고 있어야 한다.

확률론적으로 일반화된 원리로 정의를 하면 다음과 같이 정의를 합니다.

1/m의 균일한 확률로 n개의 비둘기를 무작위로 m개의 비둘기집에 넣었다면 확률적으로 적어도 하나의 비둘기집에 두마리 이상의 비둘기가 들어가게 된다.

이러한 비둘기집의 원리를 이용해 문제를 풀어 가는 유형을 살펴 보면 다음과 같습니다.

이러한 유형의 문제를 풀어 나가기 위해서는 어떤 집합이 동일한 성질을 갖는 원소를 적어도 두 개 갖는다는 것을 증명하기 위해서 먼저 이 집합의 원소들이 갖는 서로 다른 성질의 가짓수를 세고, 다음으로 원소들의 개수를 센다. 
비둘기 집의 원리는 만약 원소의 개수가 성질의 가짓수보다 많으면 적어도 두 개 이상의 원소는 동일한 성질을 갖는다는 것을 의미하기 때문에 다음과 같은 문제를 해결 할 수가 있습니다.

먼저 코드를 만드는 경우가 몇가지인지 먼저 원소의 갯수를 세어 보면

앞의 두자리가 알파벳이므로 26 * 26, 뒤의 두자리가 숫자이므로 10*10 이므로 모든 경우는 26 * 26 * 10 * 10 인것을 확인 할 수 있습니다.

이것을 계산하면 67600 가지수가 나오는데 고객의 수는 75000명입니다.

따라서 비둘기집의 원리에 의해서 적어도 두명 이상은 같은 코드를 사용할 수 밖에 없게 됩니다.

또다른 유형의 문제는 다음과 같은 유형이 있습니다.

이러한 유형의 문제는 

n개의 별개의 사물을 m개의 용기에 나누어 담으면 적어도 한 개의 용기는 n/m이상의 사물을 담고 있어야 한다.

는 원리를 이용하면

159/8  이상이므로 20개의 리그

159/10 이상이므로 16개의 리그

156/12 이상이므로 14개의 리그 

라는 것을 확인 할 수가 있습니다.

이렇게 비둘기집의 원리를 응용해서 많은 문제들이 출제 되고 있는데요.

그 중에도 비둘기 집의 원리는 어떤 문제가 풀릴 수 없다는 것을 증명하기 위해 사용됩니다.

전형적인 예는 자동차 번호판 위에 표시할 문자와 숫자의 형식을 결정하는 것이다. 번호판을 설계할 때 반드시 고려해야 할 사항은 등록된 모든 차량들이 서로 다른 문자-숫자 형식을 가질 수 있도록 하기 위해서는 얼마나 오랜 기간 동안 사용할 것인가와 번호판 위에 문자와 숫자를 어떤 형식으로 나타내야 하는가 하는 문제입니다.

자동차 번호판의 수를 세는 문제는 각 자리를 정해진 종류의 기호로 나타내므로 곱의 법칙을 적용하는 간단하고 좋은 예제입니다.

오늘은 비둘기집의 원리와 응용하는 문제에 대해 알아 보았는데요.

비둘기집의 원리는 컴퓨팅 과학에서 이것이 가능한지 불가능한지 판단을 하기 위한 중요한 요소 중의 하나입니다.

가령 첫번째 문제와 같이 은행의 고객들에게 ATM 카드를 발급해야 되는데...

서로 다른 고객이 같은 카드 번호를 소지하고 있다고 하면 중대한 오류가 발생할 것입니다.^^

프로그램을 설계할 때 많은 부분을 고려해야 하지만 특히나 이런 부분은 중요한 부분 중 하나입니다.

비둘기집의 원리 어렵지는 않지만 컴퓨팅 과학에서는 중요하다는 사실...

놓치지 않고 잘 챙기시길 바랍니다.^^

인천 서구 컴퓨터학원 - 원당컴퓨터학원

제가 알고리즘 공부를 하면서 자주 보는 책중 하나가 구종만님이 지은 알고리즘 문제해결 전략 이라는 책입니다.

그 책의 서문에 다음과 같은 글이 있어서 인용해 봅니다.

그렇다면 이러한 문제 해결 능력을 훈련하기 위한 방법은 무엇일까요?

이 책에서는 여러 프로그래밍 대회에 참가하면서 문제해결 기술을 익혀 가는 것을 추천하고 있습니다.

오늘은 학생들에게 꼭 필요한 문제해결능력을 키우기 위한 방법에 대해 알아 볼까 합니다.

1. 많은 문제를 풀어 보자.

   - 온라인 채점 사이트를 이용해서 될수 있으면 많은 문제를 풀어 보는 것이 도움이 될 수 있습니다.

   www.acmicpc.net

   www.jungol.co.kr

   algospot.com

   train.usaco.org/usacogate

   www.topcoder.com/tc

   위와 같은 사이트 외에도 좀더 찾아 보면 다양한 사이트가 존재 합니다.

   이러한 온라인 채점 사이트에서 꾸준히 문제를 풀어 보면서 자신이 아는 것을 이용해서 직접 프로그래밍을 작성해 보는 것이 중요 합니다.

2. 프로그래밍 대회에 많이 참여해 보자.

초중고 - 한국정보올림피아드, 한국코드페어,NYPC

대학생 - ACMICPC(대학생 프로그래밍 경시대회)

일반인 - 탑코더, 구글코드잼,코드포스 등

다양한 대회에 참여 해 보면서 자신의 실력을 가늠해 보고 실전 경험을 쌓을 수 있습니다.

==========================================================================

   - 프로그래밍 대회에서 요구하는 대부분의 알고리즘 대회는 어떤 UI와 같은 부분을 사용하지 않고 단순히 텍스트 파일을 읽어 들여 텍스트 파일을 출력하는 문제가 대부분입니다. 따라서 UI 구현 보다는 참가자는 문제를 해결하는데에만 집중할 수가 있습니다.

   - 시간제한과 메모리제한에 따른 문제 해법으로 자신이 알고 있는 알고리즘으로 해결이 안되는 경우 또 다른 새로운 방법을 생각해 볼 수 있기 때문에 자신이 배운 알고리즘으로는 해결이 안되는 경우가 대부분이기 때문이 원리를 찾고 그 원리를 새로운 해법을 이용해서 해결을 시도 하면서 해법을 찾아 보면서 문제해결능력을 키울 수 있습니다.

  - 프로그래밍 대회에서는 다양한 테스트 케이스를 가지고 자신이 생각해 보지 못한 경우도 나오기 때문에 다양한 각도에서 문제를 바라보는 훈련으로 문제해결 능력을 키울 수 있습니다.

문제 해결 능력을 키우기 위해서는 많은 문제를 풀어 보는 방법 밖에 없는 것을 확인해 보았는데요.

학생들이 간혹 두려워 하는 것이 끝도 없는 이 알고리즘을 계속 파고 들어야 하나? 라는 벽에 부딪히게 됩니다.

이럴때 저도 학생에게 "끝을 봐야지?" 라는 말을 못합니다.

사실 저도 아직 이 알고리즘의 끝이 어딘지 모르기 때문입니다.

제가 어렸을때 의문을 가졌던 부분이 있습니다.

우주의 끝은 있을까? 라는 질문이었죠.

이 생각만 하면 끝이 없다는 것은 더 생각 하기 싫었지만 끝이 있다면 그 끝이 끝난 그 밖은 무엇일까? 라는 생각에 사로 잡혀서 많이 고민을 했었던 적이 있는데요.

이 알고리즘 세상에도 끝이 있을까? 라는 궁금증이 생기네요.^^

아직도 수시로 새로운 알고리즘이 튀어 나오고 새로 발견되고 있고 아직 해결하지 못한 문제들도 있으니까요

하지만 저희가 1년정도 꾸준히 같이 공부해 온 한 학생을 보면서 훈련이 중요하다는 것을 느끼는 한 학생이 있는데요. 그 학생은 처음에 정말 수학을 암기형 으로 풀어 온 학생인데 지금은 원리를 찾으려고 노력하고 해법을 찾으려고 하는 학생이 되어 있음을 보면서 이 사실만은 얘기해 줄 수가 있을것 같아요.

"알고리즘 공부를 꾸준히 하다보면 어느새 성장해 있는 자신의 모습을 볼 수 있을거야" 라고요.

저희가 풀어 보는 알고리즘 문제의 유형들이 대부분 수학적인 사고력을 응용하게 되고 그 원리를 찾아 내는 것에 초점이 맞춰져 있다 보니 아무래도 생각하는 힘이 커지는 것을 확인 할 수가 있었습니다.

문제해결능력을 키우고 싶은 학생은 알고리즘 공부의 참맛을 느껴 보시길 바랍니다.^^

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