1. 최소 스패닝 트리(Minimum Spanning Tree) 외판원 문제 휴리스틱에서나 각종 그래프의 탐색 알고리즘, 최단 경로 알고리즘에서 경로를 찾는데에 사용했었다. 어떤 무향 그래프의 스패닝 트리(Spanning Tree)는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. 트리 형태라는 것은 선택된 간선들이 사이클을 이루지 않는다는 것을 의미하며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 것을 의미한다. 또한 그래프안에 여러 개의 스패닝 트리가 있다. 이런 스패닝 트리 중에서 가중치의 그래프의 스패닝 트리 중 가중치 합이 가장 작은 트리를 찾는 문제를 최소 스패닝 트리 문제(Minim..

1. 트라이 구현 문제를 해결 할 자료구조는 '트라이'다. 트라이는 문자열을 찾는데에 있어서 효율적인 자료구조이다. 주어진 단어들의 빈도에따라 추천하는 단어가 달라지므로 트라이를 구현할 때 각 노드마다 단어장에서 추천하는 단어의 인덱스변수와 추천하는 단어를 갱신하기 위한 우선순위 변수 두개가 필요하다. 단어장의 단어들을 트라이에 삽입할 때 '사전순'으로 추천하므로 일단 먼저 단어장을 정렬해야한다. 정렬한뒤 우선순위가 큰 것으로 업데이트 시켜주면 트라이 단어장은 완성된다. 2. 검색 구현 트라이에서 문자열 s 를 검색할때 s가 없으면 s의 사이즈를 반환하고, s가 해당 노드에서 추천하는 문자열과 같으면 탭을 눌러 이때까지 타자친 횟수에 1을 더해 값을 반환한다. 그 외의 경우는 문자열을 끝까지 친 경우이므..

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] 또한 참이 ..

1. 트라이 문자열은 두 변수를 비교하는데 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그러므로 이진 검색 트리에서 문자열을 찾는데에 O(mlgn) 의 시간이 걸릴 수 있다. 이와 같은 문제점을 해결하기 위해 고안된 문자열의 특화 자료 구조가 바로 트라이(trie) 이다. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로 검색 수행시 O(M)의 시간이 걸린다. - 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. - 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다. - 트라이의 루트는 항상 길이 0 인 문자열에 대응된다. - 깊이가 깊어질 수록 대응되는 문자열의 길이는 1 씩 증가한다. 트라이에서 중요한..

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..

1. 상호 배타적 집합 상호 배타적 집합을 표현할 때 유니온-파인드(union-find) 자료구조를 쓴다. 이 자료구조는 독특한 트리이다. 전체 집합을 공통 원소가 없는 여러 개의 부분 집합으로 쪼개어 나누어진 원소들(상호배타적인 부분 집합들) 에 대한 정보를 저장하고, 조작하는 자료구조가 유니온-파인드 자료구조이다. 이 자료구조의 핵심 연산은 다음과 같다. - 초기화: n 개의 원소가 있을 때 자기자신으로만 이루어진 집합들. - 합치기(union): 두 원소 a, b가 있을때 이들이 속한 두 집합을 하나로 합침 - 찾기(find): 어떤 원소 a가 주어질때 이 원소가 속한 집합을 찾는다. 2. 배열을 사용하여 상호 배타적 집합 표현하기 1차원 배열 하나를 이용하여 표현한다 belongsTo[i] = i..