원당컴퓨터학원

문제 크기와 모양이 똑같은 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로 표기를 ..

1부터 시작해 순차적으로 쪽번호를 어떤 책에 매기고 있다. 쪽 번호를 붙이는데 숫자를 1581개 썼다면 그 책은 몇쪽짜리 책인가? (예 123 페이지 쪽 번호를 붙였다면 숫자를 1,2,3 세개를 사용한 것이다.) [문제출처] 길벗 - 알고리즘퍼즐 문제풀이) 1~9 까지는 9개의 숫자를 사용한다.(총 9개 - 남은 갯수 1572) 10~99까지는 2개씩 90개의 수이므로 180개를 사용한다.(총 189개 - 남은 갯수 1392) 100~999 까지는 3개씩 900개의 수이므로 2700개를 사용한다. 100 부터 1392개를 사용한 경우이므로 1392를 3으로 나누면 464개가 된다. 100부터 464번째이므로 563 쪽이 된다.(100부터 1번째 쪽수는 100이므로 464번째는 563쪽이다.) 이것을 c언..

팬 케이크를 한번에 두개만 구울 수 있는 팬으로 1이상 n개의 팬 케이크를 만들어야 한다. 모든 팬 케이크는 양쪽을 모두 구워야 하며 한쪽 면을 굽는데 1분이 걸리는데 한장을 굽든 2장을 굽든 시간은 똑같다. 최단 시간에 팬 케이크를 모두 굽는 알고리즘을 설계해 보자. 문제풀이) n=1 일때는 무조건 2분이 걸린다. n=2 일때도 역시 2분이 걸린다. n=3 일때는 1,2 를 앞면 구운 다음 1의 뒷면과 3의 앞면을 굽는다. 그 다음 2의 뒷면과 3의 뒷면을 굽는다. 따라서 3분이 걸린다. n=4 일때도 4분이 걸린다. n=5 일때 역시 n=2를 먼저 2분에 처리하고 나머지 3개를 같은 방법으로 3분에 굽기 때문에 결국은 n 분이 걸린다. 결국은 n이 1보다 큰 경우에는 모두 n분에 구울 수 있다. c언..

길동이가 사는 마을은 7일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 8일에 열립니다. 원당이가 사는 마을은 5일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 6일에 열립니다. 길동이가 사는 마을과 원당이가 사는 마을에서 오늘 장이 열렸습니다. 그렇다면 몇일 후에 길동이가 사는 마을과 원당이가 사는 마을에서 같은 날짜에 장이 열릴까요? 문제풀이) 이 문제는 5와 7의 최소 공배수를 찾는 문제입니다. 최소 공배수를 찾는 알고리즘은 a * b / 최대공약수(a,b) 입니다. 최대공약수를 찾는 알고리즘은 유클리드 호제법을 이용해서 a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다고 정의 할 수 있습니다. 따라서 최대공약수를 구하는 알고리즘을 C언..