320x100 PS84 [Codewars]5kyu - Sum of pairs 어떤 수들의 리스트가 주어지고, target이 주어지는데, list에서 target을 맞추기 위한 쌍을 찾아서 return하면 된다. 쉬워 보이는데 막상 하면 어렵다. 그냥 이중 for문을 사용하면 무조건 시간 초과가 뜬다. NOTE에 쓰여 있듯이 길이가 천만이 넘는 리스트도 나오기 때문이다. 그리고 문제의 설명이 좀 모호한 점이 있는데, 해당 target을 만들기 위한 쌍이 여러개 있다면 두 수의 인덱스 중 나중 인덱스가 가장 빠른(왼쪽에 있는) 쌍을 골라 내보내야 한다. 이중 for문을 사용한다면 시간 복잡도는 O(n^2)이고 그 코드는 이렇다. def sum_pairs(ints, s): for i in range(1,len(ints)): for j in range(i): if ints[i] + in.. 2021. 1. 31. [CLASS 3]백준 1676번, 2579번 1676번 : 팩토리얼 0 의 개수 상당히 쉬운 문제이다. 일단 팩토리얼을 그냥 구하고 10으로 나누는 방법을 쓰면 무조건 시간 초과를 맞을 것이다. 그러므로 모두 더하는 방식이 아닌 다른 방식을 사용했다. 내 코드: def zeroCount(n): f = 0 t = 0 for i in range(n,0,-1): k = i while k % 5 == 0 or k % 2 == 0: if k % 5 == 0: k //= 5 f += 1 if k % 2 == 0: k //= 2 t += 1 return min(f,t) print(zeroCount(int(input()))) 이렇게 각각 f와 t 변수에 곱하는 모든 수의 소인수 중 5와 2의 개수를 저장한 뒤 마지막에 그중 크지 않은 값을 반환하는 방법으로 풀 .. 2021. 1. 30. [CLASS 3]백준 1463번 - 1로 만들기 1463번 : 1로 만들기 내 개인적인 생각으로 이 문제를 가장 명료하게 풀 수 있는 방법은 재귀인것 같다. 그러나 수가 커지면 너무나도 많은 재귀를 해야 하기 때문에 비효율적이다. 내 코드(재귀): # 재귀(재귀스택 초과) n = int(input()) def find(n): countList = [] if n == 1: return 0 countList.append(find(n-1) + 1) if n % 3 == 0: countList.append(find(n//3) + 1) if n % 2 == 0: countList.append(find(n//2) + 1) return min(countList) print(find(n)) 1이 아니라면 해당 수에서 1을 뺀값, 2로 나누어 떨어진다면 2로 나눈 값.. 2021. 1. 29. [CLASS 3]백준 1003번 - 피보나치 함수 1003번 : 피보나치 함수 생각보다 애를 먹었던 문제이다. 규칙성을 찾을 생각은 하지 않고 무작정 0을 호출하면 변수에 1을 더해야지! 라는 생각에 갇혀있었던 것 같다. 이후 0을 호출하는 수의 규칙성을 찾아보았는데, 문제를 아주 쉽게 풀 수 있다. n 0 1 2 3 4 5 6 7 8 0 호출 1 0 1 1 2 3 5 8 13 1 호출 0 1 1 2 3 5 8 13 21 이를 확인하면 규칙성을 쉽게 발견할 수 있다. 먼저 1 호출은, 그냥 해당 피보나치 수와 값이 같다. 애초에 재귀를 통해 푸는 풀이에서 어떤 피보나치 수를 매개변수로 넘기던, fibo(1)을 수많이 호출하고 더해서 해당 값을 만들기 때문이다. 0을 호출하는 횟수는 제일 앞이 0 으로 시작하는 것만 제외하면 1 호출과 같은 순서를 띄고 .. 2021. 1. 29. 이전 1 ··· 14 15 16 17 18 19 20 21 다음
