링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 문제 풀이 재귀로 풀지 않으면 접근 방식이 참 어려울 것 같은 문제다. 찬찬히 생각해보면, 이동 과정을 통째로 i) n-1개의 원판을 2번째 장대로 옮긴다. ii) 제일 밑에 있는 원판을 3번째 장대로 옮긴다. iii) 2번째 장대에 있는 원판들을 3번째 장대로 옮긴다. 라고 요약할 수 있다. ii)번째 과정을 생각해보자. 이는 1) 2번째 장대의 맨 마지막 원판을 제외..

링크 : https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 문제 풀이 어려운 문제다. 재귀에 대한 완전한 이해가 있어야 풀 수 있는 문제인 것 같다. C++과 파이썬의 풀이가 살짝 다르지만 이번 문제는 모든 분이 C++ 상세 풀이를 보시면 도움이 될 것 같습니다. C++ 상세 풀이 더보기 정답률이 52%지만, 수학적 발상이 있어야 하는 문제다. 어차피 재귀적으로 풀어야 하는 문제이므로 N = 3일 때와 N = 9일..

링크 : 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 삽입 미리보기할 수 없는 소스 소감