본문 바로가기

알고리즘/백준

 (64)
[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))
[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..
[BOJ] [Python] 2292번 : 벌집 벌집의 라인마다 숫자의 끝만 보면 수열이 보인다. 1, 7, 19, 37, 61 ... A(n) = A(n-1) + 6 * (n-1) 즉, 6 6x2 6x3 6x4 ...인 등차수열을 포함하고 있다. num = int(input()) count = 0 first = 1 while(True): second = first + (6 * count) if(num == 1): print(1) break if first < num
[BOJ] [Python] 1260번 : DFS와 BFS BFS DFS 공부를 하면서 풀어봤다. DFS는 재귀함수, BFS는 deque를 이용했다. from collections import deque # 입력 num = list(map(int , input().split())) n = num[0] #정점 개수 m = num[1] #간선 개수 v = num[2] #시작 정점 check = [0] * n dic = {} for i in range(m): box = list(map(int, input().split())) if(check[box[0]-1] == 0): dic[box[0]] = [(box[1])] check[box[0] - 1] = 1 else: dic[box[0]].append(box[1]) if(check[box[1]-1] == 0): dic[b..
[BOJ] [Python] 2775번 : 부녀회장이 될테야 간단한 예시를 만들어 작성하면서, 어떻게 문제를 풀어야 할 지 생각했다. 그렇게 떠올린 방법은 '재귀함수 사용' loop = int(input()) #test def people(a, b): global result if(a == 0): return b else: for i in range(1, b+1): tmp = people(a - 1, i) if(tmp != None): result += tmp for i in range(0, loop): k = int(input()) # k층 n = int(input()) # n호 result = 0 people(k, n) print(result) 사실, 이렇게 재귀함수를 사용하면 best 방법은 아니다. 한 번 방문했던 곳은 방문하지 않는 게 좋기 때문이다. p..

티스토리툴바