Sangmun

분할이 불가능한 배낭문제를 0-1 배낭 문제라고 한다. https://www.youtube.com/watch?v=A8nOpWRXQrs&t=3s * 동적 계획법으로 푸는법 n = 3 W = 30 w = [0,5,10,20] p = [0, 50,60,140] # 구하고자 하는것 # p[3][W] = p[3][30] def knapsack2(i, W, w, p): if (i

https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C 배낭 문제 - 나무위키 무게 대비 가치가 다른 물건들을 일정한 용량의 용기에 담아야 한다는 기본 틀에서, 바리에이션이 많다. 가방이 여러 개인 문제, 고려할 변수가 무게와 가치 외에도 더 있는 3개 이상의 변수 문 namu.wiki https://www.youtube.com/watch?v=8UVDnahV1eg 분할 가능한 배낭 채우기 문제 그리디 알고리즘으로 정렬을 해서 무게를 채워주면 된다. Frational Knapsack Problem 탐욕알고리즘을 이용해서 최적의 해를 구할 수 있다. def knapsack1(W,w,p): n = len(w) - 1 K = [0] * (n + 1) weigh..

class Queue: def __init__(self): self.arr=[] def push(self,a): self.arr.append(a) def pop(self): del self.arr[0] def size(self): return len(self.arr) def top(self): return self.arr[-1] def siz(self): #size는 다른 함수로 이미 사용되고 있기 때문에 사용 불가... return len(self.arr) 큐 대표 문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www...

https://velog.io/@changyeonyoo/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EC%8A%A4%ED%83%9DStack%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0 [자료구조] 파이썬으로 스택(Stack)구현하기 파이썬(python)으로 스택(stack) 자료구조를 구현해보자파이썬에 내장되어 있는 Data-type중 리스트(list)를 이용하여 구현했다.Stack 클래스를 생성하고 init method를 이용하여 멤버 변수를 만들어준다.top velog.io 스택 대표 문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) arr_list = list(map(int, input().split())) X = int(input()) arr_list.sort() left, right = 0, N -1 result = 0 while left < right: tmp = ar..

import sys input = sys.stdin.readline n, m = map(int, input().split()) a_list = list(map(int,input().split())) total_result = [] result = [] def BT(depth): if depth == n: total_result.append(result.copy()) return result.append(a_list[depth]) BT(depth+1) result.pop() BT(depth+1) BT(0) print(total_result)

코딩테스트에서 종종 나오는 정수론 문제 관련한 코드를 정리해보고자 한다. 유클리드 호제법에 대한 설명 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 ko.wikipedia.org * Greatest common divisor(gcd) def gcd(a, b): while b > 0: a, b = b, a % b return a..

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간 ko.wikipedia.org 알고리즘 문제에 종종 등장하는 단골 문제이다. 위키에 나온 파이썬 코드는 아래와 같다. def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n # n의 ..