일상
2012/01/20 19:29
요즘 열심히 Dovelete 문제를 풀고 있습니다만.....
꽤나 귀찮네요......
돈을 지르기 전에 3단계까지는 다 풀어야 하는데.....
역시....
귀찮아지니.....
후다닥 풀고 옥상 문제들 하나씩 올리겠습니다.^^
꽤나 귀찮네요......
돈을 지르기 전에 3단계까지는 다 풀어야 하는데.....
역시....
귀찮아지니.....
후다닥 풀고 옥상 문제들 하나씩 올리겠습니다.^^
'일상' 카테고리의 다른 글
| Dovelet 귀찮군요... (0) | 2012/01/20 |
|---|---|
| AVL트리 코딩이 정말 어렵다... (0) | 2012/01/17 |
| 정보올림피아드 겨울학교 다녀왔습니다. (0) | 2012/01/14 |
| 블로그 오픈 (0) | 2012/01/14 |
C/C++/Algorithm
2012/01/19 00:18
최소신장트리는 그래프에서 간선마다 가중치가 주어져 있고 그 간선들 중 몇 개를 선택하여 정점들을 연결했을 때 모든 정점이 하나의 트리에 속하며 간선의 가중치의 합이 최소가 되는 트리를 말합니다.
이렇게 말하고 보니 뭔가 복잡해 보입니다만....
예를 들면 이런 문제입니다.
네트워크를 구성하는데 n개의 도시가 있고, 어떤 두 도시를 연결하는데 필요한 비용은 각각 다르다고 한다. 또한 도시1, 도시2가 연결되어 있고 도시2, 도시3이 연결되어 있다면 도시1, 도시3은 서로 통신을 할 수 있다고 한다. 이럴 때 모든 도시들이 통신이 가능하도록하면서 비용이 최소가 되는 방법은?
헥...헥....
자꾸 말이 길어집니다만.....
이 문제의 해법으로는 Prim 알고리즘과 Kruskal 알고리즘이 있습니다.
둘 다 대표적인 욕심쟁이(Greedy) 기법이고요.
저는 제가 좋아하는 크루스칼에 대해 설명하도록 하겠습니다.(크루스칼의 시간복잡도는 O(E log E + E log V) 입니다.)
시간복잡도를 보니 복잡해 보이지만 단순합니다.
우선 간선을 비용 순으로 정렬합니다.
이후 비용이 가장 적게드는 간선부터 하나씩 추가하며 그래프에 cycle이 생기는지를 체크합니다.
어떤 간선을 추가했을 때 cycle이 생기지 않는다면 추가하고, 생긴다면 다음 간선으로 넘어갑니다.
이를 반복하여 트리를 구성하면 그것이 최소신장트리(MST)가 됩니다.
사실 이 풀이를 처음 봤을때는 과연 이 풀이로 구한 답이 정답인 것인지 의문도 생기기 마련입니다만... 증명된 사실이라고 합니다.
자세한 사항은 나중에 다시 한번 올리도록 하지요.
어찌됐건, 알고리즘은 단순합니다.
하지만 코딩을 하려고 하면 막막하죠...
cycle체크를 어떻게 해야할지 감도 안옵니다.
매번 bfs나 dfs를 돌리기에는 시간이 모자라겠죠?
이럴 때 사용하는게 Union & Find 입니다.
원리는 역시 단순합니다.
각 노드마다 자신이 속한 트리에서 자신의 부모 노드를 저장하는 것 입니다.
이렇게 한 후 어떤 간선을 더할 때 이 간선의 양 끝점에서 각각 부모를 따라 가다보면 각 트리의 root에 다다르겠죠?
이 root가 같은지만 체크해주시면 됩니다.
하지만, 이 역시 트리가 쏠린(Skewed) 경우에는 O(n)의 시간복잡도를 가지게 됩니다.
그래서 일반적으로 Union & Find는 Collapse_Find 와 Weighted_Union을 사용합니다.
Collapse_FInd는 어떤 노드에 대해 그 root를 찾아갈 때 그 경로에 있는 모든 노드의 부모를 그 트리의 root 노드로 바꾸어 주는것 입니다.
Weighted_Union은 트리 두 개를 합칠 때 작은 트리를 큰 트리 밑에 붙히는 것 입니다.
이를 이용하면 거의 완전 이진트리의 형태를 띈 트리가 될 것이고, 시간복잡도는 log scale로 줄어들게 됩니다.
역시 말로만 하기는 힘드네요..
소스를 참고해 주세요...
이렇게 말하고 보니 뭔가 복잡해 보입니다만....
예를 들면 이런 문제입니다.
네트워크를 구성하는데 n개의 도시가 있고, 어떤 두 도시를 연결하는데 필요한 비용은 각각 다르다고 한다. 또한 도시1, 도시2가 연결되어 있고 도시2, 도시3이 연결되어 있다면 도시1, 도시3은 서로 통신을 할 수 있다고 한다. 이럴 때 모든 도시들이 통신이 가능하도록하면서 비용이 최소가 되는 방법은?
헥...헥....
자꾸 말이 길어집니다만.....
이 문제의 해법으로는 Prim 알고리즘과 Kruskal 알고리즘이 있습니다.
둘 다 대표적인 욕심쟁이(Greedy) 기법이고요.
저는 제가 좋아하는 크루스칼에 대해 설명하도록 하겠습니다.(크루스칼의 시간복잡도는 O(E log E + E log V) 입니다.)
시간복잡도를 보니 복잡해 보이지만 단순합니다.
우선 간선을 비용 순으로 정렬합니다.
이후 비용이 가장 적게드는 간선부터 하나씩 추가하며 그래프에 cycle이 생기는지를 체크합니다.
어떤 간선을 추가했을 때 cycle이 생기지 않는다면 추가하고, 생긴다면 다음 간선으로 넘어갑니다.
이를 반복하여 트리를 구성하면 그것이 최소신장트리(MST)가 됩니다.
자세한 사항은 나중에 다시 한번 올리도록 하지요.
어찌됐건, 알고리즘은 단순합니다.
하지만 코딩을 하려고 하면 막막하죠...
cycle체크를 어떻게 해야할지 감도 안옵니다.
매번 bfs나 dfs를 돌리기에는 시간이 모자라겠죠?
이럴 때 사용하는게 Union & Find 입니다.
원리는 역시 단순합니다.
각 노드마다 자신이 속한 트리에서 자신의 부모 노드를 저장하는 것 입니다.
이렇게 한 후 어떤 간선을 더할 때 이 간선의 양 끝점에서 각각 부모를 따라 가다보면 각 트리의 root에 다다르겠죠?
이 root가 같은지만 체크해주시면 됩니다.
하지만, 이 역시 트리가 쏠린(Skewed) 경우에는 O(n)의 시간복잡도를 가지게 됩니다.
그래서 일반적으로 Union & Find는 Collapse_Find 와 Weighted_Union을 사용합니다.
Collapse_FInd는 어떤 노드에 대해 그 root를 찾아갈 때 그 경로에 있는 모든 노드의 부모를 그 트리의 root 노드로 바꾸어 주는것 입니다.
Weighted_Union은 트리 두 개를 합칠 때 작은 트리를 큰 트리 밑에 붙히는 것 입니다.
이를 이용하면 거의 완전 이진트리의 형태를 띈 트리가 될 것이고, 시간복잡도는 log scale로 줄어들게 됩니다.
역시 말로만 하기는 힘드네요..
소스를 참고해 주세요...
더보기
'C/C++ > Algorithm' 카테고리의 다른 글
| MST(최소신장트리) (0) | 2012/01/19 |
|---|---|
| AVL 트리 (0) | 2012/01/17 |
| 트리, 이진트리, 이진탐색트리 (0) | 2012/01/17 |
| STL(Standard Template Library) - Vector, Set, Map (0) | 2012/01/15 |
| 연결 리스트로 구현한 스택(Stack), 큐(Queue) (1) | 2012/01/15 |
| 연결 리스트(Linked List) (2) | 2012/01/15 |
C/C++/Algorithm
2012/01/17 23:37
네, 코딩했습니다.
AVL 트리는 Adellson-Velskii-Landis 의 약자입니다.
딱 보기만 해도 이 세 사람이 만든 트리겠죠?
AVL 트리는 가장 초기에 고안된 균형이진트리인데요, 그만큼 방법은 단순합니다.(다른 균형이진트리에 비하면요...)
어떤 노드에 대해 그 노드의 왼쪽 부트리와 오른쪽 부트리의 높이를 보고, 이 부트리들의 높이가 2 이상 차이가 날 경우 트리를 회전해서 이 차이를 없앱니다.
참 쉽죠?(......)
그림으로 설명할게요..
이 그림에서 왼쪽고 같은 경우 제일 위에 있는 노드에서 높이가 다름을 알아챌 수 있겠죠?
이럴 때 오른쪽 그림과 같이 만들게 되면 높이는 전체 높이는 1 감소하게 됩니다.
하지만 아래와 같은 경우도 있겠죠.
이 외에 2가지 경우가 더 있겠지만 위의 두가지의 좌우대칭 형태이므로 설명은 생략하겠습니다.
이러한 간단한 아이디어로 만들어진 AVL트리는 (비교적) 구현이 쉽다는 장점이 있지만, 다른 균형이진트리에 비해 느리다는 단점이 있습니다.
삽입이 한번 될 때 마다 이렇게 계속 회전을 시켜주니, 확실히 연산횟수가 많아지겠지요.
이를 해결한 트리가 Red-Black 트리와 2-3-4 트리 입니다.
사실상 Red-Black 트리와 2-3-4 트리는 isomorphic한 관계입니다만...(서로 전환 가능)
구현은 2-3-4트리가 쉽다고 합니다.(저는 아직 해보지 않아서..)
이에 대한 설명은 나중에 올리겠고요
밑에는 제가 한줄 한줄 직접 짠 AVL 트리 소스입니다.
(Successor와 Predecessor 함수가 원래 다르게 해야했던거 같기도 한데요...)
혹시 안되는 부분, 잘못된 부분 있으면 댓글 남겨주세요.
AVL 트리는 Adellson-Velskii-Landis 의 약자입니다.
딱 보기만 해도 이 세 사람이 만든 트리겠죠?
AVL 트리는 가장 초기에 고안된 균형이진트리인데요, 그만큼 방법은 단순합니다.(다른 균형이진트리에 비하면요...)
어떤 노드에 대해 그 노드의 왼쪽 부트리와 오른쪽 부트리의 높이를 보고, 이 부트리들의 높이가 2 이상 차이가 날 경우 트리를 회전해서 이 차이를 없앱니다.
참 쉽죠?(......)
그림으로 설명할게요..
이 그림에서 왼쪽고 같은 경우 제일 위에 있는 노드에서 높이가 다름을 알아챌 수 있겠죠?
이럴 때 오른쪽 그림과 같이 만들게 되면 높이는 전체 높이는 1 감소하게 됩니다.
하지만 아래와 같은 경우도 있겠죠.
이 외에 2가지 경우가 더 있겠지만 위의 두가지의 좌우대칭 형태이므로 설명은 생략하겠습니다.
이러한 간단한 아이디어로 만들어진 AVL트리는 (비교적) 구현이 쉽다는 장점이 있지만, 다른 균형이진트리에 비해 느리다는 단점이 있습니다.
삽입이 한번 될 때 마다 이렇게 계속 회전을 시켜주니, 확실히 연산횟수가 많아지겠지요.
이를 해결한 트리가 Red-Black 트리와 2-3-4 트리 입니다.
사실상 Red-Black 트리와 2-3-4 트리는 isomorphic한 관계입니다만...(서로 전환 가능)
구현은 2-3-4트리가 쉽다고 합니다.(저는 아직 해보지 않아서..)
이에 대한 설명은 나중에 올리겠고요
밑에는 제가 한줄 한줄 직접 짠 AVL 트리 소스입니다.
(Successor와 Predecessor 함수가 원래 다르게 해야했던거 같기도 한데요...)
혹시 안되는 부분, 잘못된 부분 있으면 댓글 남겨주세요.
더보기
'C/C++ > Algorithm' 카테고리의 다른 글
| MST(최소신장트리) (0) | 2012/01/19 |
|---|---|
| AVL 트리 (0) | 2012/01/17 |
| 트리, 이진트리, 이진탐색트리 (0) | 2012/01/17 |
| STL(Standard Template Library) - Vector, Set, Map (0) | 2012/01/15 |
| 연결 리스트로 구현한 스택(Stack), 큐(Queue) (1) | 2012/01/15 |
| 연결 리스트(Linked List) (2) | 2012/01/15 |