정글에서 온 개발자

입력이 적고(8), 문제 자체가 대놓고 완전탐색이라고 써있기 때문에 딱히 그리디를 안 따지고 풀었지만, 좀 더 빠른 코드를 고민하면서 그리디를 생각해볼 수도 있다. 그리디로 풀 수 있을까?그리디의 두가지 조건최적 부분 구조 : 문제의 최종 해결책이 부분 문제의 최적 해로 구성되어야 한다.탐욕적 선택 속성 : 각 단계의 선택이 이후의 선택에 영향을 주지 않는다.최적 부분 구조적은 소모 피로도부터 들르기얼핏 생각하기에, 최대한 많이 들르려면 피로도가 적게 드는 것부터 가야 할 것 같다.반례: [[80,20],[50,40],[30,10]] K=802→0→1 순으로 들르려고 하면 0번째에 피로도가 모자라서 1개 밖에 못 들른다.많은 필요 피로도부터 들르기그렇다면 많은 피로도부터 들르면 괜찮을까?반례: [[80,..

다양한 전체 순회permutation가장 간단하게 순열을 사용할 수 있다.from itertools import permutationsdef solution(k, dungeons): mx = 0 for perm in permutations(dungeons, len(dungeons)): hp = k visit = 0 for need,cost in perm: if(hp >= need): visit+=1 hp-=cost else: break mx = max(mx,visit) return mxPermutation 직접 구현직접 ..

부끄럽지만 원래 코드def solution(brown, yellow): MAX = int(yellow**0.5) isPrime = [True]*(MAX+1) prime = [] isPrime[0],isPrime[1] = False,False for i in range(2,MAX): if(isPrime[i]): prime.append(i) for k in range(2*i,MAX+1,i): isPrime[k]=False m = 1 n = yellow while(yellow>2): for p in prime: if(yellow%p==0): ..

좋은 코드 훔쳐오기def solution(numbers): Num = set() def perm(pick,unpick): if(pick!=''): Num.add(int(pick)) for i in range(len(unpick)): perm(pick+unpick[i], unpick[:i]+unpick[i+1:]) perm('',numbers) Num-={0,1} for i in range(2,int(max(Num)**0.5)+1): Num-=set(range(i*2,max(Num)+1,i)) return len(Num)관전 포인트itertools의 permutation을 쓰지..

코드import randomA = 0 # 구간의 최소값B = 1000 # 구간의 최대값L = 100 # 배열 최대 크기def correct_solution(numbers): answer = numbers # 정답 코드 return answerdef my_solution(numbers): answer = numbers # 내 풀이 코드 return answer def generate_random_numbers(a,b,n): return [random.randint(a,b) for _ in range(n)]def compare_solution(numbers, i=0): result1 = correct_solution(numbers) result2 = my_sol..

시도BruteForce로 비교 못함배열의 길이가 N 일 때 O(N!) 만큼 시간이 걸려 문자열을 생성해서 비교해야 한다. 생성된 문자열을 숫자로 바꾸어 비교해야하는데, 이때 숫자의 최대 길이는 1e5 * 1e3 으로 1e8 (숫자의 크기가 아니라 숫자의 길이라는데 유의) 이기 때문에 이 숫자를 2진수로 표현만 해도 약 41.52MB 를 잡아 먹는다. ( 10^(10^8) 에 밑이 2인 log를 취한 값 만큼 비트가 필요함 )가장 먼저 떠올리기 쉬운 정렬인 ‘사전식 순서(lexicographical order)’ 정렬을 해도 안 풀림[2,20,9] 을 사전식으로 정렬하면 [2,20,9] 가 나온다.사전에서는 더 짧은 숫자가 앞에 나오기 때문이다.큰 수를 만들기 위해서는 이걸 거꾸로(reverse) 해야 하..

13335번: 트럭 접근 방법 큐로 풀면 될 것 같다. 크게 2가지가 있다. 트럭이 나와야할 시간 체크하기 트럭을 큐에 넣을 때 진입하는 시간을 같이 넣는다. 트럭이 나올 때가 됐는지 시간별로 체크한다.(트럭시간 + L이 나올 시간이다.) 트럭이 이동하는 다리 시뮬레이트 하기 시간마다 실제로 트럭의 무게를 큐에 넣는다. 트럭이 들어가지 않아야할 때는 0을 넣는다. 시간마다 큐에서 pop한다. 트럭이 나와야 할 시간 체크하기 from collections import deque N,L,W = map(int,input().split()) A = deque([*map(int,input().split())]) t=0 Q=deque([]) totalWeight = 0 while A: t+=1 if(Q and t>..

첫번째 시도 최소힙, 최대힙 두개를 운용하고, size만 조절해 D연산시 size 이상으로 pop을 못하게 하면 되지 않을까? import heapq T=int(input()) for _ in range(T): k = int(input()) sQ = [] lQ = [] size=0 for _ in range(k): cmd, num = input().strip().split() num = int(num) if(cmd=="I"): heapq.heappush(sQ,num) heapq.heappush(lQ,-num) size+=1 if(size>0 and cmd=="D"): size-=1 if(num==1): heapq.heappop(lQ) elif(num==-1): heapq.heappop(sQ) if(siz..

Two Sum LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제의 핵심 합이 특정 값이 되는 두 수를 O(n)에 찾을 수 있는지? O(n^2) class Solution(object): def twoSum(self, nums, target): length = len(nums) fin=False for i in range(0,length): for j in ..

개요 JDBC(Java Database Connectivity) - 1990 중반. 자바 프로그래밍 언어의 일부 JdbcTemplate - 2000년 초. Spring Framework의 일부. Spring과 함께 등장 JPA(Java Persistence API) - 2000년대 중반. 자바 EE 표준. ORM(Object-Relational Mapping)을 위한 API 제공. Hibernate는 JPA의 구현체 Spring Data JPA - 2010년 초. Spring Data 프로젝트의 일부. JPA를 더 쉽게 사용 리포지토리 계층 쉽게 구현하는 추상화 제공 Spring Data JDBC - 2010년 후반. Spring Data JDBC. JPA의 복잡성을 줄이고자 등장. 도메인 중심 설계 촉..