Do you believe in you?

▷ 문제설명 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제 이 때, n의 범위는 1 T; for (int t = 0; t > num; cout

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ▷ 문제설명 NxM 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제 N, M의 범위는 4 > N >> M; for (int i = 0; i > arr[i][j]; } } StartCalculation(arr, N, M); } void StartCalculation(int arr[SIZE][SIZE], int N, int M) { int ..

1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ▷ 문제설명 준규가 사는 나라는 연도를 표현할 때 E, S, M 세 문자로 표현한다. 각각의 문자가 가지는 범위는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다. E, S, M이 주어질 때, E S M으로 표시되는 가장 빠른 연도를 출력하자. ▷ 문제풀이 이 문제의 경우 표현할 수 있는 년도는 15 * 28 * 19 = 7980년까지 이므로 브루트포스 방법으로 1년 부터 7980년까지 구하다가 정답과 같아지는 순간을 찾으면 된다. 이 때, 문제에..

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net ▷ 문제설명 찐 일곱난쟁이를 찾는 문제! 즉, 가짜 난쟁이 2명이 포함된 9명의 난쟁이 중에서 찐 일곱난쟁이를 찾아야 한다. 그리고 일곱난쟁이의 키를 오름차순으로 출력해야 한다. ▷ 문제풀이 1) 일곱 난쟁이의 키의 합이 100인 것과 순열의 성질을 이용한다. 2) 9명 중, 7명을 선택하는 방법이 아닌 2명의 난쟁이를 선택하는 경우를 구한다.(9C7 = 9C2) 3) 전체 키의 합에서 2명 키를 빼본다. 4) 그 값이 100이 된다면 그 둘이 가짜 난쟁이들이다. ▷ 시..

▷ 부루트 포스 알고리즘이란? : 아묻따 모든 경우의 수를 다 계산해보는 것. : 숫자가 커질 수록 계산 시간이 기하급수적으로 증가함. ▷ 예시 4자리 비밀번호를 풀어야 할 때의 0000~9999의 경우의 수인 10,000가지를 다 계산해보는 것을 말한다. ▷ 관련된 백준 알고리즘 문제 : 2309번 일곱 난쟁이, 1476번 날짜 계산, 14500번 테트로미노 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는..

▷소수란? : 약수가 1과 자기 자신 밖에 없는 수 : 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지지 않는 자연수 소수의 예) 2, 3, 5, 7, 11, 13, 17, 19, 23, ... ▷소수를 구하는 방법? ① 자연수 N의 가장 큰 약수는 N/2보다 작거나 같으므로 2부터 N/2까지 나눠보기. ② 자연수 N을 루트 N까지 나눠보기. Why? N이 소수가 아니라면 N=a X b 로 표현할 수 있다. (a와 b는 자연수) (이 때, a와 b는 a b 라면 두 수를 바꿔서 항상 a

▷최대공약수란? : GCD(Greatest Common Divisor) : 두 수 A와 B의 공통된 약수 중에서 가장 큰 정수 ▷구하는 방법? ① 2부터 min(A, B)까지 모든 정수로 나눠서 나머지가 0이 되는 최대 정수 찾기. ② 유클리드 호제법(Euclidean algorithm)으로 찾기. : a를 b로 나눈 나머지를 r 이라고 했을 때, GCD(a, b) = GCD(b, r) 이 성립한다. → 재귀로 구현 가능 : r이 0이면 그 때의 b가 최대 공약수 이다. ex) GCD(16, 12) = GCD(12, 4) = GCD(4, 0) = 4 → GCD(a, b) = GCD(b, a%b) 로 표현 됨 ▷최대공배수란? : LCM(Least Common Multiple) : 두 수의 공통된 배수 중에..

▷ C++ Template이란? : int, double, long 등의 자료형에 구애받지 않고 공통된 함수를 만들어 놓고 사용하기 위해 정의해두는 것 ▷ C++ Document에서의 정의 #include template const T& min (const T& a, const T& b) ▷ 사용법 #include #include using namespace std; template T sum(T a, T b){ return a + b; } int main(){ cout