파이썬

이항 계수 3(#11401) Problem 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 (N,K) 를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. Hint 주어진 1000000007은 크기가 큰 소수이다. Solution 큰수의 곱들의 나머지를 구할 때에는 분할 정복을 이용하여 매번 계산시에 나머지를 구한후 나머지로만 남은 연산을 실시하여도 같은 결과가 나온다는 사실은 알고 있어야한다. (나머지 연산 -모듈러 법칙) ps. 사실 법칙 네이밍은 중요하지 않다 수학적 원리를 이해할수 있기만 하면된다. 하지만 마지막에 사용하는 페르마 소정리의 경우에는 과거에 올림피아드 등을 준비하지 않았더라면 일반적인 사람이 미리 알고 있기 쉽지않다. n,k= map(int, inp..

목차 동전 0(#11047) Problem 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. Hint 나머지를 잘 이용해보자 Solution 그리디 알고리즘을 이용한 풀이 n,k=map(int,input().split()) coin=[] cnt=0 for _ in range(n): coin.append(int(input())) for i in coin[::-1]: if i

목차 구간 합 구하기 4(#11659) Problem 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. Solution 누적합을 이용한 풀이 import sys input = sys.stdin.readline n ,m = map(int,input().split()) a = [0]+list(map(int,input().split())) for l in range(2,n+1): a[l]+=a[l-1] res =[] for o in range(m): i ,j = map(int,input().split()) res.append(a[j]-a[i-1]) print(*res,sep='\n') 이 문제는 input이 아닌 readline을 사용하여야지 시간초과를 피할 수 있다. ..

01타일(#1904) Problem 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 110..

숏코딩보다는 백트래킹, BackTracking 을 이용하여 문제가 원하는 목적에 맞게 풀이해보았다. 목차 N과 M (1)(#15649) Problem 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 Hint 일반적인 백트래킹 방법을 이용하였다. Solution 백트래킹을 이용한 풀이 n, m = map(int, input().split()) res = [] def BackT(depth): if depth == m: for i in res: print(i, end=' ') print() return for i in range(1, n + 1): if i not in res: res.appe..

오류 발생 알고리즘 공부를 하다가 분명히 틀린 문법이 없는데 return 에 오류가 나왔었다. 아무리봐도 문법 오류가 없는데... 싶었지만 if 가 살짝 앞으로 더 튀어나와 있었다.. 오류 발생 이유 분석 indent, indention : 둘다 영어로 들여쓰기 라는 뜻을 가지고 있다. 정리하자면 들여쓰기가 이전 들여쓰기한 정도랑 매치하지 않는다! 라는 뜻이 된다. 오류 해결 들여쓰기의 정도를 맞춰주자. if 만큼 return 을 앞으로 한칸 빼줄수도 있지만 tab을 통하여 띄워주는것이 vscode에서 편리하기 때문에 if의 제자리를 찾아줬다.