huiyu's blog

배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데, 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다. 쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다. -> 위키백과 냅색 문제는 아래 링크에서 풀어 볼 수 있습니다. ->0/1 Knapsack 문제 보러가..

문제)타일채우기(S)2x1 혹은 2x2 크기의 타일을 2xn 크기의 직사각형 모양 틀에 넣으려고 한다. 이 때 가능한 경우의 수를 구하여라. 경우의 수가 커지므로, 주어지는 수 m으로 나눈 나머지를 출력한다. 첫 줄에는 직사각형 틀의 가로 길이 n이 주어진다. 둘째 줄에는 m이 주어진다 (1

DFS/BFS의 경우 사실 이론은 조금만 읽어도 금방 이해가 가능한데요,그러나 막상 처음 구현하려 하면 바로 구현하기 힘든 경우가 많은데 알고리즘 문제를 반복적으로 풀며 구현해보면 금방 익숙하게 구현할 수 있게 됩니다. 다음은 DFS/BFS 학습을 위해 풀었던 문제들로[기본]은 간단하게 DFS/BFS를 이용하여 풀 수 있는 문제이고, [응용]은 DFS/BFS 중에도 조금 응용을 해야 풀 수 있는 문제입니다기본적인 이론을 학습한 후 아래 문제들을 순서대로 풀어보면 좋을 것 같습니다. [기본]1. 바이러스 : https://www.acmicpc.net/problem/26062. 단지번호 붙이기 : https://www.acmicpc.net/problem/26673. 보물섬 : https://www.acmic..