1223

에라토스테네스의 체 소수를 판별하는 알고리즘 단일 숫자의 소수 여부 확인 어떤 수의 소수 여부를 확인할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 에라토스테네스의 체 원리 배열을 생성하고 초기화 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다. 2부터 시작하여 남아있는 수를 모두 출력 public class PrimeNumber2 { static int max = 999; static boolean[] prime; public static void main(String[] args) { prime = new boolean[max + 1]; primeNum(); for..

BFS(Breadth First Search) 너비 우선 탐색 가까운 노드부터 탐색 동작 방식 큐 자료구조 이용하여, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성 먼저 들어온 것이 먼저 나가며, 가까운 노드부터 탐색하게 된다. 탐색 시작 노드를 큐에 삽입하고 방문 처리 큐에서 노드를 꺼낸다 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 위의 두 단계를 반복한다. 예시 방문 처리된 노드는 밝은 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표시한다. 시작 노드(1)를 방문 처리하면서 큐에 넣는다. 큐에서 요소 하나(1)를 꺼내고, 인접한 노드들(2, 3, 4)을 작은 것부터 큐에 넣고 방문 처리를 한다. 큐에서 요소 하나(2)를 꺼내고, 인접한 노..

DFS(Depth First Search) 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 동작 방식 스택 자료구조 이용 탐색 시작 노드를 처음으로 스택에 삽입한다. 방문처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 위의 과정을 반복한다. 예시 노드 1을 시작 노드로 하여 DFS를 이용해 탐색한다. (검정색으로 칠한 노드는 방문처리가 된 노드이고, 파란 노드는 현재 위치한 노드이다.) 시작 노드(1)를 스택에 넣는다. 인접한 노드 중(2, 3, 4)에서 스택에 없는 가장 작은 숫자의 노드(2)로 이동하고 스택에 넣는다. 인접한 노드(2)로 이동했으면, 그 노드..

리스트로 구하는 법 1. ArrayList 선언 public class GraphList { private ArrayList listGraph; } ) 위의 그림을 보면 각 정점들은 배열로되어있고, 그 정점이 리스트의 헤드가 되어있다. list하나의 각 요소마다 다른 list형태가 나타나게 만들어야 하는 것을 알 수 있다. 그래서 ArrayList의 제네릭 타입이 ArrayList인 것이다. 이렇게 만들어 주고 간단하게 ArrayList의 메서드를 사용해서 노드를 연결시켜주면 된다. 2. 정점들을 생성 public void addVertex(int x){ listGraph.add(new ArrayList(x)); } 리스트의 헤드가 될 정점들을 생성한다. 3. 정점 x와 정점 y를 연결시켜주는 메서드 단..

인접 행렬로 구하는 법 인접행렬 그래프의 연결 관계를 이차원 배열로 나타내는 방식 1. 인접 행렬 선언 public class graphArray{ private int[][] array; } 위 코드의 array 그래프 정점(vertex)들을 이어주는 간선(edge)들을 0과 1로 표시한다. 0: 연결 x 1:연결 o 2. 행렬의 크기 설정 public class GraphArray { private int[][] array; //인접 행렬 선언 public GraphArray(int size) { array = new int[size + 1][size + 1]; //인접 행렬의 크기 } } 생성자로 정사각 행렬을 크기와 함께 초기화한다. 행렬의 인덱스는 0부터 시작하므로 size에 1을 더해준다. 3..