알고리즘문제
-
알고리즘: 백준 3190번 뱀 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 20. 11:06
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net import sys from collections import deque read = sys.stdin.readline N = int(read()) K = int(read()) snake = [[0 for _ in range(N)] for _ in range(N)] snake[0][0] = -1 apple = [[0 for _ in range(N)] for _ in range(N)] for i in range(K): ay, ax = list(map(int, read()..
-
알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)알고리즘 2020. 11. 6. 14:42
탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다. 반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해 최적의 해를 갖지 않는다는 것을 증명한다. 이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는 두가지 문제를 살펴본다. 우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. < 0-1배낭채우기 문제(0-1 knapsack prob..