분류 전체보기 (171) 썸네일형 리스트형 [BOJ] [Python] 3079번 : 입국심사 이진탐색을 이용하여 풀었다. 이 문제의 난관은 'mid값의 중복' 이었다. 만약 mid가 8이라면, T(k) = 2, 4, 8 모두 8초까지 작업을 수행할 수 있다. 하지만 이 예제의 인원은 5명으로 제한되어 있기 때문에 T(k) = 2만 8초까지 수행한다. 이를 어떻게 해결해야 할까? '입국 심사를 통과해야 하는 인원[입력값] == 입국 심사를 통과할 예상 인원'이 아니라, '입국 심사를 통과해야 하는 인원[입력값] [BOJ] [Python] 2805번 : 나무 자르기 이진탐색을 이용하여 풀었다. mid가 작을수록 더 많은 나무를 가져간다. num = list(map(int, input().split())) n = num[0] # 나무 수 m = num[1] # 가져가야 할 나무 길이 tree = sorted(list(map(int, input().split()))) # 나무 길이 def BSearch(li, target): low = 1 # 자를 나무 최소 높이 -> 더 많이 가져감 high = li[-1] #자를 나무 최대 높이 -> 더 조금 가져감 result = 0 while(low [BOJ] [Python] 10870번 : 피보나치 수 5 피보나치 수열은 F(n) = F(n-1) + F(n-2) ( n >= 2 ) 이다. F(2) = F(1) + F(0)일 때, F(1) = 0, F(0) = 0으로 잡아준다. num = int(input()) def fibN(n): if n == 0: return 0 elif n == 1: return 1 else: return fibN(n-1) + fibN(n-2) print(fibN(num)) [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 같은 방법인데, 더 짧고 간단한 풀이이다. 사진 출처 이전 1 ··· 13 14 15 16 17 18 다음
