파이썬2 [파이썬]10997:별 찍기 - 22 문제 링크 요약 문제 난이도: 3/10(실버 2) 문제 타입: 재귀 특이 사항: 낚시성 케이스 존재 개요 알고리즘 문제에서 가장 잘 알려진 형태인 별을 출력하는 문제입니다. N번째에 출력할 형태는 N-1번째 출력을 포함하고 있는 재귀적인 형태의 구조입니다. 예를 들어, 밑의 사진처럼 N=3일 때의 출력은 N=2일 때의 출력을 가운데에 포함하고 있습니다. 이전에 별 찍기와 연관된 문제를 푼 적이 있다면, 조금 응용하여 풀 수 있는 문제입니다. 문제 풀이 미리 정리해 놓고 가야 할 것 해당 문제는 재귀적인 함수호출을 연습하기 위해 만들어진 문제입니다. 출력의 사이즈는 다음과 같은 관계를 가집니다. 가로: 4 * N - 3, 세로: 4 * N - 1 N번째 출력은 N - 1번째의 출력을 중심으로 두고, 양옆으.. 2023. 5. 22. (Python) 약수 구하기.(시간 복잡도:$O(\sqrt{n})$) 코딩테스트 문제를 풀다보면 어떤 수의 모든 약수를 구해야 할 때가 있다. 아주 간단하게 어떤 수의 약수를 구하는 알고리즘을 알아보자.추가로, 약수를 정렬된 순서로 리턴까지 해보자. 숫자 n의 약수를 구하는 알고리즘을 소개하면 다음과 같다.(시간 복잡도:$O(\sqrt{n})$) 1 ~ $\sqrt{n}$의 범위안에 드는 자연수 i를 대상으로 루프를 돈다. 만약 n이 i로 나누어 떨어진다면, i와 n을 i로 나눈 값은 n의 약수이다. 이를 코드로 나타내면 다음과 같다. x = 100 divisor_set = set() for divisor in range(1, int(x**0.5) + 1): if x % divisor == 0: divisor_set |= {divisor, x // divisor} prin.. 2022. 12. 26. 이전 1 다음