새벽의 블로그

import heapqdef solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0]  1. heapify 사용 오류 heapify 는 heapq.heapify(list_name) 방법으로 사용하고, 리스트 자체가 힙이 된다.2. while문 조건 & 만들어지지 않는 조건 잘못 사용어차피 최소힙이므로 이 중 최소값만(즉 [0]값) K보다 큰 지 작은 지 while loop 검사하면 된다. 또한 반복할 수록 두 가지 음식이 하나로 합쳐지기 때문에, 초기 조건이 음식은 2가지 이상인 것이다. 반복할 수록 음식의 수는 줄어들고, 만약 1개까지 줄어들었다면 더 이상 음식을 합칠 수 없고, 이때도 목표 스코빌 지..

다이나믹 프로그래밍이란?똑같은 계산을 반복하지 않기 위해서, 한 번 계산한 값을 메모리에 저장하였다가, 그 계산이 필요할 때 가져다 쓰는 방법> 불필요한 반복계산을 줄여서 시간효율이 높아진다. 백준 1463번숫자 x를 입력으로 받는다.1. 3으로 나누어지는 수라면 3으로 나눈다.2. 2로 나누어지는 수라면 2로 나눈다.3. 1을 뺸다. 이 세 가지 연산을 적절히 사용해서 최소 계산 횟수로 최종 1을 만드는 문제. 만약 입력이 10이라면f(10) > f(9), f(5)f(9) > f(8), f(3)

for loop 중첩으로 돌면서 검사하면 시간초과 날 줄 알고 다른 방법을 찾아다녔는데 시간 초과 안 난다 ..def solution(citations): how = len(citations) s = set() citations.sort() for i in range(0,how+1): temp= 0 for j in citations: if j >= i: temp += 1 if temp >= i: s.add(i) return max(s)

*정석 이론dfs는 stack을 사용한다. 재귀적 방법이다..- 방문한 노드의인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 방문한다.- 그 방문 노드의 인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 또 방문한다.- 방문할 인접 노드가 없다면 (=leaf에 다다른 것이다) stack에 넣어놨던 노드를 꺼내어 반복한다. (가장 최근에 들어간 노드가 나오므로, 그 부모 노드가 나와서 거꾸로 거슬러 올라갈 수 있다.) bfs는 queue를 사용한다. - 방문한 노드의 모든 인접 노드를 queue에 삽입한다.- queue에서 다음노드를 꺼내어 다시 모든 인접 노드를 탐색한다.- 방문할 노드가 없을 때까지 반복한다. *그래프-노드 표현은 인접그래프, 인접..