The Way

백준 온라인 저지(BOJ) 1094번 문제https://www.acmicpc.net/problem/1094 1. 문제 요약64cm의 막대기를 가지고 Xcm의 막대기를 만들기.이 때 다음의 방법을 이용한다.1. 가지고 있는 막대의 길이를 모두 더해서 X보다 크면, 그 중 가장 작은 길이의 막대기를 절반으로 자른다.2. 자르고 그 중 하나를 버렸을 때 그 합이 X보다 크거나 같으면 하나를 버린다. 위 과정을 반복해, 남아있는 막대의 합이 X가 되도록 만든다.이 때 위 과정을 거친다면 몇 개의 막대를 풀로 붙여야 Xcm를 만들 수 있을까? 2. 알고리즘뭔가 표현은 복잡하지만, 분석해보면 간단함을 깨달을 수 있을 것이다. 64cm부터 시작해서, 가장 짧은 막대의 길이는 점차 반으로 줄어들어 32, 16, 8, ..

1. 피보나치 수열이란?피보나치 수열에 대해 길게 설명할 이유는 없으므로 간단히 식만 쓰도록 하자. 누구나 알고 있을 것이라 생각한다.$$F_n = \begin{cases}0 \; (n=0)\\1 \; (n=1)\\F_{n-1}+F_{n-2} \; (n>1) \end{cases}$$ 2. 재귀함수를 사용하지 않고 피보나치 수열 구하기사실 그리 어렵지는 않다.앞의 수를 기억하고 있어야 하므로 0, 1에서 시작해서 (a, b) -> (b, a+b)로 바꾸어주면 된다. int fib1(int n) { if (n == 0) return 0; if (n == 1) return 1; int a, b, t; a = 0; b = 1; for (int i = 1; i < n; ++i) { t = b; b = a + b;..

1. 재귀함수란? 재귀함수란 함수 내에서 같은 함수(자기 자신)가 또 실행되는 함수의 형태를 말한다. 가장 기본적인 형태는 base case와 recursive case 둘을 갖는 형태인데, 가장 유명한 예시인 팩토리얼 구하기를 살펴보자. int fac1(int n) { // base case if (n

C++ 코딩용으로 Visual Studio 2015를 사용할 때scanf를 사용하려고 하면 C4996 에러가 발생한다. 해석하자면, scanf 함수가 안전하지 않아 scanf_s를 사용하라고 적혀있다. 또는, _CRT_SECURE_NO_WARNINGS를 사용하라고 한다. 예시 코드는 다음과 같다. #include using namespace std; int main() { int n; scanf("%d", &n); for (int i = 1; i

백준 온라인 저지(BOJ) 2839번 문제 https://www.acmicpc.net/problem/2839 1. 문제 요약 3킬로그램 봉지와 5킬로그램 봉지를 이용해 주어진 무게의 봉지를 만들어야 한다. 이 때 봉지의 최소 개수를 출력하자. 만들수 없으면 -1을 출력. 2. 알고리즘 3kg짜리 봉지를 최대한 적게 써야한다. 처음 수에서 5의 배수가 될 때까지 3씩 빼도록 한다. 빼다가 음수가 되면 만들 수 없는 경우이므로 -1을 출력한다. 3. 코드 #include using namespace std; int main() { int N; cin >> N; int n3 = 0; int n5 = 0; while (N % 5 != 0 && N >= 0) { N -= 3; n3++; } if (N < 0) c..

백준 온라인 저지(BOJ) 11719번 문제 https://www.acmicpc.net/problem/11719 1. 문제 요약 입력 받은 대로 출력하기. 빈 줄이 주어질 수도 있고, 각 줄의 앞뒤로 공백이 있을 수도 있음. 2. 알고리즘 11718번 문제와 동일함. 자세한 내용은 여기를 참고. 3. 코드 #include using namespace std; int main() { char a; a = getchar(); while (a != -1) { putchar(a); a = getchar(); } return 0; }

백준 온라인 저지(BOJ) 11718번 문제 https://www.acmicpc.net/problem/11718 1. 문제 요약 입력 받은 대로 출력하기. 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않음. 2. 알고리즘 입출력을 어느 정도 이해해야 풀 수 있는 문제이다. 보통 사람들은 입력은 콘솔창을 이용해서 하거나 또는 파일 입출력을 한다. 이 때, '입력의 끝'이 언제냐를 아는 것이 하나의 관건이다. 보통 입력받은 것이 아무 것도 없을 경우를 판별하지만, 이번 문제는 괜찮지만 다음 문제(11719번)와 같은 경우는 중간중간 빈 줄이 있기 때문에 문제가 발생한다. 다행히도 대부분의 입출력 함수들은 입력 버퍼의 끝에 갔을 때 -1이나 false의 값을 반환한다. 이를 EOF(End of File)..

백준 온라인 저지(BOJ) 10172번 문제 https://www.acmicpc.net/problem/10172 1. 문제 요약 아래 예제처럼 개를 출력하기 |\_/| |q p| /} ( 0 )"""\ |"^"` | ||_/=\\__| 2. 알고리즘 특이사항이 있다면 ", ', \, % 이 4가지는 코드에서 쓰이는 것과 구별이 힘들기 때문에 " -> \" ' -> \' \ -> \\ % -> %% (cout을 사용할 때는 %로 입력해도 되지만, printf를 사용할 때는 %%로 써주어야 한다) 로 입력해야 한다. 3. 코드 #include using namespace std; int main() { cout

백준 온라인 저지(BOJ) 1008번 문제https://www.acmicpc.net/problem/1008 1. 문제 요약두 수 A와 B를 입력받고 A/B를 출력. 절대/상대 오차는 10^-9까지 허용. 2. 알고리즘printf("%.9lf")를 써도 되지만, c++을 사용하는 사람답게 cout을 사용해보자.cout은 정확도를 아래 코드를 이용해 조절한다.cout.precision(15); 이는 정확도를 15자리까지 표시해준다는 의미이다.소숫점 아래 15자리가 아니고, 유효숫자 15개라는 것에 유의하자. 예컨대 이 문제에 해당하지는 않지만, 123456.78912345라는 숫자가 있을 때cout.precision(6)를 한 뒤 출력하면 123457로 나온다. 소숫점 아래 자리수를 정해주려면, cout >..

백준 온라인 저지(BOJ) 1004번 문제 https://www.acmicpc.net/problem/1004 1. 문제 요약 여러 원에 둘러쌓인 두 점이 있다. 한 점에서 다른 한 점으로 갈 때, 지나야 하는 경계의 최소 개수는? (원의 경계가 맞닿거나 교차하는 경우는 없다) 2. 알고리즘 원의 경계가 맞닿거나 교차하는 경우는 없다는 조건 때문에 문제풀이가 쉬워진다. 두 점이 i) 둘 다 원 안에 있다면 0번 ii) 둘 다 원 밖에 있다면 0번 iii) 둘 중 하나만 원 안에 있다면 1번 씩 더해주면 된다. 1002번과 마찬가지로 거리를 비교할 때 sqrt를 쓰지 않는 편이 이롭다. 3. 코드 #include int main() { int T; scanf("%d", &T); for (int i = 0; ..