수학적 귀납법 "반복적인 구조를 갖는 명제를 증명하는 데 유용하게 사용되는 증명 기법" 귀납법 증명은 크게 세 단계로 나누어진다. (1) 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다. (2) 첫 단계 증명 : 그중 첫번째 단계에서 증명하고 싶은 내용이 성립함을 보인다. (3) 귀납 증명 : 첫번째 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다. 반복문 불변식 귀납법을 통해 알고리즘의 정당성을 증명할 때, 가장 유용하게 사용되는 개념이다. 반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 반복문이 마지막 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 하는 것이다. 반..

규칙 "만약 A,B,C 중에서 A에서 C로 원반이 이동해야 한다면, 가장 큰 원반을 제외한 나머지 원반들을 우선 B로 이동해야함" 어떠한 경우라도, 가장 큰 원반을 제외한 나머지 원반들은 목적지와 출발지를 제외한 나머지 축에 쌓아야 한다. 그리고 마지막 원반을 목적지에 가져다 놓은 후, 나머지 원반들을 다시 목적지로 이동시켜야 한다. 목적지로 이동할 때 또한, 위의 공식이 이뤄져야 한다. "만약 출발 축을 1, 목적지 축을 3이라고 한다면 나머지 축 2를 구하는 공식은 (1+2+3) - (3+1) 이다. " 즉, 모든 원반에서 출발 축과 목적지 축을 빼면 나머지 축이 나온다는 의미이다. 풀이 재귀 함수로 해당 문제를 푼다면, 세 가지 흐름을 이용하여 문제를 해결하면 된다. (1) 총 원반의 수가 n이라 ..

문제 시간 제한 : 0.15초 메모리 제한 : 128MB 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 풀이 문제 자체는 굉장히 쉽다. 프로그래밍 언어 책을 접하게 되면 늘 초반부에 등장하는 문제 중 하나인데 대신, 해당 문제는 시간 초가 걸려있..

문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 맞추기"이다. 이 방법은 단순하다. 원래 맞춰져있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다. 현재 상근이가 맞춰논 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 고쳐..

문제 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. 입력 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. 출력 각 테스트케이스마다 A+B를 한 줄에 하나씩 순서대로 출력한다. 예제 입력 1 5 1 1 12 34 5 500 40 60 1000 1000 예제 출력 1 2 46 505 100 2000 문제 풀이 일반적으로 입출력 기능을 구현하기 위해 Scanner 클래스를 사용한다. Scanner를 통해 입력을 받을 경우, Space와 Enter 모두를 경계로 인식하기에 입력받은 데이터..