개발자의 기록장 블로그

일단 물은 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[..

처음에 문자열을 보듯이 접근해 보았으나 코드를 써내려갈수록 굳이 ...? 란 생각이 들기 시작함.그래서 인덱싱을 대신할 방법이 무엇이 있을까 생각하다가 자릿수 개념을 떠올림. 인덱싱 대신에 자릿수 개념을 이용함1의 자리인 경우에는 참조만 당함!! 자릿수를 나타내기 위해 잠시 문자열로 형변환해서 len 함수를 이용함.def sum_digits(n): lens = len(str(n))-1 if lens == 0: return n return n // (10 ** lens) + sum_digits(n % (10 ** (lens)))

12345611+21+2+31+2+3+41+2+3+4+51+2+3+4+5+6 3번째 항은 2번째항 + 3, 4번재 항은 3번째 항 + 4n번째 항은 n-1번째 항 + n1번째 항은 참조당하기만 함!! 즉, base case는 Value로 구분되어지며, 1번항임.def triangle_number(n): if n == 1: return 1 return n + triangle_number(n-1)