느낌표 공장

Dijkstra 알고리즘이란 ? 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 음의 간선이 존재하지 않는, 간선의 값이 0 이상의 양수일 때 정상적으로 동작한다. 우선 순위 큐(heapq)를 사용한다. 동작 원리 단계 인접 리스트를 만든다. 최단 거리 테이블을 무한대의 값으로 초기화한다. 현재 노드에서 갈 수 있는 노드 다 가져온다. 현재 노드에서 다음 노드로 가는 간선 비용을 계산하여 가중치 테이블을 업데이트 한다. 3번과 4번을 반복한다. 문제 SWEA - 5251. 최소이동거리

Union-Find 란? Disjoint Set을 표현할 때 사용하는 알고리즘 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ? 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호 배타 집합을 표현하는 방법 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연결 리스트보다 효율적이다. 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 상호 배타 집합 연산 m..

에라토스테네스의 체(Eratosthenes' sieve ) 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법이다. 에라토스테네스의 체 알고리즘 1. 1부터 n까지의 자연수를 전부 나열한다. 2. 소수도, 합성수도 아닌 1을 지운다. 3. 남아 있는 자연수 중 가장 작은 수인 2 의 배수들을 모두 지운다. 4. 남아 있는 자연수 중 가장 작은 수인 3의 배수들을 모두 지운다. 5. 남아 있는 자연수 중 가장 작은 수는 소수다. 이 수의 배수들을 모두 지운다. 6. 남은 자연수 중 가장 작은 수가 n의 제곱근을 넘을 때까지 과정 5를 반복하면, 남아 있는 수가 모두 소수다. 코드로 표현하기(Python) number = [False, False] + [True] * n answer = ..