Approach 기본적인 접근 방법은 다음 문제와 비슷하다. https://viyoung.tistory.com/286 [백준 15663번] [Backtracking / Map] N과 M (9) Approach 같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다. 이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처 viyoung.tistory.com 다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자신의 index 이상부터만 고려해준다는 점에서 차이점이 존재한다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) us..

Approach 같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다. 이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처음부터 고려하는 방식으로 해결할 수 있으나, 이 문제의 경우에는 중복 때문에 단순히 그렇게 처리를 할 수 없다. 따라서 얼마까지 중복해서 사용할 수 있는지를 핸들링 하기 위해서 map 자료구조를 활용하였다. capacity가 있으면 해당 index를 사용할 수 있는 느낌으로 해결해주면 된다. 추가적으로 같은 숫자때문에 중복되는 수열이 발생할 수 있는데, 이는 unique함수를 활용해서 해결해주면 된다. 상당히 어렵다.. Code #include #define fastio ios_base::sync_wit..

Approach 근본적으로 다음 문제와 접근 방법은 완전하게 동일하다. https://viyoung.tistory.com/277 [백준 1351번] [Map / DP] 무한 수열 Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식 viyoung.tistory.com 다만, 데이터의 양이 매우 많은 상황이고 순서가 크게 중요하지 않은 상황이므로 해시를 활용한 맵인 Unordered_map을 활용하여 시간을 줄여주면 통과하는 문제이다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.t..

Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다. 1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다. 2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; t..

Approach key와 value가 등장하는 상황이므로 Map을 활용하면 된다는 것은 쉽게 추측할 수 있다. 이 문제에서 가장 독특한 지점은 가장 가까운 key값에 매핑한다는 것인데, 이 부분은 Map 안에 존재하는 lower_bound나 upper_bound method를 활용해서 구해주면 된다. 다만, 해당 method를 통해 구해준 iterator가 begin()이나 end()와 같은 경우만 예외처리를 잘 해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, k; map s; int find_key(int t){ if(s.lower_b..

Approach 일단, 빈도 순으로 정렬하는 것이므로 Map 자료 구조를 활용해서 몇 번 출현했는지를 체크해주면 된다. 독특한 지점은 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 점이다. 이 부분은 먼저 나오는 번호를 따로 저장해두면 된다. 개인적으로는 문제에서 C를 준 이유가 있다고 판단하여서 vector를 활용해 정렬하였다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool compare(pair &a, pair &b){ if(a.first.first == b.first.first) return a.first.second < b.first.se..

Approach 1번 조건 때문에 기존에 대기열에 존재하는지 여부가 굉장히 중요하다는 것을 알 수 있다. 왜냐하면 대기열 Set에 존재하는 상황에서 이후의 query가 들어오게 되면 나중의 순서로 재배정되기 떄문이다. 이 지점에서 기존의 대기열을 set으로 관리하여 존재하는지 여부를 관리하면 된다는 생각을 할 수 있다. 다만, 문제의 요구사항 중 하나는 대기열의 성공순서를 고려해야하는 상황이므로 어느 타이밍에 대기열에 등장했는지를 파악하는 것이 중요하다. 즉, 어느 타이밍에 대기열에 들어왔는지를 반영하기 위해서 Set보다는 Map 자료구조가 적합하다는 것을 알 수 있다. 그러나, key가 학번이므로 Map이 내림차순으로 정렬된다는 것을 활용항 수 없다. 따라서 Map을 2개 만듦으로서 이 문제를 해결해주..

Approach 전체에서 몇 퍼센트 해당하는지를 파악하는 것이므로, 쿼리에 대한 모든 정보를 받고 처리해야 한다. 이 부분에서 오프라인 쿼리 문제임을 인식해주면 된다. 추가적으로 Map container를 활용해주면 해당 set안에 몇 개 들어있는 상황인지를 쉽게 파악할 수 있다. + 어디까지 들어올지 모르는 상황이므로 while(getline(cin, t))를 사용하는 점을 유의깊게 보도록 하자. + cin.precision의 경우 정수부와 소수부의 자리수 개수의 합을 지정해주는 것이다. 소수점 이후의 자리부분을 설정하려면 cout