반응형 Algorithm/algorithm5 소수 구하기 - 에라토스테네스의 체 (Python & JavaScript) 우리는 알고리즘 공부를 하다보면 소수에 대한 문제를 가끔 보게 된다. 그러나 이는 구현하는 방식에 따라 시간 복잡도가 달라지는데 우리는 이번 시간에 에라토스테네스의 체를 이용해서 소수를 탐색할 수 있다. 이 방식의 시간 복잡도는 선형 시간과 비슷한 시간으로 O(NloglogN)이다. 에라토스테네스의 체 알고리즘 이는 다수의 자연수에 대해서 소수 여부를 판별할 때 사용되는 대표적 알고리즘이다. 동작 방법은 가장 작은 소수(i)를 찾고 이에 배수가 되는 값들을 제외한다. 제외한 뒤에는 소수 다음 중 가장 작은 소수를 찾아 배수가 되는 값을 제거하는 방법을 반복하면 된다. 동작과정 2부터 N까지의 모든 자연수를 담고 있는 하나의 배열에 생성한다. 배열에서 남은 수 중에서(True인 수) 아직 처리하지 않은 가.. 2022. 5. 2. 그래프 - 깊이우선탐색 / 너비우선탐색 ( DFS / BFS ) 자료 구조 - 그래프 노드와 간선으로 표현되며, 노드를 정점이라고도 한다. 그래프는 하나의 노드(정점)에서 여러 갈래의 간선을 통해 다른 노드 방문하는 탐색을 주로 이용된다. 이때 두 노드가 간선으로 연결되어 있다라고 할 수 있는데 다른 표현으로는 '두 노드가 인접하다'라고도 표현한다. 프로그래밍에서의 그래프 구조 그래프는 크게 2가지의 형태로 표현된다. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 인접 행렬 2차원 배열에 각 노드가 연결된 형태로 기록하는 방식으로, 연결되지 않은 노드끼리는 무한한 값으로 초기화 한다. 인접 리스트 메모리 측면에서 보면 인접 행렬 방식은 모든 관계를 저장하기 때문에 메모리를 낭비하게 된다. .. 2021. 10. 18. 신장 트리 (Spanning Tree) & 크루스칼(Kruskal) 신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이러한 성질을 가진 그래프는 다양한 문제에 활용되는데, 대표적인 유형이 여러 노드를 연결하는 간선이 비용을 가질 때, 그 비용의 합이 최소가 되는 신장트리를 찾아야 하는 경우이다. 예를 들어보면, 아래와 같은 그래프가 존재 한다고 한다. 간선의 비용의 합을 최소로 하기는 신장트리가 되기 위해서는 아래와 같이 연결을 해야 할 것이다. 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트릴르 찾는 알고리즘을 이제 '최소 신장 트리 알고리즘'이라고 하자. 이러한 최소 신장 트리 문제를 해결하기 위한 대표적인 알고리즘을 다음을 통해 배워보자. 크루스칼 알고리즘 (Kruskal Algorithm) 이는 가장 적은.. 2021. 9. 13. 위상 정렬 (Topology Sort) 위상 정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘, 또는 방향 그래프의 모든 노드를 방향성에 어긋나지 않고 순서대로 나열하는 것으로 정의할 수 있다. 위상 정렬을 2단계로 설명할 수 있는데 다음과 같다. 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 이때 진입차수란? 이는 한 노드로 방향을 가르키는 간선의 개수를 의미한다. 파이썬 소스 2021. 9. 13. 이전 1 2 다음 반응형
