눈송이의 개발생활

문제 https://www.acmicpc.net/problem/15988 코드 import sys input = lambda : sys.stdin.readline().strip() n = int(input()) dp = [0] * 1000001 dp[1], dp[2], dp[3] = 1, 2, 4 for i in range(4, 1000001): dp[i] = dp[i - 1] % 1000000009 + dp[i - 2] % 1000000009 + dp[i - 3] % 1000000009 for _ in range(n): num = int(input()) print(dp[num] % 1000000009) 풀이 1번째는 메모리 초과, 2번째 시도는 시간초과로 틀린 문제이다 메모리 초과는 왜 나는지 계속 찾..

문제 https://www.acmicpc.net/problem/1406 코드 #1 - WRONG ❌ from collections import deque import sys input = lambda : sys.stdin.readline().strip() str = deque(input()) n = int(input()) cursor = len(str) for _ in range(n): op = input().split() if op[0] == 'L' and cursor != 0: cursor -= 1 elif op[0] == 'D' and cursor != len(str): cursor += 1 elif op[0] == 'B' and cursor != 0: del str[cursor - 1] curso..

문제 https://www.acmicpc.net/problem/1748 코드 import sys input = lambda : sys.stdin.readline().strip() n = input() answer = 0 length = len(n) - 1 for i in range(length): # i는 0부터 시작 ~ 자릿수보다 하나 작은거까지 answer += (i+1) * 9 * (10 ** i) answer += (length + 1) * ((int(n) - (10 ** length)) + 1) print(answer) 풀이 그리디 유형 문제 중 처음으로 아무런 힌트 없이 쉽게 풀 수 있는 문제였다 예시를 보면 쉽게 패턴을 찾을 수 있다 15 → 123456789 + 101112131415 15..

문제 https://www.acmicpc.net/problem/1476 코드 E, S, M = map(int, input().split()) answer = 1 while True: # 배수가 되는 수에서 빼고 그 다음 나머지 계산 if (answer - E)%15 == 0 and (answer - S)%28 == 0 and (answer - M)%19 == 0: print(answer) break answer+=1 풀이 풀이를 생각해내는게 생각보다 오래 걸렸다. 실버5 문제인데도 꽤 어려워서(나한테는...) 내가 생각한 풀이를 완전 바꿔야 했었다. 처음에는 for문을 계속 돌면서 3 수(15, 28, 19)의 공배수를 찾는 방법으로 생각했는데 코드를 짤 수 없어서 반대로 접근해보았다. 숫자를 계속 키워..

문제 https://www.acmicpc.net/problem/3085 코드 import sys input = sys.stdin.readline # 행/열에서 사탕 최대 개수 구하는 함수 def check(candies): n = len(candies) answer = 1 for i in range(n): count = 1 # 열 순회하면서 연속되는 숫자 세기 for j in range(1, n): if candies[i][j] == candies[i][j-1]: count += 1 else: count =1 if count>answer: answer = count count = 1 # 행 순회하면서 연속되는 숫자 세기 for j in range(1, n): if candies[j][i] == candi..

문제 https://www.acmicpc.net/problem/6588 코드 import sys r = 1000000 sieve = [True for _ in range(r)] for i in range(2, int(r**0.6)): if sieve[i]: for j in range(i + i, r, i): sieve[j] = False while True: n = int(sys.stdin.readline()) if n == 0: break for k in range(3, r): if sieve[k]: if sieve[n-k]: print("%d = %d + %d"%(n , k , n-k)) break 풀이 계속 작은 조건들때문에 많이 틀린 문제이다. 문제였던 부분은.. 100000까지의 소수를 찾는 과..

문제 https://www.acmicpc.net/problem/1929 코드 #1 - WRONG❌ def is_prime(x): for j in range(2, x): if x % j == 0: return False return True min, max = map(int, input().split()) for i in range(min, max+1): if is_prime(i): print(i) 풀이 #1 - WRONG❌ 실버2인데 너무 쉽게 풀려서 의심스러웠는데 역시나... 시간초과가 떴다. 왜 그런지 백준에 올라와 있는 질문을 검색해보니 에라토스테네스의 체를 공부하고 풀어보라는 글을 발겼했다. 공부하고 다시 풀어봐야지~ 코드 #2 def is_prime_sieve(n, start): sieve = ..

에라토스테네스의 체는 뭘까? 가장 대표적인 소수를 판별하는 알고리즘이다. 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 일반적으로 소수를 구하는 알고리즘의 시간복잡도는 O(N)이다. BUT 에라토스테네스의 체를 사용하게 되면 시간복잡도를 O(N^(1/2))로 줄일 수 있다. 에라토스테네스의 체의 원리? 모든 약수들을 대친 형태를 이룬다는 점에서 가능하다. 예를 들어, 8의 약수인 2와 4를 보면 2\*4 = 4\*2 식에서 대칭인 것을 발견할 수 있다. 따라서 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다. 위의 예시로 다시 설명하면, 8의 약수를 구하기 위해서는 1, 2만 보면 된다. (8=2루트2) 🚩 하나의 소수 판별 def is_prime(x): end = int(x ** 0.5) f..