땡글이LAB

해당 문제는 투포인터 문제의 간단한 응용버전이다. 처음에는 투포인터로 안풀어도 될 거 같아서 그냥 구현해서 풀었지만 당연히 시간초과가 나왔었다. 생각보다 반복문 돌려야하는 게 많았다... 아래 코드는 시간초과나온 틀린 코드다. (그냥 set 에 원소들을 넣어주고 사이즈가 내가 원했던 사이즈가 맞으면 정답 ans 카운트를 하나 증가시키는 식으로 구현) #include using namespace std; typedef long long ll; int N; int arr[100005]; set s; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 0; i > arr[i]; } int ans..

처음 문제를 접했을 때는 DP라는 생각이 들지 않고, 그냥 단순한 구현문제인 줄 알고 구현했더니 시간초과가 나왔다. 내가 짠 코드의 시간복잡도는 O(N * M) 이었다. (아래의 코드는 시간초과된 틀린 코드이다.) #include using namespace std; typedef long long ll; int N, M; int board[2005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 1; i > board[i]; } cin >> M; int S, E; while (M--) { cin >> S >> E; if (S == E) { cout > E; cout

이 2295번 문제에 가장 간단하게 접근하는 방법은 arr[i] + arr[j] + arr[k] = arr[m] 방식으로 시간복잡도가 O(N^4)인 방법이 있을테고, arr[m]을 찾는 방식을 이분탐색으로 바꿔주면, O(N^3 * logN) 이 될 것이다. 이 문제가 정답율이 낮은 이유도 이렇게 다들 생각을 많이 하고 제출했더니 메모리 초과가 나거나 시간초과가 난 것 같다. O(N^3 * logN) 코드는 다음과 같다. 이렇게 풀면 틀립니다 #include using namespace std; typedef long long ll; int N; int arr[1005]; vector three; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> ..

매개 변수 탐색 문제(Parametric Search)는 그냥 이분 탐색 문제와는 접근방법이 조금 다르다. 기본적인 이분탐색 문제의 경우에는 배열 요소들을 정렬해준 뒤, 위치를 찾아내기만 하면 된다. 하지만 2805번 문제와 같이 매개 변수 탐색 문제 같은 경우에는 조건을 만족하는 최소/최댓값을 구하는 문제, 즉 최적화 문제를 결정 문제로 변환해 이분탐색으로 문제를 해결해야 한다. 이걸 모르면 이분 탐색을 사용해서 풀라고해도 모를 수 있다. 나 또한 그랬다... :) 그럼 2805번 문제를 살펴보자. 문제에선 상근이가 M 미터 이상의 나무를 가져가야 하는데, M미터 이상의 나무를 가져가면서 절단기 높이의 최대 길이를 구해야한다. 이제 매개 변수 탐색 문제라고 했으니, '절단기 높이'와 '상근이가 취할 수..

처음에 조합 리스트를 어떻게 구해야할지 몰라서 굉장히 막막했었는데, C++에서 제공하는 next_permutation 함수를 이용하면 순열 및 조합을 구할 수 있다는 걸 알고 내가 한 번 짜봤다. 이 문제에서의 핵심은 문자열로부터 조합을 구할 수 있느냐 없느냐의 차이인 것 같다. 조합만 구할 줄 안다면, 그 이후의 문제는 너무 쉽다. 이것 저것 찾아보니 조합을 구하는 방법 두 가지를 알게 됐다. 첫 번째 방법은 위에서 말한 대로 next_permutation 함수를 이용해서 구하는 것이고, 두 번째는 DFS(또는 재귀)로 구하는 방법이다. #1 next_permutation() 활용 풀이 우선 내가 푼 코드는 next_permutation 함수를 사용해서 푼 방식이니 내 코드부터 설명을 해보겠다. #in..

세그먼트 트리(Segment Tree)는 제목에 적힌 것처럼 이진 트리에서 응용된 트리이다. 세그먼트 트리는 여러 개의 데이터가 순서를 가지고 존재할 때, 특정 범위의 합을 구할 때 사용된다. 물론 데이터의 변경이 없다면 특정 범위의 합을 구하는 문제에서 동적 프로그래밍(DP)를 사용해도 괜찮다. 만약 주어진 데이터의 숫자가 지속적으로 변경되고 여러 번 특정 구간에 대해 합을 구해야 한다면 동적 프로그래밍(DP)의 사용이 적절할까?? 아니다. 데이터가 여러 번 바뀌고 구간 합을 여러 번 구해야 하는 상황이라면 동적 프로그래밍(DP)는 데이터가 바뀔 때마다 O(N) 시간복잡도를 가질 것이고, 데이터가 변경되는 횟수가 M이라면 총 O(NM)의 시간복잡도를 가진다. 그렇다면 세그먼트 트리의 경우는 어떨까? 세..