개발자의 기록장 블로그

logN의 시간복잡도를 가지려면 문제의 크기가 절반씩 줄어들어야 한다. 그렇다면 문제의 크기를 절반 씩 줄이는 것에 목표를 두자. power(3,5)라면, power(3,2) * power(3,2) * power(3,1) -> power(3,1)*power(3,1)*power(3,1)*power(3,1)*power(3,1)원래라면 5의 시간복잡도가 3이 됐다. 즉 y값에 따라서 문제의 크기를 절반씩 줄여주면 된다.  def power(x, y): if y == 0: return 1 if y % 2 == 0: return power(x, y//2)*power(x,y//2) else: return power(x,y//2)*power(x,y//2)*..

1. Brute Force기본 값으로 가장 첫 날의 수익을 지정 수익은 지금까지의 구한 수익 + 당일 수익 으로 구할 수 있다. def sublist_max(profits): profit = [profits[0]] for i in range(1, len(profits)): profit.append(profit[i-1] + profits[i]) return max(profit) 2. Divide and Conquer basecase는 start == end 수익율이 최대인 구간은 리스트 중앙을 기준으로 왼쪽에 있거나 오른쪽에 있거나 중앙을 관통할 수 있다.리스트를 좌 우 로 나누는 것은 재귀로 해결 중앙을 관통하는 구간의 최대값을 알기 위해서는 따로 함수의 분리 필요 -..

일단 물은 0번과 -1번 인덱스에는 찰 수 없다. 양 옆에 막아줄 빌딩이 없기 때문! 해당 인덱스 양 옆에 자신보다 큰 건물이 있으면 물이 들어감자신의 왼쪽과 오른쪽 건물중에서 가장 큰 건물 중 제일 작은 건물의 높이가 물이 들어갈 수 있는 최대 높이임최대 높이에서 자신의 높이를 빼주면?! 그 인덱스에 들어가는 물의 양이 됨!  def trapping_rain(buildings): rain_container = [] for i in range(1,len(buildings)-1): max_left = max(buildings[:i]) max_right = max(buildings[i:]) upperbound = min(max_left, ..

튜플 두개를 넘기면 거리 계산을 해주는 함수를 distance로 정의해서 참조하자.일단 거리를 계산해서 최소거리를 구하는 것은 어렵지 않다.그런데 그 최소거리가 누구의 것인지 알려면, 반드시 key-value 쌍의 데이터 구조여야 한다.따라서 dict 구조를 사용했다. from math import sqrtdef distance(store1, store2): return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)def closest_pair(coordinates): container = {} def find_value(x): return container[x] for i in range(len(c..

Brute Force 해결방식의 핵심은 가장 무식하게 하나하나씩 다 해보는 것이다.하나 하나씩 1:1 매칭을 해준다 -> 2중 for문 사용곱했을 때 최대가 되는 수부호가 다를 때와 같을 때 고려해야 하는 지 생각해 보았으나 최대값만 리턴하면 되므로 상관없음!def max_product(left_cards, right_cards): # 코드를 작성하세요. ans = [] for i in range(len(left_cards)): for j in range(len(right_cards)): ans.append(left_cards[i]*right_cards[j]) return max(ans)

하노이 탑 문제를 보고 간단한 것 같은데 간단하지 않았다... 그래서 일단 수열을 풀듯 4번까지는 직접 그려가면서 생각해 보았다. 원판의 개수가 1개일 때, 1번 기둥에서 3번 기둥으로 옮기면 끝원판의 개수가 2개일 때, 1번째 원판을 2번기둥으로 옮겨주고, 2번째 원판을 3번기둥으로 옮겨주고 1번째 원판을 3번째 기둥으로 옮겨준다.원판의 개수가 3개일 때, 1번째와 2번째 원판을 2번기둥으로 옮겨주고, 3번째 기둥을 3번기둥으로 옮겨주고, 1번째와 2번째 기둥을 3번째 기둥으로 옮겨준다원판의 개수가 4개일 때, 1,2, 그리고 3번째 원판을 2번 기둥으로 옮겨주고...위의 과정을 통해 생각해보니 공통적으로 나오는 움직임을 찾았다. 1번 기둥에서 2번 기둥으로 옮기기1번 기둥에서 3번 기둥으로 옮기기2번..

이진탐색 알고리즘은 start idx와 end idx로 범위를 지정해놓고, mid idx로 값을 찾아가며 탐색 범위를 1/2씩 줄여나가는 알고리즘이다.  즉 원본 리스트를 절반씩 나누어 가면서 범위를 줄여나가는게 목표인데재귀를 이용하려면 절반씩 나누는 과정을 재귀적으로 진행하면 될 것 같다.값을 찾으면 그 index 리턴 리스트 내에 값이 없으면 종료를 시켜야 하는데, start idx 는 항상 end idx보다 작아야하므로 start idx > end idx면 종료def binary_search(element, some_list, start_index=0, end_index=None): if end_index == None: end_index = len(some_list) - ..

리스트를 뒤집는 것은 그냥 for문을 돌리면서 some_list[i], some_list[-(1+i)] = some_list[-(1+i)], some_list[i] 이런식으로 하면 될탠데이 문제는 재귀적으로 접근해야 하므로 다른 방식이 필요했다. 문제를 큰 문제와 작은 문제로 나누어서 생각해보았는데하나의 큰 리스트가 있다면, 이를 뒤집기 위해서는 맨 앞 혹은 맨 뒤의 값을 조정해야한다.근데, 맨 앞을 뒤로 보내는 것보다, 맨 뒤를 앞으로 가져오는게 더 조정하기 쉬울 것 같아서 맨 뒤의 값과 나머지 리스트로 나누는 방식을 선택했다. 리스트를 recursive case와 base case로 나누기base case => 길이가 1이고, 파라미터 리스트의 -1 인덱스 값recursive case => list[..