알고리즘 문제해결전략(100)
-
[그래프] Graph 1: 그래프의 표현과 정의
알고리즘 문제해결전략2 그래프파트 1. 그래프 그래프는 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조이다. 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 트리와는 다르게 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있다. 2. 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 3. 그래프의 종류 간선에 추가적인 속성을 부여 존재할 수 있는 간선이나 정점의 형태에 제약 가능 여러 속성을 함께 가지는 그..
2021.02.11 -
[트리] 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 -
[트리] Tree 9: 트라이, 아호-코라식 알고리즘
1. 트라이 문자열은 두 변수를 비교하는데 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그러므로 이진 검색 트리에서 문자열을 찾는데에 O(mlgn) 의 시간이 걸릴 수 있다. 이와 같은 문제점을 해결하기 위해 고안된 문자열의 특화 자료 구조가 바로 트라이(trie) 이다. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로 검색 수행시 O(M)의 시간이 걸린다. - 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. - 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다. - 트라이의 루트는 항상 길이 0 인 문자열에 대응된다. - 깊이가 깊어질 수록 대응되는 문자열의 길이는 1 씩 증가한다. 트라이에서 중요한..
2021.02.09 -
[트리] [시도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 -
[트리] Tree 8: Disjoint Set 상호 배타적 집합, 유니온-파인드
1. 상호 배타적 집합 상호 배타적 집합을 표현할 때 유니온-파인드(union-find) 자료구조를 쓴다. 이 자료구조는 독특한 트리이다. 전체 집합을 공통 원소가 없는 여러 개의 부분 집합으로 쪼개어 나누어진 원소들(상호배타적인 부분 집합들) 에 대한 정보를 저장하고, 조작하는 자료구조가 유니온-파인드 자료구조이다. 이 자료구조의 핵심 연산은 다음과 같다. - 초기화: n 개의 원소가 있을 때 자기자신으로만 이루어진 집합들. - 합치기(union): 두 원소 a, b가 있을때 이들이 속한 두 집합을 하나로 합침 - 찾기(find): 어떤 원소 a가 주어질때 이 원소가 속한 집합을 찾는다. 2. 배열을 사용하여 상호 배타적 집합 표현하기 1차원 배열 하나를 이용하여 표현한다 belongsTo[i] = i..
2021.02.08