728x90 반응형 공부/Algorithm11 [Algorithm] 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘 (Kruskal algorithm) 다음과 같은 그래프가 있다고 해보자. 신장 트리는 그래프의 부분적인 트리라고 볼 수 있는데 그래프의 모든 노드를 갖고 있지만 에지의 경우 사이클이 생기지 않는 최소 부분만 가지고 있는 트리이다. 위의 그래프의 신장 트리는 여러 경우의 수가 존재한다. 많기 때문에 일부만 소개한다. 최소 신장 트리란 가중 그래프의 신장 트리 중에서 가장 가중치의 합이 작은 트리를 의미한다. 이렇나 최소 신장 트리를 구하는 방법인 Prim's algorithm과 Kruskal's algorithm에 대해서 공부해보려 한다. Prim algorithm 노드 하나를 선택한다. 선택된 노드들과 이어진 노드들 중 가장 가중치가 적은 노드를 고른다. 지금까지 선택된 노드들과 연결된 노드들 중 가장 가중치가 적은 노드를 고른다. 위 방.. 2022. 12. 17. [Algorithm] 점화식 점근적 접근 방식(반복 대치, 추정 후 증명) 점화식을 푸는 방법 중에서 반복 대치와 추정 후 증명에 대해 공부해보려 한다. 반복 대치 추정 후 증명 반복 대치 점화식을 잘게 쪼개어서 푸는 방법이다. (1) T(n) = T(n-1) + n 이라는 점화식이 있다고 하자. ( T(1) = 1 ) n에 n-1을 넣으면 T(n-1) = T(n-2) + n-1이 된다. 그럼 1번 점화식의 우변에 존재하는 T(n-1)에 그대로 대입하면 (2) T(n) = T(n-2)+ n + (n-1)이 된다. 원래 1번 점화식의 n에 n-2를 넣으면 T(n-2) = T(n-3) + n-2가 된다. 이를 2번 점화식의 우변에 존재하는 T(n-2)에 그대로 대입하면 (3) T(n) = T(n-3) + n +(n-1) + (n-2)가 된다. T(1)을 알고 있고 T(1)이 나올때.. 2022. 12. 5. [Algorithm] 없는 숫자 찾기 1부터 n까지의 수 집합이 존재한다. 이 중에서 하나의 수만 제외하고 n-1개의 수 집합 중에서 서로 다른 숫자 n-1개를 입력받는다. 여기서 존재하지 않는 숫자는 무엇인가? ex) n=5 이고 {1,2,4,5} 입력받았다면 답은 "3"이다. 입력 : 5 1 2 4 5 출력 : 3 크게 두 가지 방법이 존재한다. 배열 사용 첫 번째는 넉넉한 크기의 배열을 만든 다음에 모두 0을 저장한다. 그리고 수를 입력받으면 그 값을 인덱스로 사용하여 배열 해당 인덱스의 값을 1로 저장한다. 다 입력받고 나면 0이 들어있는 인덱스를 찾으면 끝이다. 위의 예시에서는 수를 전부 입력받으면 아래와 같은 모습이 된다. index 0 1 2 3 4 5 value 0 1 1 0 1 1 0번 인덱스의 값은 사용하지 않고 1번 인덱.. 2022. 12. 4. 이전 1 2 3 다음 728x90 반응형
