본문 바로가기

메모이제이션2

[백준] 1463번: 1로 만들기 Hint 1. n에서 2나 3을 나누거나 1을 뺄 생각하지 말고 1부터 고려하는 코드로 짜야함 2. 1부터 n까지의 숫자를 각각 만들기 위해선 몇번의 연산 횟수가 필요한지 생각해봐야 함 3. Memoization 기법 활용 백준 1463번: 1로 만들기 (풀어보기) n = int(input()) ans = [0] * (n+1) # ans[i] = i가 1이 되기 위한 연산 횟수 for i in range(2, n+1): ans[i] = ans[i-1] + 1 # 디폴트로는 그 전 숫자에서 +1 한거니까 횟수도 그 전 숫자의 횟수에 +1 한것임 if i % 3 == 0: ans[i] = min(ans[i], ans[i // 3] + 1) # 디폴트와 x3 하기 전의 숫자의 횟수에서 +1 한거 중에 더 작은.. 2023. 2. 17.
에라토스테네스의 체 Goal 1. 소수 정의하기 2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기 소수란? 소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다! 예시) 소수 : 2, 3, 5, 7, 11, 13, 17, 19, ... 그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ... "에라토스테네스의 체"는 언제 필요한가? N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다 .. 2023. 2. 13.

티스토리툴바