ComDoc ComDoc

소수(素數, prime number)는 1과 자기 자신만을 약수로 가지는 1 이외의 정수입니다. 정의를 따라 코딩해 보면 다음과 같죠. def is_prime1(n): if n

숫자 n에서 k개의 수를 제거해서 만들 수 있는 가장 큰 숫자를 구하라. 1234에서 숫자 두 개를 제거하면 [12, 13, 14, 23, 24, 34]를 만들 수 있습니다. 이 중 가장 큰 숫자는 34입니다. (숫자의 순서는 바뀌지 않습니다.) 숫자 n은 1자리 이상, 1,000,000자리 이하입니다. k는 1 이상, n의 자릿수 미만인 자연수입니다. 결과는 문자열로 출력합니다. [풀이] ...더보기 1234에서 1, 2 처럼 앞뒤 숫자를 비교해서 앞 숫자가 작으면 지워주면 됩니다. 자료구조를 이용한 풀이가 떠오릅니다만 식상한 감이 있으니 특이하게 풀어야 주목 받으니 문자열로 풀어봅시다. def solution(number, k): length = len(number) final_length = len..

어떤 과학자가 발표한 논문 중, h번 이상 인용된 논문이 h 편 이상이라면 이때 h가 이 과학자의 H-Index입니다. H-index를 구하는 함수를 작성하십시오. def solution(citations): citations.sort(reverse=True) for i, v in enumerate(citations): if i >= v: return i return i + 1 print(solution([32, 22, 2, 0])) # 2 print(solution([32, 22, 3, 0])) # 3 print(solution([32, 22, 4, 4])) # 4 참고) 파이썬에서는 for 문이 끝나도 사용한 index 변수가 사라지지 않고 남아 있습니다. 마지막의 i+1은 len(citations)..

최대공약수(gcd): 유클리드 호제법이 가장(?) 빠른 계산법으로 알려져 있습니다. def gcd(a, b): while b: a, b = b, a % b return a print(gcd(78696, 19332)) 최소 공배수(lcm)는 a * b / gcd def lcm(a, b): return (a*b)//gcd(a, b) 인류 최초의 알고리듬 유클리드(Euclid)는 그리스 수학자 에우클리데스(Ευκλείδης)의 영어식 표현입니다. 유클리드는 기원전 3세기경 (기하학) 원론 이라는 책을 썼고, 원론 7권 첫 부분에 유클리드 호제법이 실려있습니다. 호제법(互除法)이란 서로(互) 덜어낸(除)다는 뜻입니다. 덜어낼 때는 나누어서 몫만 남깁니다. 프로그래밍 언어에서는 보통 mod 라고 표현하죠. 호제법..

부서별로 필요한 물품 하나씩을 신청받았습니다. 정해진 예산을 초과하는 경우 '모든 부서'의 물품을 구매해 줄 수는 없습니다. 최대한 '많은 부서'의 물품을 구매하려고 합니다. 물품은 조각나지 않으며, 물품의 일부만 구매할 수 없습니다. 그래서 물품을 구매해 줄 때는 각 부서가 신청한 금액이 정확히 사용됩니다. 예를 들어 10원짜리 물품을 신청한 부서에는 정확히 10원짜리 물품이 지원되어야 하며, 10원보다 적은 금액의 물품을 대신 구매해 줄 수는 없습니다. 재귀로 풀어보았습니다. (삽질의 시작) def allocate_base(): sum = 0 # 요청의 합 index = len(request) count = 0 # 예산에 반영된 부서의 수 return allocate(index, count, sum)..

배낭 문제는 짐을 쪼갤 수 있느냐 없느냐로 나뉩니다. 쪼갤 수 있는 경우 분할 가능 배낭 문제라고 합니다. 배낭에 담을 수 있는 물건이 분할이 되면 쉽습니다. (금가루, 은가루, 철가루) 부피 (또는 무게) 대비 가치가 높은 물건들부터 담으면 되기 때문입니다. 이것을 탐욕(greedy) 알고리듬이라고 합니다. 부피 대비 가치가 높은 물건 순서대로 담으면 되고, 담을 때 '뒤에 어떤 물건을 넣을지' 고려하지 않아도 되기 때문에 붙여진 이름입니다. (탐욕스럽게) 비싼 것부터 막 넣어~! 어떤 행위가 나중에 어떤 영향을 미칠 지 생각하지 않고 현재 가장 이익이 되는 행위만 취해도 최고의 결과가 나올 때 사용하는 쉬운 알고리듬입니다. 동전 거스름돈의 경우도 대부분의 국가에서 탐욕 알고리듬으로 정답이 나오도록 되..

동적 프로그래밍((dynamic programming)을 적용하기 쉬운(?) 예제로 가장 긴 공통 문자열 찾기(LCS, Longest Common Substring)가 있습니다. 두 개의 문자열 'abcde'와 'cdefg'에서 가장 긴 공통 문자열은 'cde'입니다. 먼저 전수조사(brute force)로 답을 찾아보고 문제점을 알아봅니다. def make_set(s): result = set() for i in range(len(s)): for j in range(i + 1, len(s) + 1): result.add(s[i:j]) return result def lcs(s1, s2): max_len = 0 max_str = '' for each in make_set(s1) & make_set(s2)..

막대기 자르기(Rod cutting) 하나의 막대기가 있다. 막대기의 길이에 따라 가격이 다르다. 최고의 수익을 얻도록 막대기를 자르라. 이때 최고의 수익은? 파이프 전체의 길이, 잘랐을 때 길이에 따른 가격이 들어간 배열이 주어짐. length : i 1 2 3 4 5 6 7 8 9 price : Pi 1 5 8 9 10 17 17 20 24 재귀로 구현 def cut_rod(price, n): max_val = price[n] for i in range(1, n): max_val = max(max_val, price[i] + cut_rod(price, n - i)) return max_val print(cut_rod([0, 1, 5, 8, 9, 10, 17, 17, 20, 24], 8)) # 22 어..