1. 문제 - 6588번 2. 접근법 기존에 풀었던 에라토스테네스의 체를 활용해 풀 수 있었다. (참고 : 백준 문제 11653) 풀이 과정은 다음과 같다. - 우선 에라토스테네스의 체를 이용해 문제에서 주어진 범위(6 소수 집합 구하기 primes = [True]*n primes[0] = False primes[1] = False for i in range(2, int(n*0.5)+1): if primes[i]: for j in range(2*i, n, i): primes[j] = False return primes def test_goldbach(n, prime_list): for index, prime in enumerate(prime_list): # 짝수 n = 소수 a + 소수 b 일때, a와 ..
1. 문제 - 2004번 2. 접근법 이전 1676번 문제를 풀 때처럼 문자열을 활용한 방법으로 풀려 하니 도저히 풀리지 않았다. 계속 고민해봐도 방법을 모르겠어서 찾아보니, 다른 분들의 블로그에서 아래와 같은 원리를 활용해 문제를 풀 수 있었다. 1676번을 빠르게 푸는 방법을 알아야 이 문제를 풀 수 있다. 특히, 다음 블로그의 글이 이해하는데 도움이 되었다. https://lucian-blog.tistory.com/84 이 문제의 경우, - 문제가 의마하는 바는 n과 m의 조합 값이 가지는 0의 개수를 구하는 것 - 0의 개수를 구하기 위해서는 2와 5의 지수의 개수로 각각 0의 개수를 구할 수 있으며 그 중 작은 값을 찾아주면 됨(일종의 교집합) - n과 m의 조합 값에서의 0의 개수는 n!의 0..
1. 문제 - 1676번 2. 접근법 팩토리얼의 결과값에서 1의 자리부터 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제다.가령,5! = 120으로 0이 1개, 10! = 3628800으로 0이 2개 이런 식으로 계산된다. def factorial(num): factorial = 1 for i in range(num, 0, -1): factorial *= i return f'{factorial}'[::-1] def count_zero(num): fac = factorial(num) cnt = 0 for i in fac: if int(i) == 0: cnt += 1 else: break return cnt n = int(input()) print(count_zero(n)) 우선 첫번째 함수로 팩토리얼..
1. 문제 - 10872번 2. 접근법 기초적인 팩토리얼 문제다.반복문을 사용하면 간단하게 해결 가능하다. def factorial(num): factorial = 1 for i in range(num, 0, -1): factorial *= i return factorial n = int(input()) print(factorial(n))
1. 문제 - 11653번 2. 접근법 소인수분해를 하는 문제의 경우, 고민해보며 두가지 방법을 찾았다. - 주어진 수 n을 2부터 순차적으로 나누며 확인하는 방법으로 풀거나 - 에라토스테네스의 체로 n 이하의 소수 집합을 구한 후 소수를 순차적으로 나누거나 def prime_factor(num): if num == 1: print("") for i in range(2,num+1): while num != 1: if num%i == 0: print(i) num //= i else: break if n == 1: break n = int(input()) prime_factor(n) import sys from math import sqrt input = sys.stdin.readline def prime_..
1. 문제 - 1929번 2. 접근법 처음에 이전의 소수 구하기 문제처럼 생각하고 풀었다가, 몇번이고 시간 초과가 나왔다. 찾아보니 최대 공약수에 유클리드 호제법이 있는 것처럼, 소수 문제의 경우 에라토스테네스의 체라 불리는 일종의 노가다식 풀이법이 있다는 것을 알게 되었다. 노가다이지만, 가장 빠른 알고리즘이라는 것도. 왜 노가다인가 하면, 특정 조건( 2부터 √n 까지 의 수 중 하나라도 약수로 가진 수)을 걸어 소수에 해당하지 않는 수를 뭉텅이로 지워나가는 논리이기 때문이다. 내가 에라토스테네스의 체의 논리를 이해한 바는 이렇다. - 현재까지 검증된 방법 중, 소수를 찾는 가장 빠른 방법 - 특정 범위(ex. 1~n)까지의 소수를 알고 싶다면, n까지의 모든 수의 배수가 아니라 √n 까지만 나누어 ..
1. 문제 - 1978번 2. 접근법 주어진 수들 중에서 소수를 출력하는 문제다. 먼저 소수의 정의를 생각해보자. 소수란 '1과 자기 자신만을 약수로 가지는 수'이다. 이 점에 착안에 코드를 작성하면 아래와 같다. import sys input = sys.stdin.readline def prime_number(nums): prime_list = [] for num in nums: divs = [i for i in range(1,num)] cnt = 0 for i in divs: if num%i == 0: cnt += 1 if cnt == 1: prime_list.append(num) return len(prime_list) n = int(input()) numbers = list(map(int, inp..
1. 문제 - 11576번 2. 접근법 특정 진법이 먼저 주어지지 않고, 임의의 진법들이 주어졌을 때 상호 변환이 가능한 코드를 작성하는 문제다. 변환 전인 A진법의 각 숫자는 0으로 시작하는 경우가 없다고 했으므로, 이번 경우에는 0에 대한 처리는 생각하지 않아도 괜찮다.진법 간 변환을 쉽게 해주기 위해, A진수를 우선 10진수로 변환해준 뒤, 10진수를 나머지 원리를 이용해 B진수로 바꿔주는 코드를 작성했다.2초라는 제한 시간이 있으므로 빠른 속도를 위해 input 대신 sys 모듈을 사용해 표준입력값을 받았으며, append 메서드가 아닌 insert메서드를 사용해 출력 값을 첫 인덱스부터 삽입해주어 출력시 reversed등으로 뒤집을 필요가 없도록 했다. import sys input = sys...
1. 문제 - 2089번 2. 접근법 -2진법이란 개념에서 고민하다 찾아보니, 처음 생각한대로 원리는 가장 기본적인 진법 변환을 활용한 것이었다. 진법 변환은 나누는 수, 몫, 나머지의 관계애서 출발하므로, 이 문제도 -2를 나누는 수로 하고 나머지를 0 또는 1로 갖는 식으로 계속 나누어 주면 된다. 규칙을 좀더 직관적으로 파악하기 위해, 문제에서 주어진 수 중 9와 -13을 예시로 분석해보았다. 나머지를 반드시 0 또는 1로 만들면서, -2로 계속 나누어 보면 그 과정은 다음과 같다. -13 = -2*7 + 1 7 = -2*-3 + 1 -3 = -2*2 + 1 2 = -2*-1 + 0 1 = -1*1 + 1 1 = -2*0 + 1 13 의 결과값 : 1101119 = -2*-4 + 1 -4 = -2*..
1. 문제 - 1212번 2. 접근법 파이썬에서는 진법 변환이 가능한 내장 함수를 제공하기에 매우 간단하게 풀 수 있다. 2진법의 경우, bin 함수를 사용하면 된다. print(bin(int(input(), 8))[2:])
1. 문제 - 1373번 2. 접근법 1) 내장 함수 파이썬에서는 진법 변환이 가능한 내장 함수를 제공하기에 매우 간단하게 풀 수 있다. 8진법의 경우, oct 함수를 사용하면 된다. print(oct(int(input(),2))[2:]) 2) 진법 변환 원리를 코드로 구현 2진수의 세자리가 8진수의 한 자리가 된다는 원리에서 착안. 예를 들어, 문제에서 주어진 2진수 11001100을 끊어보면 11 / 001 / 100 이며 이걸 8진수로 나타내면 314가 된다. (계산은 0*2^2+1*2^1+1*2^0 / 0*2^2+0*2^1+1*2^0 / 1*2^2+0*2^1+0*2^0) 이런 원리를 코드로 구현하면 된다고 판단했다. import sys input = sys.stdin.readline def bin..