원당컴퓨터학원

원당이가 컴퓨터 시간에 수업을 듣는데 선생님이 다음과 같은 숙제를 내 주셨습니다. "간장 공장 공장장은 강 공장장이고 된장 공장 공장장은 공 공장장이다" 를 이진수를 이용해서 표현해 볼 수 있도록 나타내되 그 길이가 가장 짧게 표현을 해 보라고 하셨습니다. 원당이를 위해 이 문제를 어떻게 해결할지 고민해 주세요. 문제풀이) 이러한 문제는 허프만 코드라고 하는 압축 알고리즘을 사용하면 됩니다. 허프만 알고리즘의 특징은 발생빈도가 적은 문자를 많은 비트를 사용하고 발생빈도가 많은 문자를 적은 비트를 사용하게 되면 가장 최소의 비트로 어떤 텍스트 파일을 압축할 수 있는 알고리즘입니다. 먼저 허프만 알고리즘의 원리에 대해 알아 보겠습니다. 1) 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리를 생성..

시저암호란? 카이사르암호(Caesar cipher) 또는 시저암호는 암호학에서 다루는 간단한 치환 암호의 일종이다. 위와 같이 암호화 하고자 하는 내용을 알파벳별로 일정한 거리만큼 밀어서 다른 알파벳으로 치환하는 방식이다. 2개의 회전 디스크를 구성하여 코드를 암호화 하거나 암호 해독 할 수 있다. 위와 같이 회전디스크를 이용하여 회전을 시킨후에 WONDANGCOM 을 암호화 한다고 하면 ZRQGDQJFRP 로 암호화 할 수가 있게 된다. 이렇게 3칸씩 뒤에 있는 값으로 암호화 하는 방식이므로 for(i=0;i

문제 매년 12월이 되면 온 세상 아이들이 기다리는 날이 있습니다. 바로 크리스마스입니다. 하지만 원당이는 걱정을 하며 후회를 하곤 합니다. 새해부터 지금까지 내가 착한일을 얼마나 많이 했는지 또는 나쁜일을 얼마나 많이 했는지 산타 할아버지는 알고 계시기 때문입니다. 그런데 새해부터 11월 말까지 착한일을 많이 하다가 12월에 원당이는 부모님 말씀을 듣지 않고 삐뚤게 나갈거야 하고 심통을 부렸습니다. 크리스마스가 다가오자 원당이는 한편으로 후회가 되긴 했지만 이미 엎어진 물이라서 주워 담을 수 없었습니다. 하지만 산타 할아버지는 원당이의 이런 마음을 헤아려서 12월에 나쁜일을 했지만 착한일을 많이 한 원당이에게 다음과 같이 선물을 주려고 합니다. 1달 착한일을 하면 선물 1개 2달 연속으로 착한일을 하면..

원당이는 보물지도를 가지고 보물을 찾기 위해 탐험을 떠났습니다. 보물지도에 표시된 곳에는 동굴이 있었으며 동굴의 문은 굳게 잠겨 있습니다. 이 문에는 다음과 같은 표시의 구멍이 있었고 그 아래에는 숫자가 적힌 9개의 돌이 있습니다. 문 아래에는 다음과 같이 문을 여는 방법이 적혀 있습니다. 1단계) 맨위의 원에는 첫번째 수가 적힌 돌을 놓는다. 2단계) 자신의 왼쪽 아래에는 자신의 수보다 2배가 큰 수를 놓는다. 3단계) 자신의 오른쪽 아래에는 자신의 수보다 2배 큰 수 보다 1이 더 큰 수를 놓는다. 4단계) 하위 원의 규칙도 동일한 규칙을 갖게 된다. 원당이를 위해 여러분이 돌의 위치를 찾아서 원당이가 보물을 찾도록 도와 주세요. 정답) 컴퓨팅 사고력 이 문제는 컴퓨터과학에서 사용하는 트리에 관한 문..

여름방학을 맞이해서 원당이는 할아버지댁에 놀러 갔습니다. 할아버지댁 서재에서 읽고 싶은 책을 찾다가 오래된 책에서 다음과 같은 모양이 그려진 오래된 양피지를 발견했습니다. 이렇게 생긴 암호표와 함께 아래에 다음과 같은 메시지가 있었습니다. 이러한 암호화된 문자가 있는데 이것이 외계어인지 아니면 무엇을 뜻하는 것인지 원당이는 무척 궁금했습니다. 여러분이 이 암호를 해독해 주실수 있을까요? 문제풀이) 위에서 나온 양피지는 암호를 해독할 수 있는 암호화키입니다. 즉 의 의미는 A 를 의미하는 문자입니다. 따라서 위와 같이 매칭을 하게 되면 WONDANGCOM 이 됩니다. 컴퓨팅사고력 암호학에서 또는 라고 불리우는 치환 암호는 이름에서 알 수 있듯이 프리메이슨들이 즐겨 사용한 암호로 매우 간단한 치환을 사용한다..

세명의 선교사와 세명의 식인종이 강의 건너편에 있습니다. 현재 강을 건너와야 하는데 건너편에는 2인용 나룻배 하나만 있습니다. 만약 강의 어느 한쪽이라도 식인종 수가 선교사의 수보다 많으면 식인종들은 선교사를 잡아 먹습니다. 선교사들이 잡아 먹히지 않고 6명 모두 무사히 강을 건너는 방법을 선교사들에게 설명해 주세요. 문제풀이) (강건너선교사수,강건너식인종수,이쪽선교사수,이쪽 식인종수) 와 같은 형태로 생각해 보면 (3,3,0,0) 에서 가능한 경우는 (2,2,1,1) 이다. (2,2,1,1) 에서 보트를 가지고 선교사가 강을 건너간다면 (3,2,0,1) 이 된다. (3,2,0,1) 에서 선교사가 이동하는 순간 잡아 먹히므로 이때는 식인종 둘만 이동하는 경우 밖에 없다. 따라서 (3,0,0,3) (3,0..

문제 20개의 정차역을 거치는 기차가 출발 하였습니다. 처음 출발하는 역에서 10명의 손님이 탔고 그 다음 역에서는 7명이 탔습니다. 그 다음 역에서도 7명이 타고 이렇게 19개의 정차역에서 각각 7명씩이 탔습니다. 중간에 내린 사람은 없다고 합니다. 20번째역에 도착했을때 기차 안에 있는 손님은 몇명이겠습니까? 문제풀이 출발역 - 10명 2번째 - 17명 3번째 - 24명 ... 이렇게 하나 하나 계산을 해도 됩니다. 하지만 이 문제를 잘 살펴 보면 처음은 10, 그 다음부터는 7씩 증가 되는 등차 수열이 됩니다. 등차 수열이란 항 과 항 사이의 차(공차) 가 동일한 성격을 가지는 수열을 말합니다. 초항이 0 이고 공차가 7 이라고 하면 두번째 항은 0 + 7 * 1, 세번째 항은 0 + 7 * 2....

원당이는 다음과 같이 1에서 부터 10000 까지 나열을 해 놓은 수에서 2와 3의 배수를 제거했습니다. 그리고 남은 수를 확인하니 다음과 같은 수들이 남아 있었습니다. 1,5,7,11,13,17,19,23,.... 이렇게 나열해 놓고 나니 갑자기 457번째에 있는 수가 무엇인지 궁금해졌습니다. 여러분이 이 수가 무엇인지 구해 주세요~ 문제풀이) 이 문제는 규칙을 찾는 문제입니다. 표를 그려서 해당의 수를 삭제 해보면 다음과 같이 증가 되는 규칙을 찾을 수 있습니다. 1부터 시작해서 +4, +2, +4, +2 .... 와 같이 증가 되는 규칙입니다. 이렇게 확인하면 1,5,7,9... 와 같이 2개씩 증가하면서 6의 등차수열을 같는 원리 임을 알 수 있습니다. 따라서 457번째 위치의 수는 1번째 수부터..

원당이는 A 도시에서 B도시를 거쳐서 C도시를 가려고 합니다. 길이 다음과 같을때 최단 거리로 방문을 하려고 하는데~ 가는 경로가 굉장히 많습니다. 원당이는 A->B->C를 갈 수 있는 경우가 몇가지인지 궁금해졌습니다. 여러분이 갈수 있는 경우가 몇가지인지 알려 주세요. 문제풀이) 위와 같이 A에서 B로 가는 최단 경로의 경우의 수는 52 입니다. B에서 C로 가는 최단 경로이 경우의 수는 10입니다. 따라서 A에서 B로 가는 52에서 B에서 C로 각각 가는 경우가 10이기 때문에 두개의 곱 52 * 10 = 520 가지 입니다. 컴퓨팅 사고력 그래프 이론은 수학에서 객체간의 짝을 이루는 관계를 모델링하기 위해 사용되는 구조입니다. 위에서 A,B,C와 같이 어떤 위치를 정점이라고 하며 버텍스(vertex..

문제 길동이는 오늘 새로운 수의 표현과 진법에 대해 배웠습니다. 다음은 수학시간에 배운 내용입니다. 오늘은 수학시간에 수의 표현에 대해 배우겠어요~ 일반적으로 우리가 사용하는 0,1,2,3,~ 이라는 수를 표현하는 것은 십진법이라고 합니다. 0부터 9 까지의 10개의 수를 사용하기 때문에 십진법입니다. 9보다 하나가 더 커지면 일의 자리는 0 이 되고 십의 자리에 1을 올림을 하면서 10 으로 표현하게 됩니다. 따라서 자리수는 오른쪽 부터 왼쪽으로 10배씩 커지게 됩니다. 이진법 체계라는 것은 0,1 이라는 두 수를 가지고 표현하는 것이고. 0,1 다음에 더 표현 할 수 없으므로 일의 자리는 0 이 되고 2의 자리에 1을 올림을 하면서 10으로 표현하게 됩니다. 따라서 자리수는 오른쪽 부터 왼쪽으로 2배..