Segment tree
-
Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초과하게 된다. 이때 등장하는 방법이 Euler tour technique이다. 해당 방법을 통해 트리를 Array로 필 수 있게 된다. 기존에 진행하던 DFS 과정을 잘 생각해보면, 일종의 재귀적으로 계속해서 해당 노드를 기준으로 밑으로 내려가게 된다. 즉, DFS에서 방문순서를 기준으로 index를 부여할 수 있게 된다. 이를 바탕으로 다음과 같은 식을 잡을 수 있다. dfs_in[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 시작 index dfs_out[i] : 노드 i를 포함한 i의 subt..
[백준 14287번] [세그먼트 트리 / 오일러 투어 테크닉] 회사 문화 3Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초과하게 된다. 이때 등장하는 방법이 Euler tour technique이다. 해당 방법을 통해 트리를 Array로 필 수 있게 된다. 기존에 진행하던 DFS 과정을 잘 생각해보면, 일종의 재귀적으로 계속해서 해당 노드를 기준으로 밑으로 내려가게 된다. 즉, DFS에서 방문순서를 기준으로 index를 부여할 수 있게 된다. 이를 바탕으로 다음과 같은 식을 잡을 수 있다. dfs_in[i] : 노드 i를 포함한 i의 subtree를 방문하는 Euler trail의 시작 index dfs_out[i] : 노드 i를 포함한 i의 subt..
2021.07.29 -
Approach 특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다. 이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다. 따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다. 단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다. 처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만..
[백준 15816번] [세그먼트 트리] 퀘스트 중인 모험가Approach 특정한 구간에 대한 정보를 묻고 있는 상황이므로 세그먼트 트리 자료구조를 활용할 수 있지 않을까라고 판단해주면 된다. 이때, 퀘스트가 총 21억개로 상당히 많은 것과 달리 처리한 퀘스트는 최대 2백만정도 밖에 존재하지 않는다. 따라서 처리한 퀘스트를 기준으로 좌표압축을 해주고, 특정 쿼리에 대한 해결한 퀘스트의 개수를 구해주는 방식으로 이 문제를 해결할 수 있다. 단, 이런 방식으로 처리하려면 입력값으로 들어오는 좌표들을 미리 한번에 받아두어야하므로 미리 정보를 다 저장해둔다. 처음에 접근한 방식은 해결한 퀘스트 번호만을 가지고 좌표 압축을 진행하였다. 다만 이 방식의 문제점은, request에서 퀘스트 번호가 주어졌을 때 무엇을 포함하고 포함하지 않을 것인지에 대한 기준이 모호하다. 만..
2021.07.29 -
백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..
[백준 15561번] [세그먼트 트리 / 분할 정복] 구간 합 최대? 2백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..
2021.02.02 -
이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다. 이 지점에서 Segment Tree 기법을 생각했어야 한다. Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다. 다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데 이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다. 또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다. 요약하자면 다..
[백준 16993번] [세그먼트 트리 / 분할 정복] 연속합과 쿼리이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다. 이 지점에서 Segment Tree 기법을 생각했어야 한다. Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다. 다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데 이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다. 또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다. 요약하자면 다..
2021.02.01 -
문제 상황을 이해하려고 끄적거리다보면 숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다. 즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다. 이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다. 1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지 2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지 이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다. 또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와..
[백준 1849번] [세그먼트 트리] 순열문제 상황을 이해하려고 끄적거리다보면 숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다. 즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다. 이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다. 1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지 2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지 이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다. 또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와..
2021.01.31 -
전형적인 Segment tree 문제이다. 관련한 개녕은 www.crocus.co.kr/648 에 잘 나와있으므로 참고하도록 하자. Init, sum, update함수를 적당히 잘 구현해서 풀어주면 되는 문제이다. 중간중간에 숫자를 수정하고 구간 합을 구하는 지점에서 세그먼트 트리 문제임을 눈치챘어야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); typedef long long ll; using namespace std; ll arr[1000000]; ll tree[1000000 * 4]; ll init(ll start, ll end, ll node){ if(start == end) return tree..
[백준 2042번] [세그먼트 트리] 구간 합 구하기전형적인 Segment tree 문제이다. 관련한 개녕은 www.crocus.co.kr/648 에 잘 나와있으므로 참고하도록 하자. Init, sum, update함수를 적당히 잘 구현해서 풀어주면 되는 문제이다. 중간중간에 숫자를 수정하고 구간 합을 구하는 지점에서 세그먼트 트리 문제임을 눈치챘어야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); typedef long long ll; using namespace std; ll arr[1000000]; ll tree[1000000 * 4]; ll init(ll start, ll end, ll node){ if(start == end) return tree..
2021.01.31