분류 전체보기 (42) 썸네일형 리스트형 [Problem] 배낭 문제의 그리디 알고리즘적 접근 (Knapsack, Greedy) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. 그리디 배낭 (GreedyKnapsack) 클래스 구현 class GreedyKnapsack(Knapsack): def get_algorithm(self): return 'Greedy' def fractional_solve(self): # TODO: 분할 배낭 문제를 그리디로 구현 3.3.1. 0-1 배낭 문제 접근 0-1 배낭 문제를 그리디 알고리즘적으로 접근할 수 있을까? DP에서 사용한 단위 무게당 가치의 개념을 다시 사용해보자. 물체를 단위 무게당 가치 내림차순으로 정렬한 다음 배낭에 넣을 수 있는 만큼 차례로 넣는다면 반드시 최고 가치를 가질 수 있을까? 그렇지 않다. 안타깝게도 단위.. [Problem] 배낭 문제의 동적 계획법 알고리즘적 접근 (Knapsack, Dynamic Programming) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. DP 배낭 (DPKnapsack) 클래스 구현 from functools import cmp_to_key from knapsack import Knapsack class DPKnapsack(Knapsack): def get_algorithm(self): return 'Dynamic Programming' def zero_one_solve(self): # TODO: 0-1 배낭 문제를 DP로 구현 def fractional_solve(self): # TODO: 분할 배낭 문제를 DP로 구현 3.2.1. 0-1 배낭 문제 접근 동적 계획법의 조건 최적 하위 구조 (Optimal Substructu.. [Problem] 배낭 문제의 브루트 포스 알고리즘적 접근 (Knapsack, Brute Force) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. 브루트 포스 배낭 (BFKnapsack) 클래스 구현 class BFKnapsack(Knapsack): def get_algorithm(self): return 'Brute Force' def zero_one_solve(self): # TODO: 0-1 배낭 문제 브루트 포스로 구현 3.1.1. 0-1 배낭 문제 접근 $n$ 개의 물체를 배낭에 넣고자 할 때, 가능한 경우의 수는 집합 $A$의 가능한 부분집합의 개수인 $2^n$ 이고, 이는 곧 시간 복잡도가 $O(2^n)$ 임을 의미한다. 기하급수적 복잡도(Exponential Complexity) 를 지닌 해당 접근은 별로 좋지 못하다고 할 수 있다. 구.. [Problem] 배낭 문제 (Knapsack Problem) 1. 개요배낭 문제 (Knapsack Problem)는 최대 수용 무게가 있는 어떤 배낭에 각각의 특정 가치를 갖는 여러 물체를 넣되, 배낭이 지니는 가치가 최대가 되도록 하는 물체의 조합을 찾는 문제를 의미한다.기본적으로 다음을 정의하면,배낭의 최대 수용무게: $W_{ \max }$물체의 집합: $A = \{ a_i | 0 \lt i \le n \}$물체의 개수: $n$$i$ 번째 물체의 무게: $w_i$$i$ 번째 물체의 가치: $v_i$물체: $a_i = (w_i, v_i)$물체 ($a_i$)$a_1$$a_2$$\cdots$$a_n$무게 ($w_i$)$w_1$$w_2$$\cdots$$w_n$가치 ($v_i$)$v_1$$v_2$$\cdots$$v_n$$W_{ \max }$ 만큼 수용할 수 있는 배낭에.. [Algorithm] 그리디, 탐욕 (Greedy) 1. 개요 그리디 (Greedy), 탐욕 알고리즘 (이하 그리디) 은 어떠한 것을 선택할 상황이 발생하면 항상 그 시점의 최선의 선택을 해나가는 방식을 의미한다. 근사적인 최적해 (이하 근사해) 를 구할 수 있다는 특징이 있다. 근사해가 최적해 만큼 의미있게 취급될 경우 주로 사용한다. * 근사해라고 표현되는 이유는 그리디가 항상 최적해를 구할 수 있는 것은 아니기 때문이다. 따라서 최적해를 구하기 위한 근사적인 방법 이라는 것만 이해하면 충분하다. 그리디를 적용하기 전, 다음의 경우를 만족하는가를 파악할 필요가 있다. 현재 선택이 미래의 선택에 독립적인가? 하위 문제를 통해 전체 문제를 해결할 수 있는가? 2. 의의 그리디는 DP를 사용하는 경우 중, 특정 경우에 대해 속도를 향상 시키기 위해 사용한다.. [Baekjoon] 2096번 내려가기 G5 2096번 - 내려가기 1. 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, .. [Flutter] 토스 스타일의 Pressable 커스텀 위젯 만들기 1. 개요 Flutter 의 대부분의 누를 수 있는 위젯은 InkWell animation 이 채택되었다. 위젯을 탭하면 위젯 색상이 highlight 되고 탭 위치부터 원이 splash 되어 퍼져나간다. TextButton, IconButton, InkWell 위젯의 예시 위 gif 의 코드는 아래와 같다. import 'package:flutter/material.dart'; void main() => runApp(const MyApp()); class MyApp extends StatelessWidget { const MyApp({super.key}); @override Widget build(BuildContext context) { return MaterialApp( debugShowChecke.. [Baekjoon] 1065번 한수 S4 1065번 - 한수 1. 문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. Input 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. Output 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 2. 사용 알고리즘 완전 탐색, 브루트 포스 (Brute Force) 3. 풀이 자연수 N 자연수 $N$은 $1000$ 보다 작거나 같으므로 수열의 항은 최대 4개이다. $N < 100$ $N$은 한 자리 수 혹은 두 자리 수 이므로, 모든 경우에서 등차수열의 특징을 만족.. 이전 1 2 3 4 5 6 다음
