목록분류 전체보기 (317)
지나가던 개발자
[Algorithm] 카라추바 알고리즘 | 빠른 곱셈 | Python
PS를 할 때 빠른 곱셈과 빠른 거듭제곱은 정말로 중요하다. PS를 할 때 뿐만 아니라 그냥 코딩을 할 때에도 중요하다. 카라추바 알고리즘은 빠르게 곱셈을 할 때에 사용되는 알고리즘으로, 보통의 곱셈 알고리즘의 시간 복잡도가 O(n^2)인 데에 반해 카라추바 알고리즘의 시간 복잡도는 O(n^1.585)밖에 나오지 않는다. 혁신인 것이다! O(n^2)와 O(n^1.585)가 차이가 별로 안 난다고 생각할 지도 모르지만, n이 1부터 50까지 커질 때 O(n^2)와 O(n^1.585)의 차이를 보면 다음과 같다. for n in range(1, 51): print("When N is", n, "- O(n^1.585):", n**1.585, "O(n^2): ", n**2) n=2일 때는 약 3과 4 정도로밖에..
[Python] 백준 4150번(피보나치 수) 문제 풀이
import sys sys.setrecursionlimit(10**6) def nth_fibonacci(n, lookup): if n
이제 벌써 제가 중학교 3학년입니다.. 시간이 왜 이리 빠른지 모르겠어요. 저는 아직 애긴데 벌써 고교생이라니. 저는 진짜 아직 애긴데. 저번에 서울과학고등학교를 넣었던 적이 있는데 2차에서 가볍게 떨어져주고요즘 유가도 비싼데 괜히 서울까지 왔다갔다만 했다 이번에는 지방과고인 전북과학고를 넣었습니다. 합격할 것 같긴 하지만 합격하려면 준비를 철저히 해야 하죠. 제 자소서에 제가 수학특기로 유클리드 호제법을 넣었습니다. 면담에서 증명하라칼것같아서 글을 써보려 합니다. 우선 유클리드 호제법이라는 것은 a>b인 두 자연수 a, b에 대해서 a=bq+r이라고 할 때 gcd(a, b)=gcd(b, r)이라는 것입니다. 이게 무슨 의미가 있냐 하면 gcd(3414943903189551289, 527180105123..
[Python] 백준 2028번(자기복제수) 문제 풀이
def 자기복제수(num): if str(num**2)[-len(str(num)):] == str(num): return "YES" return "NO" for i in range(int(input())): print(자기복제수(int(input()))) 겉멋만 든 영어 변수명을 거부합니다... 라기보다는 자기복제수를 어케 번역해야 적절한 변수명이 나올지 모르겠어서 그냥 한글로 했다.
[Python] 백준 2535번(아시아 정보올림피아드) 문제 풀이
players = [] for i in range(int(input())): players.append(list(reversed(list(map(int, input().split(" ")))))) players = sorted(players, reverse=True) printed_country = [] i = 0 while True: if printed_country.count(players[i][2]) < 2: print(players[i][2], players[i][1]) printed_country.append(players[i][2]) if len(printed_country) == 3: break i += 1 2차원 배열을 sort하면 0번째 인덱스를 기준으로 정렬된다. 사실 그냥 key를 사..
[Python] 백준 10448번(유레카 이론) 문제 풀이
triangle_number = [n*(n+1)//2 for n in range(1, 45)] eureka = [0 for i in range(1001)] for i in triangle_number: for j in triangle_number: for k in triangle_number: if i+j+k
빅오 표기법, 개발을 시작한 지 일주일에서 한 달 정도 되었으면 누구나가 들어 보셨을 겁니다. 못 들어 봤더라도 O(n), O(n log n)과 같은 표기들은 분명히 보셨을 겁니다못 보셨어요? 그러면 문과 가세요. 그만큼 개발자들과 떼려야 뗄 수 없는, 마치 수영장과 물, 스키장과 눈(!) 같은 존재가 개발자들과 시간 복잡도입니다. 빅오는 그걸 나타내는 표기 중 하나이고요. 빅오는 상한을 의미합니다. 하한을 의미하는 빅오메가도 있고, 평균을 의미하는 빅세타도 있어요. 그런데 빅오를 쓰는 이유는 상한으로 표기해야지 틀리지 않기 때문이에요. 예를 들어 어떤 프로그램이 1초 안에 돌아가겠다고 예상한다면 0.5초 안에 돌아가든 0.3초 안에 돌아가든 상관이 없습니다. 그런데 0.5초나 0.3초 안에 돌아간다고 ..
