코딩 테스트24 백준 23326번: 홍익 투어리스트 (C++) ttps://www.acmicpc.net/problem/23326 이 문제를 접근 할 때 map STL을 통해서 key값을 구역으로 두고 value값을 명소 여부인 0,1을 저장하려고 하였다. 하지만 이렇게 접근하면 실제로 시계 방향으로 이동하거나 시계 방향으로 최소 몇 칸 움직여야 하는지 출력하는 과정에서 map내부의 값을 다 돌아야 하므로 시간 복잡도가 최대 O(500,000*100,000)으로 초과하게된다. 그렇지만.. 풀이 방법이 떠오르지 않아서 아래와 같은 풀이로 시간 초과가 발생하였다. 아래 풀이는 참고하지 말자....! #include #include //#include using namespace std; map m; int main() { ios::sync_with_stdio(false).. 2024. 1. 31. 백준 21939번: 문제 추천 시스템 Version1 (C++) https://www.acmicpc.net/problem/21939 해당 문제의 핵심 접근 방법은 아래 두 가지와 같다. 해당 문제는 실제 번호에 해당하는 배열의 위치에 난이도를 넣어서 하나의 문제 번호만 존재하도록 관리한다. 위 배열을 참고해서 set 자료형을 배열로 선언하여 배열의 위치를 난이도로 하고 해당 배열에 문제 번호를 넣으면 문제 번호가 오름차순이 되기 때문에 문제에서 원하는 조건을 조금 더 쉽게 구현할 수 있다. 풀이는 아래와 같다. #include #include using namespace std; int probl[100'002]; set s[102]; int n,m; int main() { cin >> n; for(int i=0; i> p >> l ; probl[p]=l; s[l]... 2024. 1. 31. 백준 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. 이전 1 ··· 3 4 5 6 다음