Algorithm
-
Approach 이 문제를 단순히 반복문을 활용해서 처리하기 어려운 이유는 출력해야하는 자리수가 입력값에 영향을 받기 때문이다. 따라서 이 문제를 재귀를 통해 풀 수 있다는 것을 직관적으로 이해할 수 있다. 또한 증가하는 순서대로 출력해야한다는 조건 때문에 현재 입력하고 있는 값이 무엇인지 판단하는 것이 중요하다. 추가적으로 몇 번째 자리를 고려하고 있는 것인지 판단하는 것이 중요하게 된다. 따라서 재귀 함수의 입력값에 2가지 정보를 집어넣어주면 된다. 1. 현재 입력하고 있는 수 2. 현재 몇 번째 자리를 고려하고 있는지 추가적으로 이 문제는 출력값에 대한 배열을 따로 관리해주어야 한다. 그렇지 않으면 탑다운 방식으로 진행하는 상황에서 현재 숫자를 몇번이나 출력해야하는지를 알 수 없고, 재귀적으로 호출..
[백준 15652번] [Backtracking] N과 M(4)Approach 이 문제를 단순히 반복문을 활용해서 처리하기 어려운 이유는 출력해야하는 자리수가 입력값에 영향을 받기 때문이다. 따라서 이 문제를 재귀를 통해 풀 수 있다는 것을 직관적으로 이해할 수 있다. 또한 증가하는 순서대로 출력해야한다는 조건 때문에 현재 입력하고 있는 값이 무엇인지 판단하는 것이 중요하다. 추가적으로 몇 번째 자리를 고려하고 있는 것인지 판단하는 것이 중요하게 된다. 따라서 재귀 함수의 입력값에 2가지 정보를 집어넣어주면 된다. 1. 현재 입력하고 있는 수 2. 현재 몇 번째 자리를 고려하고 있는지 추가적으로 이 문제는 출력값에 대한 배열을 따로 관리해주어야 한다. 그렇지 않으면 탑다운 방식으로 진행하는 상황에서 현재 숫자를 몇번이나 출력해야하는지를 알 수 없고, 재귀적으로 호출..
2021.10.24 -
Approach s.p.s dp[x][y] : $\sum \limits_x \sum \limits_y v(x_i, y_i)$ for $1 \le x_i \le x , 1 \le y_i \le y$ (It is defined to be 0 if x or y are less than 1) Therefore dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1]. So, Summation (x1, y1) to (x2, y2) equal to dp[x2, y2] - dp[x2, y1 - 1] - dp[x1 - 1, y2] + dp[x1 - 1, y1 - 1] Code #include #define fastio ios_base::sync_with_stdio(0), ..
[백준 11660번] [구간 합] 구간 합 구하기 5Approach s.p.s dp[x][y] : $\sum \limits_x \sum \limits_y v(x_i, y_i)$ for $1 \le x_i \le x , 1 \le y_i \le y$ (It is defined to be 0 if x or y are less than 1) Therefore dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1]. So, Summation (x1, y1) to (x2, y2) equal to dp[x2, y2] - dp[x2, y1 - 1] - dp[x1 - 1, y2] + dp[x1 - 1, y1 - 1] Code #include #define fastio ios_base::sync_with_stdio(0), ..
2021.10.23 -
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..
[백준 1354번] [Unordered_map / DP] 무한 수열 2Approach 근본적으로 다음 문제와 접근 방법은 완전하게 동일하다. 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..
2021.10.23 -
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..
[백준 1351번] [Map / DP] 무한 수열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..
2021.10.23 -
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..
[백준 12757번] [Map / 이분 탐색] 전설의 JBNUApproach 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..
2021.10.23 -
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..
[백준 2910번] [Map] 빈도 정렬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..
2021.10.21 -
Approach 문자열을 그냥 바로 대소 비교하면 된다는 것만 캐치하면 쉽게 풀 수 있다. 문자열에서 따로 숫자를 파싱하고 하면 상당히 복잡하게 생각할 수 있으나 제시된 시각의 틀이 동일하기 때문에 바로 문자열 비교를 통해 요구한 시간안에 출석을 했는지 여부를 판단해주면 된다. 문제에서 가장 중요한 부분이 개강 총회가 끝나고 스트리밍이 끝날때까지 채팅을 남긴 대상 중, 개강 총회가 시작하기 전에 등어온 사람만 출석이 된다는 것이다. 전자 조건은 문자열 비교를 통해 쉽게 해결할 수 있으나, 해당 사람이 시작하기 전에 출석한 Set에 속한 사람을 판단하는 것을 Set 자료 구조를 활용해주면 쉽게 해결할 수 있다. 문제 자체는 되게 쉽다. (문자열 처리만 잘 한다면) Code #include #define f..
[백준 19583번] [Set] 싸이버개강총회Approach 문자열을 그냥 바로 대소 비교하면 된다는 것만 캐치하면 쉽게 풀 수 있다. 문자열에서 따로 숫자를 파싱하고 하면 상당히 복잡하게 생각할 수 있으나 제시된 시각의 틀이 동일하기 때문에 바로 문자열 비교를 통해 요구한 시간안에 출석을 했는지 여부를 판단해주면 된다. 문제에서 가장 중요한 부분이 개강 총회가 끝나고 스트리밍이 끝날때까지 채팅을 남긴 대상 중, 개강 총회가 시작하기 전에 등어온 사람만 출석이 된다는 것이다. 전자 조건은 문자열 비교를 통해 쉽게 해결할 수 있으나, 해당 사람이 시작하기 전에 출석한 Set에 속한 사람을 판단하는 것을 Set 자료 구조를 활용해주면 쉽게 해결할 수 있다. 문제 자체는 되게 쉽다. (문자열 처리만 잘 한다면) Code #include #define f..
2021.10.21 -
Approach 1번 조건 때문에 기존에 대기열에 존재하는지 여부가 굉장히 중요하다는 것을 알 수 있다. 왜냐하면 대기열 Set에 존재하는 상황에서 이후의 query가 들어오게 되면 나중의 순서로 재배정되기 떄문이다. 이 지점에서 기존의 대기열을 set으로 관리하여 존재하는지 여부를 관리하면 된다는 생각을 할 수 있다. 다만, 문제의 요구사항 중 하나는 대기열의 성공순서를 고려해야하는 상황이므로 어느 타이밍에 대기열에 등장했는지를 파악하는 것이 중요하다. 즉, 어느 타이밍에 대기열에 들어왔는지를 반영하기 위해서 Set보다는 Map 자료구조가 적합하다는 것을 알 수 있다. 그러나, key가 학번이므로 Map이 내림차순으로 정렬된다는 것을 활용항 수 없다. 따라서 Map을 2개 만듦으로서 이 문제를 해결해주..
[백준 13414번] [Map] 수강신청Approach 1번 조건 때문에 기존에 대기열에 존재하는지 여부가 굉장히 중요하다는 것을 알 수 있다. 왜냐하면 대기열 Set에 존재하는 상황에서 이후의 query가 들어오게 되면 나중의 순서로 재배정되기 떄문이다. 이 지점에서 기존의 대기열을 set으로 관리하여 존재하는지 여부를 관리하면 된다는 생각을 할 수 있다. 다만, 문제의 요구사항 중 하나는 대기열의 성공순서를 고려해야하는 상황이므로 어느 타이밍에 대기열에 등장했는지를 파악하는 것이 중요하다. 즉, 어느 타이밍에 대기열에 들어왔는지를 반영하기 위해서 Set보다는 Map 자료구조가 적합하다는 것을 알 수 있다. 그러나, key가 학번이므로 Map이 내림차순으로 정렬된다는 것을 활용항 수 없다. 따라서 Map을 2개 만듦으로서 이 문제를 해결해주..
2021.10.21