[백준 10870번-파이썬/Python] 피보나치 수 5

http://acmicpc.net/problem/10870 {코드} def fibo(n): if n < 2: return n else: return fibo(n-1) + fibo(n-2) print(fibo(int(input()))) {설명} 피보나치 수열은 0과 1로 시작하며 바로 앞의 두 수를 더한 값이 다음 피보나치 수가 되는 수열입니다. 그렇기에 n번째 피보나치 수는 n-1번째와 n-2번째 수의 합이 되므로 위와 같이 구성됩니다. 만약 4번째 피보나치 수를 구한다고 하면 아래와 같이 구성됩니다. (무시하고 더 내리셔도 됩니다.) n = 4 4는 2 보다 작지 않음 3번째 피보나치 수를 찾음 3은 2보다 작지 않음 2번째 피보나치 수를 찾음 2는 2보다 작지 않음 1번째 피보나치 수를 찾음 1은 2..

→2020.12.20

알고리즘 공부/BOJ백준 풀이

[백준 10872번-파이썬/Python] 팩토리얼

http://acmicpc.net/problem/10872 {코드} def factorial(n): if n < 2: return 1 return n * factorial(n-1) print(factorial(int(input()))) {설명} 팩토리얼은 n부터 1까지의 곱으로 5의 경우 5*4*3*2*1=120입니다. 팩토리얼은 반복문으로도 풀 수 있으나 재귀라는 문제의 의도를 살려 재귀로 풀었습니다. 아래는 반복문을 활용한 방법입니다. #반복문 ans = 1 for n in range(int(input(), 1, -1): ans *= n print(ans) *숫자 여러 개의 팩토리얼을 구하라는 문제는 동적 계획법이라는 방법을 통해서도 구할 수 있습니다.

→2020.12.19

알고리즘 공부/BOJ백준 풀이

[백준 1002번-파이썬/Python] 터렛

http://acmicpc.net/problem/1002 {코드} for _ in range(int(input())): x1, y1, r1, x2, y2, r2 = map(int, input().split()) d = (x1-x2)**2 + (y1-y2)**2 rad_sum = (r1 + r2)**2 rad_dif = (r1 - r2)**2 if d == 0: if r1 == r2: print(-1) else: print(0) else: if d in [rad_sum, rad_dif]: print(1) elif rad_dif < d < rad_sum: print(2) else: print(0) {설명} 어떤 점이 주어졌을 때 그 점에서 일정한 거리에 있는 점들은 원을 형성합니다. 즉, 두 점은 원의 중심..

→2020.12.18

알고리즘 공부/BOJ백준 풀이

[백준 3053번-파이썬/Python] 택시 기하학

http://acmicpc.net/problem/3053 {코드} r = int(input())**2 print(r*3.14159265359) print(r*2) {설명} 이 글에서 택시 기하학이 무엇인지는 따로 설명하지는 않겠습니다.(저도 몰라요) 다만, 택시 기하학에서의 거리는 직선거리가 아닌 거쳐야 하는 선의 개수라는 것만 아시면 됩니다. 택시 기하학에서의 원은 다음과 같이 생겼고 거리는 검은색 선의 길이가 중심으로부터의 거리가 됩니다. 이렇게 격자에서 선으로만 이동할 때의 거리라고 생각하면 원의 넓이는 반지름의 제곱*2가 됩니다. *math 라이브러리에서 pi를 가져오는 대신 근사값을 넣었는데 저 값보다 자릿수가 적으면 틀렸다고 뜨니 주의하세요.

→2020.12.18

알고리즘 공부/BOJ백준 풀이

[백준 4153번-파이썬/Python] 직각삼각형

http://acmicpc.net/problem/4153 {코드} while True: data = list(map(int, input().split())) if data[0] == 0: break a = max(data) data.remove(a) if a**2 == data[0]**2 + data[1]**2: print('right') else: print('wrong') {설명} 정상적인 입력은 양의 정수들로만 입력되므로 만약 0이 포함되어 있으면 반복문을 나오면 된다. 그리고 최댓값을 찾아 직각삼각형의 특징 중 하나인 a^2 = b^2 + c^2가 만족하는지 확인하여 맞으면 'right', 틀렸다면 'wrong'을 출력하면 된다.

→2020.12.18

알고리즘 공부/BOJ백준 풀이

[백준 3009번-파이썬/Python] 네 번째 점

http://acmicpc.net/problem/3009 {코드} x, y = [], [] for _ in range(3): n, m = map(int, input().split()) x.append(n) y.append(m) for i in x: if x.count(i) == 1: print(i, end=' ') break for i in y: if y.count(i) == 1: print(i) break {설명} 주어진 세 점 중 중복이 없는 것을 찾는 문제이므로 x좌표들과 y좌표들 중 개수가 하나인 것을 골라 출력하면 됩니다.

→2020.12.17

알고리즘 공부/BOJ백준 풀이

[백준 1085번-파이썬/Python] 직사각형에서 탈출

http://acmicpc.net/problem/1085 {코드} x, y, w, h = map(int, input().split()) print(min(x, y, w-x, h-y)) {설명} 주어진 직사각형은 x축, y축, x=w, y=h로 이루어졌습니다. 즉, 각 경계선까지의 거리는 주어진 x, y, w-x, h-y이므로 이중 가장 작은 값을 출력하면 된다.

→2020.12.17

알고리즘 공부/BOJ백준 풀이

[백준 9020번-파이썬/Python] 골드바흐의 추측

http://acmicpc.net/problem/9020 {코드} data = [int(input()) for _ in range(int(input()))] n = max(data) sieve = list(range(n+1)) sieve[0], sieve[1] = 0, 0 for i in range(2, n+1): if sieve[i]: for t in range(i+i, n+1, i): if sieve[t]: sieve[t] = 0 for n in data: p, q = n//2, n//2 while True: if sieve[p] and sieve[q]: print(p, q) break else: p -= 1 q += 1 {설명} 최대한 n을 이루는 수의 차가 작아야하므로 n의 절반에서 시작해서 n을..

→2020.12.17

알고리즘 공부/BOJ백준 풀이

[백준 4948번-파이썬/Python] 베르트랑 공준

http://acmicpc.net/problem/4948 {코드} sieve = [1]*246913 sieve[0] = 0 sieve[1] = 0 for i in range(2, 246913): if sieve[i]: for j in range(i+i, 246913, i): sieve[j] = 0 while True: n = int(input()) if n == 0: break print(sum(sieve[n+1:n*2+1])) {설명} 어떤 범위 안의 소수의 개수는 체에서 해당 범위의 1의 개수와 같고 이는 결국 해당 범위의 합과 같습니다.

→2020.12.17

알고리즘 공부/BOJ백준 풀이

[백준 1929번-파이썬/Python] 소수 구하기

http://acmicpc.net/problem/1929 {코드} def isPrime(n): if n

→2020.12.17

티스토리툴바