killog

dp가 너무 안돼서 dp 조지기를 하는 중 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. N = int(input()) dp=[100000000]*(N+5) dp[0]=0 dp[1]=0 dp[2] =1 dp[3]=1 dp[4] =2 i = 4 while i

보호되어 있는 글입니다.

유명한거랑 내가 풀수 있는거랑은 다르지. 내눈엔 dp로 안풀린다. 손코딩하다가 몰라! 하고 답보는 중.. 내일이 코테라면 어떡하냐 그런데 확실히 뭔가 좀 알겠는게 dp 를 배열로 만들고 항상 반복문을 통해 dp 배열을 채워나가는 형식인 것 같다. 요소들을 배열에 넣어 놓는다는 것을 이제 깨우쳤다. 동적 프로그래밍을 이용해서 시간복잡도 O(nk)로 문제를 해결할 수 있다. 🎈 문제 풀이의 핵심 아이디어 => 이진 행렬로 문제를 품 핵심아이디어: 모든 무게에 대하여 최대가치 저장하기 D[i][j] = 배낭에 넣은 물품의 무게 합이 j 일때 얻을 수 있는 최대 가치 각 물품 번호 i 에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결할 수 있다. (이 식은 외워야합니다. 암기암기암기 이 친구때문..

동적 프로그래밍 특징: 한번 구한 값은 다시 구하지 않는다. 점화식을 잘 짜야 풀 수 있는 문제 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되..

문제를 푸는건지..답을 보는건지.. 머리가 안돌아간다. 위상정렬을 공부해보자. 문제유형: 힙, 위상정렬 문제 난이도 : 중 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드..

내가 푼 풀이랑 while 조건문 하나 달랐는데 왜 난틀린건지....... 정답을 공유한다. 그리고 최대한 재귀보다는 while 문이 에러가 덜남을 잊지말자 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10+20)+(30+40..

문제 널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하..

** 힙 구현** 일반적으로 힙 구현시 배열 자료구조를 활용한다. 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월하다. 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 //2 왼쪽자식 노드 인덱스 번호 = 부모노드 인덱스 번호 *2 오른쪽 자식 노드 인덱스 번호 = 부모노드 인덱스 번호 * 2+ 1 heap = Heap(15) heap.insert(10) heap.insert(8) heap.insert(5) heap.insert(4) heap.insert(20) heap.heap_array heap.pop() # 20 # [None, 20, 10, 15, 5, 4, 8]class Heap: def __init__(self, da..