링크 : https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 문제 풀이 문제에 점화식이 주어졌으므로 그대로 구현하면 된다. 아래 강좌를 참고해도 좋다. https://reo91004.tistory.com/54 [자료구조] 순환 (Recursion) 순환 (Recursion) 흔히 재귀라고 부른다. 즉, 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환으로 구현할 수 있는 알고리즘의 ..

링크 : https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 간단한 재귀 문제이다. 재귀를 이해해야 하는 기초 문제라 아래 링크를 참고하면 좋을 것 같다. https://reo91004.tistory.com/54 [자료구조] 순환 (Recursion) 순환 (Recursion) 흔히 재귀라고 부른다. 즉, 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환으로 구현할 수 있는 알고리즘의 대다수는 반복으로도 구현할 수 있다. 다만 reo91004.tistory.com C++ 코드 전문 HTML 삽입 미리보기할 수 없는..

링크 : https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 문제 문제 풀이 처음에 택시 기하학이 이해가 가지 않아 인터넷을 참고한 문제다. 너무 설명을 잘해주신 분들이 많아 그 분들의 블로그를 참고하는 것이 더 도움이 될 것 같다. https://lalayeon.tistory.com/178 [백준] 3053 택시 기하학 (C++) 문제 www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를..

링크 : https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제 문제 풀이 피타고라스 정리를 코드로 구현하면 된다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 문제 풀이 나는 '두 소수의 차이가 가장 작은 것을 출력' 이라는 조건을 보고, 애초에 n을 2로 나누어 거기서부터 시작하면 어떨까? 하는 생각부터 시작했다. 그러다 예제를 보고 어차피 더하면 n이 나와야 하니 n / 2 + k와 n / 2 - k가 둘 다 소수인 k를 찾으면 정답이겠구나 싶어 코드를 설계하게 되었다. 발상이 빨리 되지 않았다면 어려운 문제였을 것..

링크 : https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 문제 풀이 소수를 구하는 이전 문제들과 비슷한 맥락이지만 일일이 소수를 판별하는 알고리즘을 사용하면 시간 초과가 난다. 에라토스테네스의 체를 이용해야 한다. 잘 설명해주신 분이 있어 링크를 첨부한다. https://maramarathon.tistory.com/39 소수 판별 알고리즘과 에라토스테네스의 체 소수 판별 알고리즘 소수 판별 알고리즘은 시간복잡도에 따라 다르게 구현 ..

링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 문제 풀이 이전에 포스팅했던 소수 찾기, 소수 문제들과 같은 맥락이다. 출력값만 조금 조정해주면 된다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 문제 풀이 N이 i로 나누어지면 출력하는 식으로 반복해주면 된다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 문제 풀이 바로 전 문제인 소수 찾기와 같은 알고리즘을 사용한다. 조건만 추가되었을 뿐이다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 문제 풀이 다들 에라토스테네스의 체로 구현했는데 나는 하나씩 입력받아 이를 소수인지 판별하는 방식이 가장 먼저 떠올라 해당 방식으로 풀어보았다. 파이썬은 에라토스테네스의 체로 구현해보았다. C++ 코드 전문 HTML 삽입 미리보기할 수 없는 소스 Python 코드 전문 HTML 삽입 미리보기할 수 없는 소스 소감

링크 : https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제 풀이 어떤 방법을 사용해도 정수형으로는 풀 수 없는 문제이다. 그러므로 char 배열을 이용하거나 string을 이용해야 한다. 둘 다 맥락은 비슷하지만 string으로 풀어보았다. C++ 상세 풀이 더보기 for (i = 0; i < len; ++i) { tmp = carry; carry = false; if (i < A.size()) tmp += A[A.size() - i - 1] - '0'; if (i < B.size()) tmp += B[B.size() - i - 1] - '0'..

링크 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 문제 풀이 수학 문제다. 푸는 방법은 DP와 그리디, 두 가지 방법이 있다. 우선 그리디로 푸는 방법은 간단하다. 최대한 적은 봉지를 들고 가고 싶다 했으니, 5kg짜리 봉지로만 담으면 된다. 처음에 주어진 N값이 5로 나누어 떨어진다면 (N % 5 == 0) 바로 5로 나눈 값을 출력하면 되고, 그렇지 않다면 3kg 봉지로 담고 출력할 값을 늘려줌과 동시에 N에서 3을 빼는 식으로 풀었다. ..