boj10 [segment tree] 11658번 구간 합 구하기 3 https://www.acmicpc.net/problem/11658 자료구조 2차원 segment tree 사용 언어 Python 시간 복잡도 $O(m(logn)^2)$ 풀이 포인트 segment tree안에 또 다른 segment tree (2차원)을 구현하여 시간 복잡도를 $(logn)^2$로 맞춰야한다는 점 2차원 segment tree 이 문제는 2차원 배열에서 수를 변경하는 쿼리가 발생할 때, 이를 효율적으로 처리하면서 주어진 2차원 배열에 대한 합도 구해야하는 문제이다. 우선 segment tree을 사용하지 않고 단순하게 문제를 푸는 경우를 생각해보자. 2차원 배열에서 수의 변경이 일어나는 쿼리를 처리하는데에는 $O(1)$의 시간이, 배열의 합을 구하는데에는 $O(N^2)$의 시간이 소요된다.. 2022. 5. 25. [segment tree] 1777번 순열복원 https://www.acmicpc.net/problem/1777 자료구조 Segment Tree 사용 언어 Python 시간 복잡도 $O(10^5 log (10^5))$ 풀이 포인트 BOJ 1849번 풀이와 거의 동일 query 함수의 분기 조건이 다르다는 것 Segment Tree 이 문제는 BOJ 1849번과 유사한 유형이다. 1849번은 수열 A[i]가 i 앞에 있는 수 들 중, i보다 큰 수들의 개수이다. 1777번은 수열 A[i]가 i 뒤에 있는 수 들 중, i보다 작은 수들의 개수이다. 두 문제의 차이는 1) A[i]의 정의가 앞, 또는 뒤에 있는 수들과 연관되어 있고 2) 이 수들과 작거나 큰 수들의 개수라는 것이다. 이 두 차이 때문에 두 문제는 아래와 같은 관점에서 풀이 방향성이 달라진.. 2022. 4. 24. [segment tree] 1849번 순열 https://www.acmicpc.net/problem/1849 자료구조 Segment Tree 사용 언어 Python 시간 복잡도 $O(10^5log(10^5))$ 풀이 포인트 BOJ 2243번 풀이와 거의 동일 두 가지 다른 점은 update 함수를 따로 구현하면 TIL이 발생하여 query 함수에서 이를 처리해줘야 한다는 점과 query 함수에서 분기하는 if 조건이 =을 포함하지 않는다는 점 단순 for문 풀이: TIL BOJ 2243번 풀이와 마찬가지로 왜 segment tree 자료구조를 사용해야하는지에 대해서 생각해보자. for문을 이용해볼 때, 시간 복잡도가 어떻게 나오는지 살펴본다. 입력에는 수열 A가 주어지고 A[i]는 그 수열에서 i 앞에 있는 수(i 왼쪽에 있는 수 들 중,)들 중.. 2022. 4. 9. [segment tree] 2243번 사탕상자 https://www.acmicpc.net/problem/2243 자료구조 Segment Tree 사용 언어 Python 시간 복잡도 $O(10^5 log(10^6))$ 풀이 포인트 트리의 i번째 노드 값이 1~i 사탕 맛의 개수의 합을 의미하도록 트리 설정 왼쪽 자식 노드의 값과 오른쪽 자식 노드의 값을 k와 비교하면서 왼쪽 자식 노드와 오른쪽 자식 노드 중 하나를 선택함 Segment Tree 이 문제에서 segment tree 자료구조를 사용해야하는 이유에 대해서 생각해보자. 굳이 자료구조를 사용해서 어렵게 풀지 않아도 될 상황이면, 머리 아프게 자료구조를 생각하지 않아도 되기 때문이다. 자료구조를 사용하지 않고 평범한 for문을 돌렸을 때, 시간 복잡도가 어떻게 나오는지 생각해보자. 수정이가 사탕.. 2022. 4. 8. [누적합] 2015번 수들의 합 4 https://www.acmicpc.net/problem/2015 알고리즘 누적합 (구현) 풀이 포인트 누적합의 개념을 알고 있어야 하고 코딩할수 있어야 한다. key-value 개념을 통해, 이전에 누적합이 i인 것의 개수를 저장한다. 누적합 누적합을 통해 주어진 수열의 부분합을 $O(n)$으로 구할 수 있다. 하지만 이 문제는 부분합이 $k$인 구간이 몇 개 있는지 구해야한다. 수열의 부분합을 구하고 ($O(n)$) $n$개 중 2개를 뽑아서 ($O(n^2))$ 그 부분합이 $k$인지 확인 ($O$(1))하면 된다. 즉, 시간 복잡도는 $O(n^2)$이며, 문제의 $n$의 범위로 보아, 시간 초과가 뜰 것이다. 따라서 이 문제는 시간 복잡도를 $O(n)$ 또는 $O(nlogn)$으로 줄여야 정답 판정.. 2022. 3. 9. [Greedy] 12931번 두 배 더하기 https://www.acmicpc.net/problem/15990 알고리즘 Greedy 풀이 포인트 BFS나 Brute Force 풀면 시간초과가 뜬다. greedy한 접근법을 통해 풀이 시간을 줄여야한다. BFS 딕셔너리 visited를 key 상태까지 도달하기 위한 최소 연산 횟수로 정의한다. 그리고 큐에서 현재 상태를 꺼낼 때마다, n개의 원소에 대해, i번째 원소에 1을 더한 a의 새로운 상태를 큐에 넣는다. 또한, 일괄적으로 2배를 한 a의 새로운 상태도 큐에 넣는다. 이 풀이의 시간 복잡도는 어떻게 될까? 최악의 경우, 길이가 50이면서 b의 모든 원소는 1000의 값을 가진다. 0에서 1000까지 1씩 더하면 1000번의 계산이 필요하므로, 대략 시간복잡도는 $O(50 \times 1000.. 2022. 2. 11. 이전 1 2 다음
