UVA10003 막대 자르기 나무 막대를 여러 조각들로 잘라야만 한다. 가장 적당한 업체인 아날로그 벌목 공업사는 잘라야 될 막대의 전체 길이에 따라서 돈을 청구한다. 이들의 작업 절차는 한 시간에 한번만 자를 것을 요구한다. 자르는 순서를 달리하면 다른 조각들이 만들어질 수 있다. 예를 들어, 끝에서 2, 4, 7 미터에서 자를 수 있는 길이 10 미터의 막대기를 생각해 보자. 자르는 순서는 몇 가지가 있을 수 있다. 이럴 경우 처음 막대는 10 미터였으며, 자른 이후에는 8 미터에서 다음 4를 잘라야 하며, 마지막 한번 자르려면 6의 막대에서 자르므로, 10 + 8 + 6 = 24 의 돈을 막대 자르는 데 지출해야 한다. 또 다른 방법은 먼저 4에서 자르고, 다음은 2에서 자르면 4에서 2를 자르고,..
떡 먹는 호랑이 하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머..
가족 찾기 그래프는 아주 쉬운 문제에서부터 까다로운 문제까지 해결의 실마리를 제공한다. 유명한 외판원 문제나 최소 신장 트리 문제는 아주 어려운 문제이지만 그래프에 효과적인 알고리즘을 적용하여 해결된다. 이번 문제에서는 기본적인 그래프 탐색에 관해 학습하고 자 한다. 문제 ( 난이도 ★★☆☆☆) 건수네 학교에서 부모님들과 학생들이 모두 참석한 행사를 하고 있다. 행사 중 모든 사람 들이 모여서 할 수 있는 놀이 중 가족 찾기가 있다. 다만 놀이에 모든 사람이 포함되는 것은 아니고 정사각형을 만들 수 있는 일부 사람들이 놀이에 참가한다. 놀이의 규칙은 다 음과 같다 같은 가족이면 서로 좋아해야 한다. 같은 가족은 2명 이상이다 다른 가족은 서로 싫어한다. 좋아하는 사람을 표시할 때는 1을 표시하고 싫어하는..
거듭 제곱 구하기 우리가 사용하는 C 혹은 C++, 비주얼 베이직 같은 프로그램 언어들은 각자 사용하는 자료형을 가지고 있고 자료형들은 일정한 크기를 갖는다. 따라서 이 자료형을 이용하여 큰 수 혹은 자료를 계산하는데는 한계가 있다. 이번 문제에서는 큰 수의 처리에 관한 학습을 하고자 한다. 문제 ( 난이도 ★★★☆☆ ) 컴퓨터는 복잡한 계속을 빠르고 쉽게 해결해 준다. 그런데 숫자가 매우 커지면 문제가 발생한다. 예를 들어 여러분이 만약 프로그램에서 Visual C++을 사용한다면 int 형 변수는 10자리 이상을 표현하지 못한다. 다른 프로그램 언어도 마찬가지로 자료형마다 표현 할 수 있는 최대 크기가 정해져 있다. 그렇다면 10자리 이상 혹은 매우 긴 자리 이상의 계산은 어떻게 할 수 있을까. 예를..
- Total
- Today
- Yesterday