본문 바로가기

분류 전체보기

 (171)
[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..
[그래프 탐색] 깊이 우선 탐색[DFS], 너비 우선 탐색[BFS] 그래프 탐색 방법 1. 깊이 우선 탐색[DFS (Depth-First Search)] 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다른 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 스택(선입후출), 재귀함수로 구현한다. sojeong-lululala.tistory.com/5 [BOJ] [Python] 2775번 : 부녀회장이 될테야 간단한 예시를 만들어 작성하면서, 어떻게 문제를 풀어야 할 지 생각했다. 그렇게 떠올린 방법은 '재귀함수 사용' loop = int(input()) #test def people(a, b): global result if(a == 0): return b else: for i.. sojeong-lululala.tistory.com 2. 너비 ..
[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..
[BOJ] [Python] 2839번 : 설탕 배달 num = int(input()) tmp = num // 5 def sugar(num, tmp): if(num % 5 == 0): return num // 5 else: while(tmp != 0): if((num - tmp * 5) % 3 == 0): tmp += (num - tmp * 5) // 3 return tmp else: tmp-= 1 if(num % 3 == 0): return num // 3 else: return - 1 print(sugar(num, tmp))
[BOJ] [Python] 1748번 : 수 이어 쓰기 1 예를 들어, 입력값이 1234라고 한다면 1000부터 1234까지는 모두 4자리 수기 때문에, 4자릿수 (1234 - 1000 + 1)개를 미리 처리했다. 그리고 나머지는 그 수가 무엇이든, 자릿수에 따라 9 * 1, 9 * 10, 9 * 100 ... 개로 예상을 벗어나지 않기 때문에, 아래는 저렇게 처리했다. + 한 자릿수는 따로 처리 해줘야 한다. (한 자릿 수일 경우, 입력 값 그대로 출력하면 된다.) num = int(input()) len_fir = (num - int('1' + ('0' * (len(str(num)) - 1))) + 1) * len(str(num)) if(len(str(num)) == 1): print(num) else: num = str(num)[1:] len_aft = 0..
[BOJ] [Python] 1449번 : 수리공 항승 구멍을 완전히 막으려면 양쪽 0.5cm씩 더 막아야 해서, 소수점을 신경써야했다. 그러나 구멍위치와 테이프 길이가 모두 정수형이기 때문에, 테이프 길이를 -1하고 구멍의 위치만 신경쓰기로 했다. i번째 구멍 + ( l - 1)을 할 경우 i번째 구멍으로부터 테이프의 끝 위치를 알 수 있다. n, l = map(int, input().split()) hole = list(map(int, input().split())) hole.sort() now_hole = 0 count = 0 for i in hole: if(now_hole < i): count += 1 now_hole = i + l - 1 print(count) + 마지막에 count += 1을 해야 한다. (마지막 구멍) n, l = map(int,..

티스토리툴바