원당컴퓨터학원

모양이 똑같은 100개의 동전이 있다. 그중 99개는 진짜 동전이고 하나는 가짜 동전이다. 진짜 동전의 무게는 모두 똑같고 가짜 동전의 무게는 가벼운지 무거운지를 알 수 없지만 진짜동전과 무게는 서로 다른 것만 알 수 있다. 최소 횟수는 몇회인지 찾아내고 3보다 큰 N개의 동전이 입력 되었을 때 가짜 동전을 찾아내기 위한 최소 횟수는 몇번인지 알고리즘을 설계해 보시오. 문제풀이) A그룹 50개, B그룹 50개로 나눈다. A그룹 50개를 재어 보면 정상적인 동전만 있다면 정상적인 동전 한개의 무게는 총무게/50 이 된다.(1회) 그 다음 A그룹의 25개의 무게를 재 보았을 때 25개의 총무게/25 와 같은지 판별하면 50개의 동전이 정상인지 아닌지 판별 할 수 있다. 만약 50개의 동전이 모두 정상이라면 ..

바구니 안에 빨간공 120개와 파란공 30개가 들어 있다. 이렇게 들어 있는 바구니에서 다음과 같은 절차에 의해 공을 꺼낸다. 1. 두개의 공을 꺼낸다. 2. 만약 두개의 공의 색깔이 같으면 빨간공 한개, 서로 다르면 파란공 한개를 집어 넣는다. 3. 1과 2를 계속 반복한다. 바구니의 마지막 공의 색깔은 어떤 색이 될까? 문제풀이) 바구니 안의 공이 빨간공 120개 파란공 30개 에서 시작을 한다. 만약 두개 모두 빨간공을 꺼냈다면 빨간공이 119개,파란공 30개가 된다. 두개 모두 파란공이었다면 빨간공이 121개,파란공은 28개가 된다. 두개 모두 색깔이 다르다고 하면 빨간공 119개 파란공 30개가 된다. 이것을 확인 했을 때 빨간공은 1개가 줄거나 1개가 늘어난다. 파란공은 0개가 줄거나 2개가 ..

맥너겟수란? 맥도날드에서 판매하는 치킨 맥너겟은 처음에 6조각,9조각,20조각으로만 판매했는데 이에 6,9,20의 합으로 얻을 수 있는 자연수를 맥너겟 수라고 한다. 예를 들어 6 + 6 = 12, 6+9+9+9+20=53 이므로 12와 53은 맥너겟 수이다. 맥너겟 수에 맥너겟 수를 더하거나 곱해도 맥너겟 수이다. 곧 덧셈과 곱셈은 맥너겟 수의 집합에 대하여 닫혀 있다. 출처 - https://namu.wiki/w/%EB%A7%A5%EB%84%88%EA%B2%9F%20%EC%88%98 맥너겟 수 - 나무위키 이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 ..

문제 크기와 모양이 똑같은 n 개의 동전이 있다. 그 중에 1개의 동전이 가짜 동전이라고 한다. 이 가짜 동전의 무게는 진짜동전과 구별 할 수 없는데 단지 무게만 다르다고 한다. 단, 무게가 가벼운지 무거운지는 모른다. 이때 최소의 횟수로 가짜 동전을 구분 할 수 있는 방법을 찾는 알고리즘을 구현하라. 출처) 길벗 - 알고리즘 퍼즐 문제풀이 동전의 무게가 가벼운지 무거운지 안다면 다음과 같이 반씩 나누면서 찾을 수 있을 것이다. n이 100이라면 50:50 으로 가짜 동전이 있는 쪽을 선택후 25:25 -> 12:12 -> 6:6 -> 3: 3->1:1 과 같이 나누면서 찾을 수 있다. n이 101이라도 동일한 횟수로 나눌 수 있다. 즉 101 -> 50:50 으로 나눌 수 있다. 여기서 1개는 50:5..

문제 출처) 길벗 - 알고리즘 퍼즐 문제) 늑대 n마리, 염소 n마리, 양배추 n개, 사냥꾼 n명이 있다. 누구도 위험해 지지 않는 방법으로 이들을 한 줄로 세우는 방법을 찾아야 한다. 즉 사냥꾼 옆에 늑대가 있다면 사냥꾼은 늑대를 총으로 쏘아서 죽일 것이고 늑대 옆에 염소가 있다면 늑대는 염소를 잡아 먹을 것이고 염소 옆에 양배추가 있다면 양배추는 염소에게 먹힐 것이다. 또한 같은 종류 끼리는 서로 인접하지 않아야 한다. 즉 사냥꾼과 사냥꾼이 같이 있으면 안된다. 이 문제의 해를 구하는 알고리즘을 설계하시오. 문제 풀이) 먼저 n = 1인 경우 다음과 같이 생각 할 수 있다. 첫번째 : 늑대,염소,양배추,사냥꾼이 나오는 각각의 경우를 생각해 보자. 늑대-양배추-사냥꾼-염소 염소-사냥꾼-양배추-늑대 양배..

물로 가득 찬 8L 짜리 물병 한개가 비어 있고 비어 있는 5L,3L 물병이 각각 하나씩 있다. 이 셋 중 어느 물통에든 정확히 물 4L를 담는 방법을 설명하라. 물은 이 세개의 물통을 이용할 수만 있으며 물을 옮겨 담을 때는 원래 물이 들어 있던 통이 완전히 비거나 물이 담기는 통이 가득 찰 때까지 옮겨 담아야 한다. [문제 출처] 길벗 - 알고리즘 퍼즐 [문제풀이] 이러한 유형의 문제는 정보올림피아드 예선 문제에서 자주 출제되던 유형의 문제이다. 풀이 방법은 다음과 같다. 8L짜리 물병에서 5L 에 가득 채우는 방법(8L/3L,5L/5L,3L/0L)와 3L에 가득 채우는 방법(8L/5L,5L/0L,3L/3L) 두가지 방법이 존재한다. 이 것을 다음과 같이 각각 또 분배를 할 수 있다. 8L/3L,5L..

문제 조명이 n개(n>2) 있고 조명은 원형으로 배치되어 있다. 각 조명마다 아래에 스위치가 있다. 각 스위치를 조작할 때마다 스위치 바로 위에 있는 것과 양쪽에 인접한 두개의 on/off 상태가 바뀐다. 처음에는 모든 조명이 꺼져 있다. 예를 들어 1,2,3 과 같이 세개의 조명이 원형으로 배치 되어 있다면 1번 아래 있는 스위치를 조작 했을 때 1과 양 옆에 있는 2와 3의 조명이 on 이 된다. 이 때 스위치 조작 횟수를 최소화 하면서 모든 조명을 켤 수 있는 알고리즘을 설계하라. 문제출처) 길벗 - 알고리즘 퍼즐 문제풀이 조명이 3개 인경우에는 1,2,3 어느 스위치를 조작해도 한번에 모두 켜진다. 마찬가지로 3의 배수인 6개인 경우는 1,2,3,4,5,6 이라면 1번과 4번만 조작하면 모두 켜지..

어느 마술사가 한 관객에게 1부터 27까지 쓰여진 27장의 카드 중에서 한 장을 고른 후 그 카드를 마술사에게 보여주지 않은 채 다시 카드 무더기 안에 집어 넣으라고 시켰다. 마술사는 카드를 다시 섞은 다음 한 번에 한 장씩 앞면이 보이도록 세 무더기로 나누기 시작했다.(예 1~27 까지의 카드가 순서대로 있었다면 1,4,7...,25 / 2,5,8 ...,26/3,6,9 ...,27 와 같이 순서대로 하나씩 3 그룹으로 분리한다.) 그런 후 카드를 선택했던 관객에게 아까 골랐던 카드가 어느 무더기에 들어갔는지 물어본다. 관객이 고른 무더기를 다른 두 무더기 사이에 집어 넣은 다음 카드를 섞지 않은 채 아까처럼 세 무더기로 나눠 놓는다.(예를 들어 첫번째 그룹에 들어 있었다면 2,5,8,...26/1,4..

길이가 100인 막대를 잘라 길이가 1인 조각 100개를 만들어야 한다. 여러 조각을 한꺼번에 자를 수 있다고 가정할 때 자르는 최소 횟수는 몇번인가? 막대의 길이가 n일때 최소 횟수만에 자르는 알고리즘을 설명하라. 문제출처) 길벗 - 알고리즘 퍼즐 문제풀이) 이 문제는 정보올림피아드 예선 문제에 자주 출제되는 유형으로 다음과 같이 절반씩 잘라 가는 유형으로 생각하면 됩니다. 100 = 50 * 2 50 = 25 * 2 25 = 13 + 12 (여기서 13 크기를 기준으로 생각함) 13 = 7 + 6 (여기서 7 크기를 기준으로 생각함) 7 = 4 + 3 (여기서 4 크기를 기준으로 생각함) 4 = 2*2 2 = 1*1 즉 7번이면 100인 막대를 1 크기로 모두 자를 수 있습니다. 여기서 아이디어는 절..

세계 과학의 역사라는 책을 준비 중인 편집자가 주요 과학자가 가장 많이 살아 있던 시기를 알아 보려고 한다. 여기서 주요 과학자는 그 책에 출생연도와 사망연도가 모두 기록된 과학자로 정의한다.(그 책에 살아 있는 과학자는 수록되어 있지 않다) 책의 색인을 입력 받아 이 작업을 처리해보자. 만약 A가 사망한 해에 B가 새로 태어났다면 A의 사망시점이 B의 출생 시점보다 앞선다고 가정하자. 문제 출처)길벗출판사- 알고리즘 퍼즐 문제풀이) 이 문제는 자료구조의 count배열을 사용하여 해결이 가능하다. 예를 들어 다음과 같이 (태어난 해,사망한해)의 형태로 데이터가 입력 되었다고 가정해 보자. A(1,9),B(4,7),C(2,10),D(7,11),E(3,12) 태어난 해에는 +1,사망한 해에는 -1로 표기를 ..