알고스팟(70)
-
[트리] SOLONG 안녕히, 그리고 물고기는 고마웠어요!
1. 트라이 구현 문제를 해결 할 자료구조는 '트라이'다. 트라이는 문자열을 찾는데에 있어서 효율적인 자료구조이다. 주어진 단어들의 빈도에따라 추천하는 단어가 달라지므로 트라이를 구현할 때 각 노드마다 단어장에서 추천하는 단어의 인덱스변수와 추천하는 단어를 갱신하기 위한 우선순위 변수 두개가 필요하다. 단어장의 단어들을 트라이에 삽입할 때 '사전순'으로 추천하므로 일단 먼저 단어장을 정렬해야한다. 정렬한뒤 우선순위가 큰 것으로 업데이트 시켜주면 트라이 단어장은 완성된다. 2. 검색 구현 트라이에서 문자열 s 를 검색할때 s가 없으면 s의 사이즈를 반환하고, s가 해당 노드에서 추천하는 문자열과 같으면 탭을 눌러 이때까지 타자친 횟수에 1을 더해 값을 반환한다. 그 외의 경우는 문자열을 끝까지 친 경우이므..
2021.02.10 -
[트리] EDITORWARS 에디터 전쟁
1. 문제 이 문제는 여러 집합들을 세 집합으로 나누는 문제이다 - 아무것도 속해있지 않은 집합 - b집합과 대치되는 a집합 - a집합과 대치되는 b집합 m개의 댓글에서 두명의 정보가 주어진다. 두명의 정보는 ack -> 같은 편, dis -> 다른편 으로 주어지고 이를 통해 a와 b 집합으로 나누는 것이다. 그 후 a와 b의 모순이 생기면 모순이 생기는 댓글의 인덱스를 모순이 생기지 않으면 아무것도 속해있지 않은 집합의 크기와 a,b중 더 큰 집합의 크기를 더한 값을 반환하면 문제를 해결할 수 있다. 2. 상호 배타적 집합: 유니온-파인드 자료구조 ack a b 가 주어지면 a 와 b를 합친다. 이때 a와 b가 대치되는 사람 r[a] r[b] 가 있다고 하자 그러면 ack r[a] r[b] 또한 참이 ..
2021.02.10 -
[트리] [시도x] MEASURETIME
1. 펜윅트리를 이용한 풀이 처음에 이 문제를 봤을때 펜윅트리를 어떻게 써야할 지 감을 못잡았다. 책에서는 수열의 입력값으로 이루어진 트리를 만들고 해당 입력값이 오게되면 그것을 포함하는 구간을 전부 +1을 해줘서 루트에 현재 수열의 길이를 저장하게 되고 입력값 까지의 부분합을 구하게 되면 현재 수열중에서 입력값보다 작은 것들의 개수를 알 수 있다. 이를 통해 자신보다 큰 원소의 개수를 알 수 있고, 앞으로 몇칸 이동 시켜야하는지 파악할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..
2021.02.08 -
[트리] [시도x] FAMILYTREE 족보 탐험
FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 www.algospot.com 이 문제의 핵심은 '전위 탐색' 이다. 전위 탐색은 트리를 재구성하고, 부분 구간을 생성할 수 있게 해준다. 1. 생각. 이 문제를 풀기 위해서는 성벽 문제와 마찬가지로 두 사람의 두 노드간의 길이를 구하는 문제이므로 최소 공통 조상을 찾아야 할 거 같다. 최소 공통 조상을 찾으려면 일단 트리를 구현해야한다. 트리를 구현한뒤 depth를 구해 각 번호마다 따로 저장해놓는다. 그 후 2 * lgn 만에 두 노드를 찾은후 거슬..
2021.02.08 -
[트리] MORDOR 등산로
1. 문제 표지판번호가 0 ~ n-1 인 표지판이 있는 등산로가 있다고한다. 표지판에는 해발고도가 적혀있고 배열 h에 번호마다 해발고도가 저장되어있다. a번 표지판에서 b번 표지판까지의 등산로의 난이도를 a~b의 최대 해발고도와 최소 해발고도의 차이라고 한다. a, b가 주어졌을때 난이도를 구하는 함수를 만드라는게 이 문제의 의도이다. 2. 구간 트리 초기화 pair 객체를 가지는 구간 트리를 만들어서 각 구간마다 최대 최소인 원소를 저장해야한다. 이는 바텀업 방식으로 재귀를 이용하여 리프부터 루트까지 각 노드를 채워야한다. 기저조건으로 구간의 길이가 1 일때(리프) 구간은 최대와 최소가 같은 pair을 반환한다. 재귀를 이용하여 왼쪽, 오른쪽 서브트리를 루트로 합친다. 합칠때 최대는 최대끼리 최소는 최..
2021.02.07 -
[트리] RUNNINGMEDIAN 변화하는 중간값
1. 균형잡힌 이진 검색트리를 이용한 풀이 트립 을 구현하여 수열이 추가될때마다 이진 검색트리를 유지 시키고, k번째 수열을 찾는 kth함수를 구현하여 중간값을 찾는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103..
2021.02.07