본문 바로가기

알고리즘

 (138)
[BOJ] [Python] 10872번 : 팩토리얼 팩토리얼은 n! = n * n -1 * ... * 1 이다. ( 0! = 1 ) num = int(input()) def recursion(n): if n == 0 or n == 1: return 1 else: return n * recursion(n - 1) print(recursion(num))
[BOJ] [Python] 2110번 : 공유기 설치 이진탐색을 이용하여 풀었다. low는 '공유기와 집' 사이의 최소 간격, high는 최대 간격으로 잡았다. ※ 현재 mid 값에 설치된 공유기 개수 찾기 '집 위치 - 공유기가 설치된 지점'가 mid보다 크다면 설치가 가능하다. n개의 집에 몇 개의 공유기가 설치될 수 있는 가? => 현재 mid 값으로 설치된 공유기 개수 >= 설치해야 할 공유기 개수라면? : mid값이 작은 것이다. 즉, 간격이 좁은 것이다. 간격을 더 늘려도 된다. (만약, 개수가 같아서 혹은 개수를 더 줄일 수 없다면 result값에 저장해놓은 값을 출력한다.) => 현재 mid 값에 설치된 공유기 개수 < 설치해야 할 공유기 개수라면? : mid값이 큰 것이다. 즉, 간격이 넓은 것이다. 간격을 더 좁혀도 된다. num = li..
[BOJ] [Python] 1072번 : 게임 이진탐색을 이용하여 풀었다. 이 문제는 주의해야 할 점이 있다. 첫 번째, int(y + mid / (x + mid ) * 100)는 안된다. (100 * (y + mid)) // (x + mid)는 된다. 똑같은 의미인데 .. 왜일까? Python은 부동소수점 오차가 있어서, 정확하지 않다고 한다. (다음부터 풀 때는 이 점을 주의해야겠다!) 두 번째, 입력이 몇 줄인지 정확히 명시하지 않았다. 그러므로 예시처럼 한 줄일거라고 생각하지 말고, N개의 줄에 대비해야 한다. high 값을 잡기가 애매했다. 그래서 문제에서 명시해준 최대인 10억을 잡았다. def BSearch(x, y, z): low = 1 high = 1000000000 while low z: high = mid - 1 else: # n..
[BOJ] [Python] 2512번 : 예산 이진탐색을 이용하여 풀었다. low는 0으로, high는 예산의 최댓값으로 잡았다. n = int(input()) region_p = sorted(list(map(int, input().split()))) max_p = int(input()) def BSearch(r_p, m_p): low = 0 high = r_p[-1] result = 0 while low m_p: high = mid - 1 else: result = mid low = mid + 1 return result print(BSearch(region_p, max_p)) return을 하나만 작성할 경우, 이렇게도 가능하다. n = int(input()) region_p = sorted(list(map(int, input().split())..
[BOJ] [Python] 13706번 : 제곱근 이진탐색을 이용하여 풀었다. num = int(input()) def BSearch(num): low = 0 high = num while low num: high = mid - 1 else: low = mid + 1 return -1 print(BSearch(num))
[이진 탐색] 이진 탐색[Binary Search] 정렬된 배열에서 특정 값을 찾아내는 알고리즘이다. 위 설계를 옮긴 코드이다. def BSearch(array, check): low = 0 high = len(array) -1 while(low check): high = mid - 1 else: low = mid + 1 return -1 시간복잡도는 O(logN)이다. 응용 문제 sojeong-lululala.tistory.com/14 [BOJ] [Python] 13706번 : 제곱근 이진탐색을 이용하여 풀었다. num = int(input()) def BSearch(num): low = 0 high = num while low num: high = mid - 1 else: lo.. sojeong-lululala.tistory.com
[BOJ] [Python] 2581번 : 소인수분해 나머지가 0일 때까지, 2부터 N까지 나누어서 그 몫을 다시 N으로 해주는 방법으로 풀었다. num = int(input()) result = [] boo = True while(boo): if(num != 1): for n in range(2, num+1): if num % n == 0: print(n) num = num // n if num == 1: boo = False break else: break 같은 방법인데, 더 짧고 간단한 풀이이다. 사진 출처
[BOJ] [Python] 2581번 : 소수 1978번 소수 찾기와는 조금 다른 방법으로 풀었다. 2부터 N-1까지 나누어서, 0으로 떨어진다면 소수가 아니라고 판정하는 식이다. start = int(input()) end = int(input()) result = [] for num in range(start, end+1): if(num != 1): dec = True for n in range(2, num): if num % n == 0: dec = False break if(dec): result.append(num) sum_result = sum(result) if (sum_result): print(sum_result) print(result[0]) else: print(-1)
[BOJ] [Python] 1978번 : 소수 찾기 소수는 1과 자기 자신밖에 없는 수이다. 이를 이용하면 2가지 방법으로 풀 수 있는데, 1. 소수^2 < 1000인 소수를 이용 (에라토스테네스의 체) 2. 약분 1번 방법 n = int(input()) num = map(int, input().split()) prime_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] count = 0 for find_num in num: if find_num != 1: if find_num in prime_list: count += 1 else: for p in prime_list: if find_num % p == 0: break elif prime_list[-1] == p: count += 1 print(count) 2번 방법 ..
[BOJ] [Python] 2869번 : 달팽이는 올라가고 싶다 시간 초과를 신경 써야 하는 문제이다. 아래 코드처럼 구현하게 되면, 위 예시가 정말 오래 걸린다. (a와 b의 차이가 얼마 안 나기 때문이다.) num = list(map(int, input().split())) a = num[0] b = num[1] v = num[2] count = 1 result = a while(v > result): result -= b result += a count += 1 print(count) 위 코드를 식으로 표현하자면, a * n - b * (n - 1) >= v 이렇게 나온다. 정리하면, n >= (v - b) / (a - b) >= 를 처리하기 위해 math 모듈을 이용해 '올림' 처리 해주었다. import math num = list(map(int, input..

티스토리툴바