안녕하세요? 코딩충입니다.오늘은 코딩계에서 꽤나 유명한 knap-sack 문제에 대해서 포스팅 하겠습니다. 사람들에 따라서 베낭 문제, 보석가게 도둑 문제 등등 다양한 이름으로 불리웁니다. 문제에 나오는 사람도 도둑, 여행자 등 다양하고 가방, 배낭 등 들고가는 것도 다양하며,가지고 가는 것도 보석, 짐 등 다양하며, 한정된 것도 무게, 크기 등 다양하며, 짐을 나눌 수 있는 문제와 없는 문제 등 다양합니다. 하지만 핵심은 같습니다.자원을 희생시켜서 이득을 얻을 때 최소 자원으로 최대 이득 얻기. 저희는 이 다양한 문제들 중에서 0-1 베낭 문제를 다루겠습니다.가장 간단하고 기본적인 문제입니다.0-1 배낭문제와 다른 변형문제들은 이 포스팅의 메인 주제가 아니니, 위키피디아를 참고해주시길 바랍니다.0-1 ..
안녕하세요? 코딩충입니다. 코딩에 관련해서 [유용하게 쓰이는 것들]이라는 카테고리를 새로 만들었습니다.아무래도 코딩 초보분들(뭐 저도 코딩 초보 수준으로 갓 졸업한 코더지만)은 코딩을 많이 한 분들에 비해 경험이 적다보니 코딩의 지름길(?)으로 못 가시고 어려운 길로 가시게 되는데 이런 일을 방지하기 위해 똑같은 일을 쉽게 하실 수 있도록 이 카테고리를 만들었습니다. 어려운 길로 가봐야지 느는것도 사실이지만 필요없는 생노가다에 시간을 보낼 필요는 없잖아요? 그래서 이 카테고리를 만들었습니다.어떻게 보면 STL도 지름길(?)의 한 종류라고 볼 수 있는데 STL은 처음부터 쓰시면 안되고, 구현을 완벽하게 할 수 있는 경지에 이르렀을때만 STL을 쓰셔야 됩니다. 특히 stack이나 queue 같은 경우는 더 ..
이번 대회는 A, B 2문제를 해결함으로써1500 -> 1431(-69) 레이팅으로 마무리했다. 이번 라운드는 A문제가 조금 특이했다(보통 대회에 안 나오는 문제였다). A. Letters Deque 간단하다. 그냥 문자열 덱을 구현하는 문제였다. 앞에 push할지, 뒤에 push할지 알려주고 문자열을 받아서 deque에 넣는 문제였다.나는 stl deque를 사용하여 풀었다.8분이나 걸려서 푼게 조금 아쉬웠다. 12345678910111213141516171819202122#include #include using namespace std;dequed;int main() { int n; cin >> n; for (int i = 0; i > a; cin >> s; if (a == 1)d.push_back..