1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 2 예제 출력 1 1 예제 입력 2 10 예제 출..
1. 개요 Dynamic Programming, 즉 동적계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다. 즉, 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 것이다. 2. DP를 쓰는 이유 일반적인 재귀 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 f(n) = f(n-1) + f(n-2)이다. 위 피보나치 수열 함수 트리를 보면 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고..
빅오란, 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이를 이용하여 알고리즘의 시간과 공간복잡도를 표현할 수 있다. 1. O(1), constant time 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 의미한다. def array_zero(n): return (n[0] == 0) 위 함수를 보면 입력 데이터인 n의 0번째 인덱스의 숫자가 0이면 True를 0이 아니면 False를 반환한다. 이는 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다. 2. O(n), linear time 입력 데이터의 크기와 비례하여 처리 시간이 걸리는 알고리즘을 의미한다. def array_print(n): for i in range(n): print(i) 위 함수를 보면 n이 하나..
2007년 https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 문제 오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지,..
A+B-4 https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 각 테스트 케이스마다 A+B를 출력한다. 예제 입력 1 1 1 2 3 3 4 9 8 5 2 예제 출력 1 2 5 7 17 7 코드 while True: try: a, b = map(int, input().split()) print(a + b) exce..
