오묘한

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 이번 문제는 정말 어려웠다...! 한참을 고민해도 답을 찾지 못해서, 푸신 분들의 블로그를 찾다가 재귀를 활용해 굉장히 간단하게 구현하신데다 설명도 이해하기 쉽게 써주신 분의 블로그를 참조해 문제를 풀 수 있었다!(https://mgyo.tistory.com/183) [백준] 2447번 별찍기 문제 재귀 함수 이용해서 풀기 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 ..

17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 풀이 처음 봤을 때는 '이게 뭐람?' 싶었지만 출력 예시를 잘 뜯어보면 재귀를 사용해서 풀 수 있는 쉬운 문제! 앞의 '____'(----가 아니다! 처음에 ----인 줄 알고 이걸로 풀었더니 틀렸었다.) 의 개수가 몇 개씩 늘어나는지, 어떤 문장이 몇번 반복되고 있는지를 체크해보며 풀면 된다. #17478 재귀함수가 뭔가요? def recursion(N, lines): print(lines + '\"재귀함수가 뭔가요?\"') if N > 0: print(lin..

10872번: 팩토리얼 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 팩토리얼은 3가지 방법으로 풀었다. 재귀 함수로 한번, 반복문을 이용해 한번, 파이썬 자체적인 내장함수를 이용해 한번. 내장함수를 쓰는 방법이 제일 오래 걸렸다. # 10872 팩토리얼 # 첫 번째 방법: 재귀함수 def fact(N): if N > 0: return N * fact(N-1) else: return 1 N = int(input()) ret = fact(N) print(ret) # 두 번째 방법 : 반복문 활용 N = int(input()) sum = 1 for i in range(N, 0, -1): sum *= i prin..

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 처음에 이렇게 풀었는데 시간 초과가 났다 # 4948 베르트랑 공준 import math def isPrime(n): cnt = 0 for num in range(n + 1, 2 * n + 1): sq = int(math.sqrt(num)) flag = False for i in range(2, sq+1): if num % i == 0: flag = True break if flag is True: continue else: cnt += 1 return ..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 첫번째 시도: 이전처럼 2부터 n-1까지 모든 수로 n을 나누며 소수를 판별하는 방법을 사용했는데 시간초과가 났다. 두번째 시도: 아래 블로그 글을 참고해 제곱근을 활용하여 2부터 n-1이 아니라 2부터 제곱근까지로 나누어 소수를 판별하도록 알고리즘을 짰다. [백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python) 츄르사려고 코딩하는 코집사입니다. 1. [백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python) 1) 문제번호 : 1929번 2) 문제 출처 https://ww..

11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 원리는 N을 나누어 떨어지게 하는 수가 소수인지 여부를 판별하고, 소수이면 해당 수를 출력한 뒤, N에는 해당 소수로 나눈 몫을 저장해 N이 1이 될 때까지 반복문을 돌리며 나누는 소수를 출력하도록 했다. 하지만 내 생각보다 시간이 많이 걸렸다. 제곱근을 안쓰고 2부터 num까지 수로 모두 num을 나눠서 소수를 판별했기 때문일 것이다. # 11653 소인수분해 (2192ms) N = int(input()) cnt = 0 while N > 1: for num in range(2, N+1): flag = False if N % num == 0: for z in range(2, num)..

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 이것도 2부터 num까지 num을 나누어 소수인지 여부를 판별했다(매우 비효율적인 방법이다. 테스트케이스가 많은 예시일 때 시간초과 나기 쉽다.) 소수의 합과 소수 중 최솟값은 파이썬 내장함수(sum()함수, min()함수)를 이용했다. 시간은 588ms, 메모리는 30840KB가 나왔다. # 2581 소수 M = int(input()) N = int(input()) arr = [] for num in range(M, N+1): flag = False if num == 1..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net flag를 사용해서 주어진 숫자들이 소수인지 여부를 확인하면 되는 문제였다. 테스트케이스가 많지 않아서 그냥 2부터 a까지 모든 숫자들로 다 나눠보아도 시간이 그렇게 많이 들지 않았다. (하지만 뒤로 갈수록 테스트 케이스가 많아져서 이 방법대로 풀 수는 없었다. 그래서 제곱근이나 에라토스테네스의 체를 찾아보고 적용해야만 했다.) # 1978 소수 찾기 N = int(input()) arr = list(map(int, input().split())) cnt = 0 for a in arr: flag = False if a == 1: ..

2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 이 문제는 n과 k가 1부터 14 사이의 작은 수여서 O(n2)의 시간복잡도가 나오더라도 이중 반복문을 사용해 풀었다. # 2775 부녀회장이 될테야 T = int(input()) for tc in range(1, T+1): k = int(input()) n = int(input()) house = [[0 for _ in range(n+1)] for z in range(k+1)] # 0층의 room들은 1, 2, 3 순으로 사람이 들어가 있다. for r in range(n+1): house[0][r]..

10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 이 문제는 쉽게 접근해서 풀었지만, 중간에 미처 찾지 못한 반례때문에 계속 틀리다가 반례를 알아내서 맞춘 문제이다. 처음에는 이렇게 flag 없이 풀었다. # 10250 ACM호텔 T = int(input()) for tc in range(1, T+1): H, W, N = map(int, input().split()) cnt = 1 for w in range(1, W+1): for h in range(1, H+1): if cnt == N: print(..