본문 바로가기

DEVELOP/알고리즘

 (53)
9. BST - 트립 직접 구현하기 이진 트리는 각 노드가 왼쪽, 오른쪽 최대 두개의 자식 노드만을 가질 수 있는 트리이다. 따라서 이진 트리는 자식 노드들의 배열 대신 두개의 포인터 left, right를 담는 객체로 구현된다. 이진 검색 트리는 각 노드의 왼쪽 서브트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이 있고, 오른쪽 서브트리에는 해당 노드의 원소보다 큰 원소를 가진 노드들이 있는 트리이다. n개의 노드가 있을 때, 원하는 원소를 찾기 위해서 매번 후보의 수를 절반씩 줄여갈 수 있으므로 O(logN) 시간에 해결할 수 있을 것이다. 이진 검색 트리는 집합에 원소를 삽입하거나 삭제할 때 진가를 드러낸다. 원하는 원소를 찾거나, 최대, 최소 원소를 구하는 등의 구현은 정렬된 배열일 때도 쉽게 할 수 있다. 그러나 정렬된 배..
8. 트리의 구현과 순회 - 트리에서 가장 긴 경로 찾기 트리에서 최장 경로 문제를 푸는 열쇠는 최장 경로의 양 끝의 노드가 항상 루트 노드 혹은 리프 노드여야 한다는 것이다. 루트 노드도 아니고 리프 노드도 아닌 내부 노드가 최장 경로의 끝점이라고 가정해보자. 이 때 내부노드는 부모로 가는 간선과 자식으로 가는 간선을 무조건 가지고 있기 때문에 두개 이상의 간선이 연결되어 있다. 따라서 최소한 하나의 간선이 경로에 사용되지 않은 채 남아있기 때문에 해당 경로는 최장 경로라고 할 수 없다. 즉, 최장 경로의 길이는 다음 둘 중 더 큰 값이 된다. 1. 가장 긴 root - leaf 노드 경로의 길이 2. 가장 긴 leaf - leaf 노드 경로의 길이 이 때 1번은 사실상 전체 트리의 높이이기 때문에, 2번만 찾으면 된다. 잎 - 잎 경로들은 항상 어떤 노드까..
8. 트리의 구현과 순회 - 트리 순회 순서 변경(traversal) 문제 이 문제는 재귀 호출을 이용하면 간단하게 구현할 수 있다. 전위 순회 순서에서 가장 먼저 오는 값은 트리의 루트값이라는 것을 알 수 있다. 그러면 이 값을 중위 순회에서 찾아 왼쪽 서브트리와 오른쪽 서브트리를 구분할 수 있게 된다. 위와 같이 왼쪽 서브트리의 크기를 구하여 전위 순회 배열과 중위 순회 배열을 잘라 재귀호출 할 수 있다. // 트리 순회 순서 변경 문제를 해결하는 재귀 호출 코드 #include #include #include using namespace std; // v 벡터를 a인덱스부터 b-1인덱스까지 자른 결과 리턴 vector slice(const vector& v, int a, int b) { return vector(v.begin() + a, v.begin() + b); } v..
8. 트리의 구현과 순회 선형으로 표현하기 어려운 형태의 자료 중 하나로 계층 구조가 있다. 자료 간에 상하위 관계나 포함 관계가 존재하는 경우 계층 구조가 생긴다. 계층 구조를 갖는 자료들을 표현하기 위한 자료 구조가 바로 tree 이다. 트리는 탐색형 자료 구조로도 유용하게 쓰인다. 특정한 조건을 지키도록 구성된 트리들을 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 할 수 있기 때문이다. 트리의 구성 요소 트리는 자료가 저장된 노드(node)들이 간선(edge)으로 서로 연결되어 있는 자료구조를 말한다. 노드 간에는 상/하위 관계가 있으며, 두 노드가 연결되었을 때 한 노드는 좀 더 상위, 다른 노드는 좀 더 하위에 있어야한다. 두 연결된 노드 중 상위노드를 부모(parent), 하위 노드를 자식(chi..
7. 최단 경로 알고리즘 - 선거 공약(promises) 문제 문제를 해결하기 위해 각 도시를 정점으로 하고 고속도로를 간선으로 하는 그래프를 모델링 할 수 있다.현재 존재하는 고속도로들에 대해서 플로이드 알고리즘을 실행하여 각 도시간 최단 경로를 구한다.그 후 새로 건설할 고속도로를 첫번째부터 두 도시를 잇는 경로의 최단 시간을 비교하게 된다.새로 건설할 고속도로가 최단 시간이 더 짧으면 해당 고속도로를 건설하고, 현재 고속도로의 최단 시간이 더 짧거나 같으면 건설하지 않는다.이 때 새로 건설한 고속도로에 대해서 그래프를 업데이트 해주어야 한다.그런데 고속도로를 새로 건설할 때마다 기존 플로이드 알고리즘을 한번 더 수행해 주는 것은 매우 비효율적이다. 새로 건설한 고속도로가 연결하는 도시가 a와 b라고 하자.그러면 두 도시간 최단 경로에 변경이 생기는 경우는 a나..
7. 최단 경로 알고리즘 - 음주 운전 단속(drunken) 문제 문제를 해결하기 위해 각 장소를 정점으로 하고 도로를 간선으로 하는 그래프를 모델링할 수 있다.그런데 중간 지점에서 음주 단속을 할 수 있기 때문에 최단 경로의 경유점이 중요하다.따라서 플로이드 알고리즘을 약간 변형하여 문제를 해결하도록 한다.플로이드는 경유점 집합을 늘려가며 모든 쌍에 대해 최단 경로를 구한다.이 때 경유점 집합에 정점을 어떤 순서로 추가하든지 관계는 없다.따라서 각 정점을 단속에 걸리는 시간 별로 정렬한 뒤, 시간이 적게 걸리는 정점부터 경유점 집합에 추가하면서 최단 경로를 갱신해나간다.최단 거리를 계산하면서, 해당 최단 거리에 최대 지연 시간을 더한 값을 계산하여 이전의 어떤 경로보다 짧은지 비교하여 저장한다.해당 경로에서 가장 단속이 오래걸리는 지점은 현재 경유하게 된 지점이 되기..
7. 최단 경로 알고리즘 - Floyd 알고리즘 플로이드 알고리즘은 다익스트라나 벨만-포드 알고리즘과 다르게 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구하는 모든 쌍 최단거리 알고리즘이다. 플로이드 알고리즘의 작동 원리를 이해하기 위해 정점 u, v에 대해 둘 사이를 잇는 최단 경로를 구한다고 해보자.이 때 이 경로에는 다른 정점들이 포함될 수도 있고, 포함되지 않을수도 있다.정점 집합 S에 포함된 정점만을 경유점으로 사용해 u에서 v까지 가는 최단 경로의 길이를 Cs(u, v) 라고 하자.이 때 집합의 모든 정점들을 경유점으로 사용해야 하는 것은 아니다.그러면 집합 S에 포함된 정점 하나를 x라고 하면, u에서 v까지의 최단 경로는 x를 포함할수도, 포함하지 않을 수도 있다.이 때 최단 경로는 다음 두가지 형태를 가진다. 1. 경로가 정점 x를 ..
7. 최단 경로 알고리즘 - 시간여행(timetrip) 문제 문제를 해결하기 위해 각 은하계를 정점으로 하고, 은하계 사이를 이동하는 웜홀들을 간선으로 하는 그래프를 모델링할 수 있다.지구는 0번 은하계, 안드로메다는 1번 은하계이므로 문제는 0번 정점에서 1번 정점까지 가는 최단 경로를 구하는 문제가 된다. 가장 빠른 시간뿐만 아니라 가장 늦은 시간도 구해야 하기 때문에 최장 경로의 길이도 구해야 하는데,이는 lower[] 배열을 하나 더 만들어서 하한선에서 완화 과정을 통해 값을 증가시켜나가는 방법도 있고,각 웜홀의 이동시간에 대해 모두 부호를 반대로 바꿔서 최단 경로 알고리즘을 한번 더 수행하는 방법도 있다. 그런데 경우에 따라 안드로메다로 도달할 수 없는 경우도 있고, 무한한 과거나 미래로 갈 수 있는 경우가 있다.무한한 과거나 미래로 가는 경우는 음수 사..

티스토리툴바