Baekjoon/Stepbystep

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

목차 동전 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..

숏코딩보다는 백트래킹, 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..

목차 배수와 약수(#5086) Problem 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. Hint 나머지를 이용하여 약수인지 배수인지를 구별하자 Solution 나머지를 이용한 풀이 a=b=1 res=[] while a+b!=0: a,b=map(int,input().split()) if a>b and a%b==0: res.append('multiple') el..