할머니의 콤퓨타 도전기

이분 탐색 탐색 범위를 두 부분으로 분할해서 찾는 방식. 따라서 전부를 탐색하는 것에 비해 속도가 빠름 시간 복잡도 O(log(n)) 1. 이미 정렬이 되어있어야 이분 탐색 가능 2. left, right로 mid 값을 결정 3. mid 값과 구하고자 하는 값 비교 4. 비교할 때 mid 값보다 구하고자 하는 값이 크면 left를 mid + 1로, 낮으면 right를 mid-1로 만듦 5. left > right 가 될 때 까지 위의 과정을 반복해 구하고자 하는 값 찾음

다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 크고 어려운 문제가 있으면, 그것을 먼제 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것 Memoization이 사용됨 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환하기만 하면 됨 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 -> 이 두 가정이 모두 성립하면 다이나믹 프로그래밍 사용 가능

합집합 찾기(Union-Find), 서로소 집합(Disjoint-Set) 알고리즘 여러 개의 노드 중 두 개의 노드를 선택해서, 이 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 1. 우선 모든 노드가 연결되지 않고 자신만을 집합의 원소를 갖고있도록 만듭니다. 따라서 모든 값이 자기 자신을 가리키도록 합니다. 첫 번째 행은 노드 번호, 두 번째 행은 부모 노드 번호입니다. 즉, 각 노드 번호가 어떤 부모에 포함되어 있는지를 의미합니다. 1 2 3 4 5 1 2 3 4 5 2. 1번 노드와 2번 노드가 연결되어있다고 가정합시다. 1 2 3 4 5 1 1 3 4 5 부모를 합칠 때에는 더 작은 값 쪽으로 합치는 것(Union)이 일반적입니다. 따라서 1번 노드와 2번 노드가 연결되면 2번 노드의..

크루스칼 알고리즘(Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. (최소비용신장트리를 만들기 위한 대표적인 알고리즘) 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자할 때 실제로 적용합니다. ​ 모든 간선정보를 오름차순으로 정렬한 뒤에 (간선 거리(비용)이 짧은(적은) 순서대로 정렬) 비용이 적은 간선부터 차근차근 그래프에 포함시키면 됩니다. 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에는 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 포함시키지 않는다 ​ 사이클이 발생하는 지의 여부는 Union-Find 알고리즘을 적용하면 됩니다. #include #include #include..

Bellman-Ford Algorithm 시작점으로 부터 다른 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘과 유사합니다. 그러나 벨만 포드 알고리즘은 간선 cost가 음수인 경우에도 사용할 수가 있습니다. (O(VE)의 시간으로 다익스트라 알고리즘보다는 시간이 오래걸림) 위와 같은 그래프에서 0번 정점으로 부터 2번 정점까지의 최단거리를 구하고자 합니다. 최단거리는 0->1->2 를 거쳐서 12+(-9)=3이 됩니다. 그러나 다익스트라 알고리즘에서는 dist[1]=12 > dist[2]=7 이기 때문에 2번 정점을 방문하게 되고 따라서 음의 간선이 존재하는 그래프에서는 최단경로를 제대로 구할 수 없게 됩니다. 벨만 포드 알고리즘은 2중 for문을 통해 가능한 모든 경우를 다 체크합니다. 최단경..