반응형 Segment tree18 [코드트리] 코드트리 등산 게임 (삼성 SW 역량테스트 2024 하반기 오후 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고 - BOJ 10828 : 스택- BOJ 12015 : 가장 긴 증가하는 부분 수열 2 https://www.codetree.ai/training-field/frequent-problems/problems/%08codetree-mountain-climbing-games 이 문제는 산의 높이가 주어질 때,등산가는 현재 위치보다 오른쪽에 위치한 산 중, 현재 산 보다 높은 산으로만 움직일 수 있다.케이블 카가 없다면, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing.. 2024. 12. 20. BOJ 12015 : 가장 긴 증가하는 부분 수열 2 알고리즘 문제 전체 링크삼성 B형 전체 링크 https://www.acmicpc.net/problem/12015 참고- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 수열 A의 크기는 1,000,000이고 들어 있는 값은 1부터 1,000,000이므로 세그먼트 트리를 이용해서 문제를 풀 수 있다. 예제의 {10, 20, 10, 30, 20, 50}에서가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이 4를 찾아보자. 수열에 값이 하나가 추가될 때마다, LIS의 길이를 세그먼트 트리를 이용해서 갱신하면 문제를 풀 수 있다.값 x가 추가되고, 구간 [1, x - 1]의 LIS의 길이가 y라면 구간 [1, x]의 LIS의 길이는 y + 1이 된다.. 2024. 12. 20. [코드트리] 코드트리 DB (삼성 SW 역량테스트 2024 하반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고 - 산타의 선물 공장- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)- 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree)- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 https://www.codetree.ai/training-field/frequent-problems/problems/codetree-db 문제를 요약하면 다음과 같다. init- 테이블을 초기화 한다.테이블은 unord.. 2024. 12. 20. BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 삼성 C형 전체 링크 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5397 참고 - BAPC 2010 I번 문제 - BOJ 5397 : 키로거 (스택) - 링크드 리스트 Linked List - 링크드 리스트 삭제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 - 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 - BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 위 문제를 스택을 이용한 방법 대신, 세그먼트 트리와 링크드 리스트로 풀어보자. 다만 이 방법으로는 이 문제의 tc를 시간 내에 통과할 수 없다. 키로거는 커서를 한 칸씩 이동.. 2023. 8. 25. BOJ 12899 : 데이터 구조 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/12899 참고 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 - BOJ 1168 : 요세푸스 문제 2 BOJ 1168 : 요세푸스 문제 2와 마찬가지로 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. 찾은 값은 update를 이용해 다시 삭제하면 된다. #include int N; int tree[4194304]; int start, leafSize; void update(int index, int diff) { index += start; while (index > 1) { tree[ind.. 2023. 3. 4. BOJ 1168 : 요세푸스 문제 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1168 참고 - BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 큐(Queue)를 사용하는 BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제보다 N이 매우 큰 경우다. 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. N이 100,000이고, 100,000보다 2배 이상 큰 2의 배수는 262,144이다. 따라서 tree의 사이즈는 다음과 같다. int tree[262144]; 이제 N보다 큰 2의 배수를 구해보자.. 2023. 3. 4. BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List 이전 글에서는 tree의 크기를 넉넉하게 잡았다. 구간의 길이가 100만이기 때문에 실제로는 2배 정도의 크기만 있으면 된다. 여기서는 필요한 만큼만 적절히 잡아서 다이나믹하게 트리를 만들어보자. 배열의 index를 이용하는 방법 원래 update 코드는 아래와 같다. void update(int left, int right, int node, int index, ll value) { if (inde.. 2023. 2. 8. BOJ 6549 : 히스토그램에서 가장 큰 직사각형 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6549 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 문제의 예시대로 사각형을 그려보자. 전체 구간 [1 ~ 7]을 포함하는 가장 큰 직사각형의 넓이는 7이다. 예를 들어 구간 [6 ~ 7]만 포함하는 가장 큰 직사각형의 넓이는 6이 된다. 이 넓이는 어떻게 구할 수 있을까? 구간 [a ~ b]에서 가장 작은 높이와 (b - a + 1)을 곱하면 된다. 그리고 구간 [a ~ b]에서 가장 작은 높이의 index가 c라면 구간 [a ~ c - .. 2023. 1. 20. BOJ 3653 : 영화 수집 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/3653 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) 6개의 영화가 있고 최대 M = 10번 영화를 본다고 가정하자. 그러면 세그먼트 트리를 아래와 같이 만들 수 있다. 마지막 leaf에서 10개는 비워두고, 6개의 영화를 순서대로 노드에 넣고 값을 1씩 증가시킨다. 영화를 10번 보기 때문에 앞의 노드를 그만큼 비워둔다. 영화가 순서대로 1, 2, 3, 4, 5, 6이 쌓여있는 상태다. 예를 들어 3번 영화를 본다고 가정하면, 3번 앞에는 1번과 2번 영화가 있기 때문에 .. 2023. 1. 20. 이전 1 2 다음 반응형