영..환...코테..정..리한..다..하..기싫..다...그..래도...한..다... 1. 각 자리수의 합 10으로 나눈 나머지는 1의 자리 수기존의 수를 10으로 나눈 몫은 1의 자리 수를 날리는 것.n = int(input())answer = []while n != 0: answer.append(n%10) n = n // 10 2. 순열 검사 중복없는 배열인지. 배열의 길이 만큼만 있는지[4, 1, 2, 3] OK[4, 2, 3] No ->  4는 배열의 길이 3보다 크므로. 풀이 방법 1 : 확인해야 할 array와 길이가 같으며 index가 값의 위치이다.ex) index = 0 : 숫자 1의 위치 and 숫자 1이 array에 있는 개수 def solution(arr): answer ..

리스트안에 랜덤한 숫자 n개가 있을 때 n개의 합이 M보다 작으면서 최대한 가까운 수를 구하라고 했는데...3중반복문을 써서 n개의 합을 다 구했는데 좀 더 좋은 방법은 없을까?

분해합 문제나는 매번 정수 자릿수 문제는 문자열로 바꿔서 푸는데정수는 %로 다루어야 자릿수를 정수로 다룰 수 있다.근데 이거는 너무 복잡하지 않나아~~ 더 쉬운 방법있을까~~

이 문제는 예전에 최대 건물 높이 중에서 최소값이 빗물이 담길 수 있는  최대 값이라고 했었다.하지만 그렇게 하면 O(n^2)의 시간복잡도를 가지는데... 이를 해결하려면 최대 건물 높이를 미리 알아놓으면 좋을 것 같다. def trapping_rain(buildings): container = 0 left = [] right = [] for i in range(len(buildings)): left.append(max(buildings[:i+1])) right.append(max(buildings[i:])) for i in range(len(buildings)): container += (min(left[i], rig..

탐색이란 의미를 잘 살펴보자. 0번 인덱스 1을 취했을 때, 15가 되려면 11을 선택해야 될 가능성이 존재한다.이때 12는 15보다 작으므로 좌측 값을 늘려야한다. 1번 인덱스 2를 취했을 때 15가되려면 11을 선택해야 한다.이때 13이므로 좌측 인덱스를 늘린다.5와 11의 경우 15보다 크므로 우측 인덱스를 줄인다. 이런 방식으로 가다보면 값이 없는 경우는 O(n)이고 값이 있으면 탐색된다. def sum_in_list(search_sum, sorted_list): left = 0 right = len(sorted_list)-1 for i in range(len(sorted_list)): if sorted_list[right] + sorted_list[left] ..

위의 계단의 위치를 생각해보면, 1->2->3->42->3->41->3->42->4 이다. 즉 4번째 계단에 도착하려면 2번째 계단이나 3번째 계단에서 출발해야한다.식을 쓰면 stair(4) = stair(3) + stair(2)이고 이 식은 피보나치 식과 같다. def staircase(n): temp1, temp2 = 1, 1 for i in range(n): temp1, temp2 = temp2, temp1+temp2 return temp1  계단 올라가는 수를 조정한다면?   이 경우에도 마찬가지로 stair[n] 을 올라가려면 stair[n-k] + stair[n-l] + --- 이런 식이다.def staircase(stairs, possible_steps):..

1. BruteForce def max_profit(stock_list): max_profit_so_far = stock_list[1] - stock_list[0] for i in range(len(stock_list)): for j in range(i+1,len(stock_list)): max_profit_so_far = max(max_profit_so_far, stock_list[j] - stock_list[i]) return max_profit_so_far하나하나 보면서 모든 경우를 살펴보면 된다. O(n^2) 2. So_Far def max_profit(stock_list): max_profit_so_far = stock_list[1] ..

1. O(n) 저장소 활용  값이 없으면 딕셔너리에 저장하고, 값이 있으면 그 즉시 원소를 리턴해주면 된다. def find_same_number(some_list): container = {} for ele in some_list: if ele in container: return ele container[ele] = True 2. 저장소 활용하지 않고 풀기  사실 N+1 크기의 리스트에 1~N까지 자연수가 할당되려면 무조건 중복되는 놈이 하나씩 생긴다.그 중복되는 값만 찾으면 되므로 중복되는 녀석이 있는 범위를 좁혀나가면서 구하면 될 듯 하다.줄여 나간다는 것은 divide 한다는 것이고 이는 재귀적으로 문제를 해결해나간다는..