본문 바로가기

알고리즘

[백준 알고리즘/Python] 11726 2×n 타일링
알고리즘/백준알고리즘 2022. 1. 28. [백준 알고리즘/Python] 11726 2×n 타일링 문제 문제 이해 그림을 그려보았습니다. 3일 때는 2x2 타일 수와 2x1의 타일수를 더하면 되었고 4일 때는 2x3 타일과 2x2 타일의 수를 더하면됐습니다. n-1의 도형에다가 2x1를 하나 추가시킨 개수와 n-2의 도형에다가 1x2를 2개 추가시킨 개수를 더하면 됩니다. 코드 num = int(input()) d = [0] * (num+1) if num
[백준 알고리즘/Python] 1463 1로 만들기
알고리즘/백준알고리즘 2022. 1. 27. [백준 알고리즘/Python] 1463 1로 만들기 문제 문제 이해 처음 DP를 만나서 어떻게 접근해야할지 몰랐습니다.메모이제이션 기법을 이용해야한다고 하는데 이전의 결과를 이용해야한다? 부터 어려웠습니다. 그림을 그려 살펴보니 이해가 되었습니다. 예를 들어 6이란 수를 1로 만들려면 위 예시 에서 2,3으로 나눠지지 않는 결과는 제외했습니다. ex) 5는 1빼는 방법밖에 없어서 4가 나왔습니다. 6에서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법 이 3가지를 모두 적용할 수 있습니다. 1이 나오기 과정까지 2,3이 반복해서 나오는 것을 확인할 수 있습니다. 그럼 2,3의 값을 어디다가 저장해두고 다른 수를 찾아보면 되겠지요. 빈 리스트의 i가 1를 변화 시킬 때 수는 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법 중 가장 작은 수를 ..
[백준 알고리즘/Python] 1212 8진수 2진수
알고리즘/백준알고리즘 2022. 1. 25. [백준 알고리즘/Python] 1212 8진수 2진수 문제 문제이해 저번에 풀었던 2진수 -> 8진수와 비슷합니다. 이번에는 내장함수를 이용해서 풀어봤습니다. 8진수로 입력을 받고 -> bin()으로 2진수를 만듭니다. 코드 num = int(input(),8) print(bin(num)[2:]) int(문자열,진수) -> 8진수로 받고 bin(정수) -> 2진수로 만듭니다. 이때 str형태이니 문자열 자르기를 이용해 줍니다.
[백준 알고리즘/Python] 1373 2진수 8진수
알고리즘/백준알고리즘 2022. 1. 24. [백준 알고리즘/Python] 1373 2진수 8진수 문제 문제이해 문자를 받아와서 오른쪽부터 3개씩 끊어서 8진수를 얻는 것을 생각했습니다. 그런데 문자가 1,2개 남으면 앞에 0을 붙혀줘야하니 [0,0]을 붙혀주는 것으로 처리를 했습니다. 코드 binary = list(map(int,input())) result = "" for i in range(0,len(binary),3): if(len(binary)
[백준 알고리즘/Python] 17087 숨박꼭질6
알고리즘/백준알고리즘 2022. 1. 23. [백준 알고리즘/Python] 17087 숨박꼭질6 문제 문제 이해 수빈이의 위치 S에서 각 동생의 위치의 절대값을 구하면 수빈이가 얼마나 이동해야하는지 알 수 있습니다. ex) 수빈이가 3에 있고 동생이 1, 7 11에 있으니 [ 2, 4, 8 ]만큼 움직이면 됩니다. [ 2, 4, 8 ]에서 시간을 고려하지 않고 모든 동생을 찾으려면 2씩 움직이면 됩니다. 즉, [ 2, 4, 8 ]에서 최대공약수를 구하면 됩니다. 코드 N,S = map(int,input().split()) children = list(map(int,input().split())) li = [] result = 0 def 최대공약수(num1, num2): #num1이 num2보다 크게 if(num1 < num2): a = num1 num1 = num2 num2 = a while((nu..
[백준 알고리즘/Python] 2004 조합 0의 개수
알고리즘/백준알고리즘 2022. 1. 20. [백준 알고리즘/Python] 2004 조합 0의 개수 문제 문제이해 조합 ( nCr ) 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 이렇게 풀면 시간초과가 나옵니다. 도저히 다른 방법이 생각이 안났습니다. 다른 사람 풀이의 힌트를 보았고 0의 개수를 출력한다는 것은 10의 배수를 측정하는 것과 같았습니다. 그렇다면 m!과 n!, (m-n)!의 2의 개수와 5의 개수를 구하면 됩니다. 하지만 다시 팩토리얼을 돌면 시간초과가 날것이니 다른 방법이 필요 합니다. 25! = 15511210043330985984000000 입니다. 10의 배수는 6개 있죠. 2와5는 무조건 6쌍을 필요로 합니다. 즉, 한 숫자 팩토리얼의 5의 개수를 알고 싶다면 몫을 계속 5로 0이 될 때 까지 수를 저장합니다. ex) 25 => [ 5..
[백준 알고리즘/Python] 1676 팩터리얼 0의 개수
알고리즘/백준알고리즘 2022. 1. 19. [백준 알고리즘/Python] 1676 팩터리얼 0의 개수 문제 문제 이해 처음에 '뒤에서부터 처음 0이 아닌 숫자가 나올때까지' 가 무슨뜻인지 몰랐습니다. 예시를 보니 10! = 3628800 입니다. 오른쪽에서 2칸 떨어져있다는 뜻이였습니다. 3! = 6 은 0이 없으니 0의 개수는 0개 입니다. 코드 input = int(input()) def factorial(n): ans = 1 for i in range(1, n+1): ans *= i return ans result = list(str(factorial(input))) answer = 0 for i in range(1, len(result) + 1): if(result.pop() == "0"): answer += 1 else: print(answer) break 팩토리얼 함수는 처음에 제귀로 했다가 ..
[백준 알고리즘/Python] 6588 골드바흐의 추측
알고리즘/백준알고리즘 2022. 1. 18. [백준 알고리즘/Python] 6588 골드바흐의 추측 문제이해 예전에 풀어본 골드바흐 문제와 비슷합니다. 에라토스테네스의 체로 리스트를 소수화 합니다. 그리고 3부터 소수를 찾아서 가장 먼저 찾은 소수와 주어진 수를 빼서 그게 소수이면 그 조합이 답이 됩니다. 8 예를 들어 보겠습니다. 3부터 소수 찾으면 8에서 3을 빼봅니다. 5는 소수입니다. -> 짝수도 아닙니다. -> 출력합니다. 코드 import sys a = [False, False] + [True] * (1000000) #에라토스테네스의 체로 리스트a를 조정한다. for i in range(2, 1000000): if(a[i]): for j in range(i*2, 1000000, i): a[j] = False #여기서 리스트 a는 소수만 True #소수를 구하는 함수 def prime_num(..
[백준 알고리즘/Java] 2609 최대공약수와 최소공배수
알고리즘/백준알고리즘 2022. 1. 13. [백준 알고리즘/Java] 2609 최대공약수와 최소공배수 문제이해 2개의 수를 입력받고 for문으로 1부터 증가하면서 2개의 수가 동시에 나머지가 0인 구간은 최대공약수로 생각했고 2개의 수중 작은 수를 시작으로 1부터 곱해가면서 그 결과가 동시에 나머지가 0이 나올 때까지 반복하겠다고 생각했습니다. 코드 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String[] Num = br.readLine().split(" "); int num1 = Integer.parseInt(Num[0]); int nu..

티스토리툴바