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자리 이상 혹은 매우 긴 자리 이상의 계산은 어떻게 할 수 있을까. 예를..
Hamilton Circuit 해밀턴 회로는 모든 정점을 방문하여 처음 출발점으로 돌아 오는 회로이다. 해밀턴 회로를 사용하려면 일단 그래프를 배열로 표현해야 한다. 만일 다음과 같은 그래프가 있다고 하자 그래프는 2차원 배열로 나타내게 된다. 간선이 연결된 곳은 1, 그렇지 않은 곳은 0으로 저장한다. 위의 그래프를 배열로 표현하면 다음과 같다. 1 2 3 4 1 0 1 1 0 2 1 0 1 1 3 1 1 0 1 4 0 1 1 0 해밀턴은 정점을 두 번이상 방문하지 않아야 하므로 처음 false 로 해두었다가 한번 방문하면 true로 바꾸어 정점을 체크하는 것만 오일러 코드에 추가하면 해밀턴 코드가 된다. 해밀턴 회로에 대한 입력 예제가 다음과 같다. 입력 4 5 1 2 1 3 2 3 2 4 3 4 출..
이번엔 데큐라는 것에 대한 포스팅입니다. 쉽게 설명하자면 데큐는 큐를 발전시킨건데 앞뒤로 입력이 가능한 구조 입니다. --------------------------------- → ← ← → --------------------------------- 백번 설명하는 것 보다 직접 해보시는게 더 빠를거예요. push_back(원소)는 원소를 뒤에 삽입한다는 것이고 pop_front(원소)는 가장 앞의 원소를 삭제한다는 것입니다. front()는 가장 위의 원소이고 empty()는 데큐 안이 비었는지 확인하는 함수입니다. 아 참고로 deque는 헤더파일이 따로 있으므로 #include가 꼭 필요하고 using namespace std 역시 필요하다는 것을 잊지 마세요. 입력예제 5 1 1 1 0 0 0 0..
[초등부] 기말 고사 준비 정보 올림피아드 문제에서 가장 쉽게 접할 수 있는 문제는 최적해를 구하는 것이다. 최적해를 구하는 것은 발생할 수 있는 모든 경우를 고려한 후 답을 구할 수 도 있지만, 수행 시간 문제가 발생한다. 이번 문제에서는 최적해 문제의 해결에 접근하는 방법을 학습 하고자 한다. 문제 ( 난이도 ★★★☆☆ ) 인표는 기말 고사를 앞두고 있다. 지난 중간고사 때 감기몸살로 공부를 제대로 하지 못해 성적이 저조했다. 그래서 인표는 기말고사를 더욱 중요하게 생각하고 있다. 그러나 불행히도 인표에게 주어진 시간은 그리 많지 않다. 인표는 자신에게 주어진 시간을 최대한 효율적으로 사용하여 기말고사에서 최대의 효과를 보려고 그 동안의 경험과 친구들의 조언을 토대로 다음과 같은 표를 만들어 보았다...
게임하지마라 망한다 수학 공부 해라 수능 안칠거란 소리를 하진 않겠지 나도 이 말 선배님들한테 들었었다. 당근 나는 안 지켰고 니들한텐 지키라고 얘기하고 있지. 아마 너희들도 대부분이 못지킬거임. 100%임. 확실하다. 왜냐하면 우리 반에서도 지킨애들이 거의 없거든. 걍 내가 바라는 점은 자각만 하고 있으면 됨. 그럼 언젠간 바뀔거다. c,c++ 좀 배웟다고 우쭐대지마라. 그게 다가 아니다. 나도 허접이지만 나보다 1년 느린 너희들이 나보다 잘할거라 생각하지 않음. (나보다 잘난 사람한텐 미안 ^ㅅ^) 내가 잘난게 아니라 우리가 어리기 때문에 그런거다. 그리고 c,c++이 다가 아니다. 적을려면 끝도 없진 않지만 엄청 많고, 어차피 고등학교 1,2,3학년 동안 하루 16시간 프밍만 한다고 해도 현재 있는..
- Total
- Today
- Yesterday