구현

프로그래머스: 숫자블록 (파이썬, 구현)

프로그래머스에는 약수를 구하는 문제가 꽤 많은데 그 중 한 문제이다. 길의 길이는 10^9이고 블록의 길이는 최대 10^7이기에 완전탐색을 하면 틀리는 문제이다. 약수를 효율적으로 구하는 것이 문제의 핵심인데 약수는 일일이 나눠서 구해야하므로 완전탐색으로 구해야하고, 더 빠르게 구하려면 약수는 제곱근 전 후로 쌍을 이룬다는 성질을 응용하여 제곱근까지만 약수를 구하고 그 약수들로 수를 나누어 나머지 약수들을 찾아야 한다. 먼저 내가 푼 코드이다. from bisect import bisect_left def get_yaksu(num): # 1은 모든 수의 약수 yaksu = [1] # 제곱근까지 약수를 구함 으로써 탐색 범위를 줄임 for i in range(2, int(num**0.5)+1): if nu..

백준 17135번: 캐슬 디펜스 (파이썬, 완전탐색, 구현)

정말 어려운 문제였다. 처음 문제를 봤을때 완전탐색 혹은 DP중에 고민했는데 시간복잡도가 M개 중에 3 개를 뽑는 조합 mC3 = m(m-1)(m-2)/6, 적들이 N번 움직이므로 반복문 O(N), 사정거리 D만큼, M열에 대해 거리를 탐색해야 하니 O(N^2)으로 M= 15, N = 15일 때 455*15*15*10= 10^6으로 시간제한인 1초에 넉넉하게 맞출 수 있어 완전탐색으로 풀어야 겠다고 생각할 수 있었다. 그러나 구현 문제를 거의 처음 풀어봐서 시간이 오래 걸렸는데 반복문이 많이 중첩되다 보니 순서나 반복값에 있어서 헷갈림이 많았다. 알고리즘은 간단하다. 먼저 조합으로 [0:M]에 대해 3개를 뽑는다. 이때 궁수의 위치는 N행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다. 그다음 적과..