ComDoc ComDoc

어떤 과학자가 발표한 논문 중, 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 어..

피보나치 수(Fibonacci numbers)의 역사는 적어도 기원전 700년경으로 거슬러 올라가며, 1202년 이탈리아의 수학자인 레오나르도 피보나치가 피보나치 수로 토끼의 개체 수 증가를 설명한 것을 계기로 피보나치라는 이름이 붙었다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55....이전의 두 숫자를 더해서 다음 숫자를 만드는 수열입니다.  이제 문제만 읽어도 아 이건 재귀 문제구나 느낌이 오죠?물론 재귀로만 이 문제를 풀 수 있는 것은 아닙니다만...알고리듬은 역시 재귀. 재귀가 제 맛 아니겠습니까? 재귀 1자 이제 코딩을 해봅시다. def fibonacci(a, b): print(a) return fibonacci(b, a+b)fibonacc..

정렬된 데이터에서 검색할 때는 이진(이분) 검색이 더 효율적입니다. 친구가 1부터 100까지 숫자 중 하나를 고르고, 나는 그 숫자를 맞추는 게임을 한다고 가정합니다. 친구는 "고른 숫자가 내가 제시한 숫자보다 크다, 작다, 맞다."를 대답해 줘야 합니다. 이때 가장 빨리 정답을 찾는 법은 절반인 50을 제시하는 것입니다. 여기서 친구가 작다고 하면 25를 불러보고... 한번 검색할 때마다 절반이 날아갑니다. 엄청난 효율이죠. 실제로 32라는 숫자를 찾아보겠습니다. 1. 50? 작아 2. 25? 커 3. 37? 작아 4. 31? 커 5. 34? 작아 6. 32? 정답 6번 만에 찾을 수 있습니다. from random import randint print("Guess the number!") secret..