CS(Computer Science)지식/[C++][코딩 테스트] 자료구조 및 알고리즘60 백준 1202번: 보석 도둑(C++) https://www.acmicpc.net/problem/1202 해당 문제를 풀 때 가장 중요한 것은 어떤 조건에서 가장 이득을 보는지 생각해야 한다. 우선 쉽게 정답을 먼저 말하면 가장 가격이 비싼 보석을 가장 무게가 적은 가방에 넣는 과정만 생각하면 상덕이가 훔칠 수 있는 보석의 최대 가격을 구할 수 있다. 우선 보석의 무게와 가격이 중복될 수 있고 가방의 무게도 중복될 수 있으므로.. 중복을 고려한 자료구조를 사용 해야 되고 보석 같은 경우 가격에 따라서 정렬 해야지 가장 비싼 보석부터 가방에 넣어볼 수 있고, 가방 같은 경우도 가장 무게가 적은 가방에 넣는 과정을 진행해야 하므로 무게에 따른 정렬이 필요하다. 따라서 다음과 같이 코드를 작성 하였다. 헷갈렸던 부분을 하나 이야기 해보자면 보석의 .. 2024. 1. 31. 백준 7662번: 이중 우선순위 큐 (C++) https://www.acmicpc.net/submit/7662 우선 해당 문제는 바킹독님 강의를 참고하여 이진 검색 트리 알고리즘을 활용한 STL인 multiset을 활용하였다. 이 문제는 Key, value 대응 관계가 필요한건 아니니 map보다는 set이나 multiset(중복허용)이 적합하다. (최솟값 삭제 최댓값 삭제 모두 O(logN)) #include #include using namespace std; int main() { int t; cin >> t; while (t--) { int k; cin >> k; multiset ms; while(k--) { char c; cin >> c; if (c == 'D') { int num; cin >> num; if (ms.empty()) conti.. 2024. 1. 31. 백준 9375번: 패션왕 신해빈 [C++] https://www.acmicpc.net/problem/9375 해당 문제 같은경우는 hash_map 자체에 대한 이해도를 묻기보단 문제를 해석하는 센스와 수학적인 경우의수를 어떻게 쉽게 구할 수 있는지가 쟁점인 문제다. 입력으로 옷의 이름과 옷의 종류를 입력받는데 옷의 이름은 겹치지 않으므로 경우의 수를 구할 때 옷의 종류 만 생각하면 된다. 예를 들어서 옷의 종류가 양말, 모자, 상의 라고 가정하고 각각 다른 양말2개, 모자3개, 상의2개가 있다고 가정해보자 양말 안에서 선택할 수 있는 경우의수는 양말1 or 양말2 or 양말 선택 x 총3개 모자 안에서 선택할 수 있는 경우의수는 모자1 or 모자2 or 모자3 or 모자 선택 x 총4개 상의 안에서 선택할 수 있는 경우의수는 상의1 or 상의2o.. 2024. 1. 31. 백준 17219번: 비밀번호 찾기 [C++] https://www.acmicpc.net/problem/17219 #include #include using namespace std; int n,m; unordered_map um; int main() { cin >> n >> m; for(int i=0; i> add >> pass; um.insert(make_pair(add,pass)); } for(int i=0;i> add; if(um.find(add)!=um.end())cout N >> M; while (N--) { cin >> s >> p; umap[s] = p; } while (M--) { cin >> s; cout 2024. 1. 31. 이전 1 ··· 11 12 13 14 15 다음