Baekjoon

목차 색종이 만들기(#2630) Problem 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져..

이항 계수 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을 사용하여야지 시간초과를 피할 수 있다. ..

목차 알고리즘 수업 - 피보나치 수 1(#24416) Problem 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자. 피보나치 수 재귀호출 의사 코드는 다음과 같다. fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2)); } 피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다. fibo..

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..