분류 전체보기

1차 캐시→체크리스트X, OrderedDict()★★

나의 풀이 from collections import OrderedDict def solution(cacheSize, cities): #city가 cache에 없는 경우에는 전부다 cache miss이다. if cacheSize ==0: return len(cities)*5 #cities의 요소를 저장하기 위한 cache공간으로 OrderedDict를 사용한다. cache=OrderedDict() #최초실행시간을 0으로 초기화한다. execution_time =0 #대소문자를 구분하지 않으므로 전부다 대문자로 바꾸어 놓는다. for city in cities: city=city.upper() #만약에 city가 cache안에 있다면 cache hit이다. if city in cache: execution..

멀리 뛰기 → 점화식★★ + 재귀함수★★ + 피보나치수열

실패한 풀이 #실패한 나의 풀이 def solution(n): if n==1 or n==2: return 1 elif n>2: return (solution(n-1)+solution(n-2))%1234567 ▶ 시간복잡도 O(2^n) 성공한 풀이- for문, 재사용 O def solution(n): if n==1 or n==2: return 1 result =[0]*(n+1) result[1]=1 result[2]=2 for i in range(3, n+1): result[i]=result[i-1]+result[i-2] return result[n]%1234567 ▶ for문을 써서 재귀함수의 호출을 방지하고, 배열을 사용하여 구한 값의 재사용성을 높인다. ▶ 시간복잡도 O(n)

예상 대진표 ★★

통상적인 풀이 def solution(n,a,b): # 발생할 수 있는 최대 라운드 수 계산 max_round = 0 while 2 ** max_round = mid: lower = mid mid = (mid + upper) // 2 max_round -= 1..

점프와 순간 이동→재귀함수(DFS)★★ + 동적 계획법

효율성 실패한 나의 첫번째 풀이 def solution(n): if n == 1 or n == 2: return 1 result = [0] * (n + 1) result[1] = 1 result[2] = 1 for i in range(3, n+1): # 이전에 구한 결과값을 재사용 if i % 2 == 0: result[i] = result[i // 2] else: result[i] = result[i-1] + 1 return result[n] ▶ for문 때문에 작은 수부터 큰 수까지 쭈욱 훑어서 효율성 테스트에서 계속 실패했다. 효율성 테스트를 통과한 풀이 def solution(n): if n==1 or n==2: return 1 if n % 2 ==0: return solution(n//2) el..