본문 바로가기

BOJ(백준 문제풀이)

 (22)
백준 10870 피보나치 수 5 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net 1. 피보나치 수열의 식을 이해하기 문제에 나와있는 피보나치의 수열의 식을 보면 n번 째 항은 (n - 1)번 째항과 (n -..
백준 10872 팩토리얼 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 1. 팩토리얼의 정의 생각해보기 n!은 n부터 1까지의 곱 ex) 4! = 4 × 3 × 2 × 1 반복문으로 구현 가능하지만 이번에는 재귀로 구현해 보겠습니다. 재귀란 어떤 것을 정의할 때 자기 자신을 참조하는 것을 말합니다. 이 코드의 경우에는 factorial()함수 안에 다시 factorial()을 호출하는 것을 볼 수 있습니다. 이와 같이 함수 안에서 다시 자기 자신을 호출하는 함수를 재귀 함수라고 합니다. 1 2 3 4 5 6 7 def factorial(n): if n == 1 or n ..
백준 1929 소수 구하기 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net 소수의 정의를 생각해보기 n의 약수의 범위 생각해보기 소수란 1과 자기 자신만을 약수로 가지는 수를 말한다. 이 문제의 경우 에라토스테네스의 체의 방법을 응용하여 해결하였다.(시간 초과 때문에) 에라토스테네스의 체는 2부터 시작하여 우선 2의 배수를 모두 지운다. 2는 소수로 놔둔다 3의 배수를 모두 지운다. 3은 2와 마찬가지로 소수로 놔둔다. 4는 2의 배수로 지워지고 다음 수인 5의 배수를 모두 지운다. 이러한 방식으로 마지막에 남아있는 수가 소수가 되는 방법이다. 1 2 3 4..
백준 1002 터렛 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 좌표(x1, y1, x2, y2)와 거리(r1, r2)로부터 원의 중심과 반지름을 떠올린다. 두 개의 원이 동시에 지나는 점(접점)의 개수를 생각해본다. 접점은 최대 2개가 될 수 있다. 접점이 3개가 될 경우는 존재하지 않고 두 원이 같은 경우 접점이 무한대가 되기 때문에 -1을 출력한다 두 원의 중심의 거리를 구할 때는 제곱근을 사용하지 않는다. python의 math 모듈에 있는 sqrt()는 근삿값을 구하기 때문에 오차를 없애기 위해 반지름도..
백준 3053 택시 기하학 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |y1-y2| 두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다. 따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다. 원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합 www.acmicpc.net 택시 기하학의 이해(택시 기하학에서의 원) 택시 기하학에서의 원의 넓이 구하기 택시 기하학에서의 원은 중심을 원점이라고 했을 때 (|x..
백준 4153 직각 삼각형 solution[python, 파이썬] - 풀이, 설명::FBTT https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 문제 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오. 입력 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. 출력 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다. 예제 입력 1 복사 6 8 www.acmicpc.net 직각 삼각형의 조건을 생각해 본다 피타고라스의 정리 적용 항상 세 변이 크기 순서 대로 입력된다는 조건이 없어 세 변의 list를 정렬해..

티스토리툴바