알고리즘 공부

    [백준 2331번-파이썬/Python] 분해합
    알고리즘 공부/BOJ백준 풀이

    [백준 2331번-파이썬/Python] 분해합

    http://acmicpc.net/problem/2331 {코드} def func(): n = int(input()) m = max(n - 9*len(str(n)),0) for i in range(m, n): if n == sum(map(int, str(i)))+i: return i return 0 print(func()) {설명} 각 자릿수의 합을 구하기 위해 문자열의 각 인덱스마다 정수로 변환해서 그 합을 구한다. 거기에 기존의 수를 더한 결과가 타겟 수와 같으면 생성자 수이므로 이를 반환한다. 만약 반복문이 끝날 때까지 생성자를 찾지 못하면 0을 반환한다. 그리고 어떤 수에 대해서 생성자가 될 수 있는 최솟값은 n에서 9*(자릿수의 개수)를 뺀 값인데 0 이상이어야 하므로 0과 비교하여 더 큰 값부..

    [백준 2798번-파이썬/Python] 블랙잭
    알고리즘 공부/BOJ백준 풀이

    [백준 2798번-파이썬/Python] 블랙잭

    http://acmicpc.net/problem/2798 {코드} n, t = map(int, input().split()) data = tuple(map(int, input().split())) def blackjack(): ans = 0 for i in data[:-2]: for j in data[1:-1]: if i == j: continue for k in data[2:]: if j == k or i == k or i+j+k > t: continue if i+j+k == t: return t else: ans = max(ans, i+j+k) return ans print(blackjack()) {설명} 브루트 포스는 결국 모든 경우의 수를 전부 시도해보는 방법입니다. 그래서 3장의 카드를 고르기 ..

    [백준 11729번-파이썬/Python] 하노이의 탑 이동 순서
    알고리즘 공부/BOJ백준 풀이

    [백준 11729번-파이썬/Python] 하노이의 탑 이동 순서

    http://acmicpc.net/problem/11729 {코드} x = int(input()) print(2**x-1) def hanoi(n, p1, p2, p3): if n == 1: print(p1, p3) else: hanoi(n-1, p1, p3, p2) print(p1, p3) hanoi(n-1, p2, p1, p3) hanoi(x, 1, 2, 3) {설명} 이 문제는 파이썬 클래스님의 하노이의 탑 알고리즘 영상과 JW MATHIDEA님의 하노이의 탑 일반항 포스트(왜 총 이동 횟수가 2**x+1인지)를 참고하시기 바랍니다. 간단하게 설명하자면 하노이의 탑 문제는 각 원반이 일정한 규칙에 따라 움직이며 n은 n번 원반이며 p1은 현재 기둥, p2는 보조 기둥, p3는 이동할 기둥입니다. 그리..

    [백준 2447번-파이썬/Python] 별 찍기 - 10
    알고리즘 공부/BOJ백준 풀이

    [백준 2447번-파이썬/Python] 별 찍기 - 10

    http://acmicpc.net/problem/2447 {코드}n = int(input()) data = [['*']*n for _ in range(n)] def remove_stars(length, x, y): global data if length == 1: return for row in data[x-length+length//3: x-length//3]: row[y-length+length//3:y-length//3] = ' '*(length//3) for i in range(length//(length//3)): for j in range(length//(length//3)): remove_stars(length//3, x-i*length//3, y-j*length//3) remove_star..

    [백준 10870번-파이썬/Python] 피보나치 수 5
    알고리즘 공부/BOJ백준 풀이

    [백준 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..

    [백준 10872번-파이썬/Python] 팩토리얼
    알고리즘 공부/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) *숫자 여러 개의 팩토리얼을 구하라는 문제는 동적 계획법이라는 방법을 통해서도 구할 수 있습니다.

    [백준 1002번-파이썬/Python] 터렛
    알고리즘 공부/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) {설명} 어떤 점이 주어졌을 때 그 점에서 일정한 거리에 있는 점들은 원을 형성합니다. 즉, 두 점은 원의 중심..

    [백준 3053번-파이썬/Python] 택시 기하학
    알고리즘 공부/BOJ백준 풀이

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

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

    [백준 4153번-파이썬/Python] 직각삼각형
    알고리즘 공부/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'을 출력하면 된다.

    [백준 3009번-파이썬/Python] 네 번째 점
    알고리즘 공부/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좌표들 중 개수가 하나인 것을 골라 출력하면 됩니다.

티스토리툴바