알고리즘 (7) 썸네일형 리스트형 에라토스테네스의 체 - seive of eratosthenes 📗 에라토스테네스의 체 알고리즘 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 구하는 방법으로 프로그래밍 알고리즘에서 소수를 구할 때도 적용하여 사용한다. ✔️ 에라토스테네스의 체 알고리즘의 원리 에라토스테네스의 체 알고리즘의 원리는 "소수의 배수인 수들을 전부 제외하면 소수만 남는다" 이다. 다시 말하면 소수의 배수들은 전부 소수가 아니기 때문에 소수의 배수들만 전부 제외하면 소수만을 구할 수 있는 것이다. 🚨CODE // 에라토스테네스의 체 boolean[] prime = new boolean[n]; public static void SeiveOfEratosthenes(){ // true = 소수x , false = 소수 prime[0] = prime[1] = true; for(int i = 2; i 다익스트라 알고리즘 - Dijkstra 📗 다익스트라 알고리즘 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. ✔ 왜 DP 문제? 다익스트라 알고리즘이 DP 문제인 이유는 "최단 거리는 여러 최단 거리로 이루어져있기 때문이다" 따라서 작은 문제가 큰 문제의 부분집합에 속해 있다고 볼 수 있다. 기본적으로 다익스트라는 "하나의 최단거리를 구할 때 그 이전까지 구했던 최단거리 정보를 그대로 사용한다"는 특징이 있다. 현재까지 알고있던 최단 경로를 계속해서 갱신해나간다. 📗 다익스트라 매커니즘 기본적으로 DP와 그리디 기법을 사용한다. 아래 두 단계를 반복해 임의의 노드에서 각 모든 노드까지 최단거리를 구한다. 1. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (.. 이분 탐색 - Binary Search 이분 탐색 이란 탐색 범위를 두 부분으로 분할 하면서 찾는 방식 처음부터 마지막까지 돌면서 탐색하는 것 보다 훨씬 빠른 장점이 있다. 시간의 복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN) 진행 순서 데이터를 정렬해야 한다. 시작 값인 start, 끝 값인 end로 중간 값인 mid 를 설정해야한다. mid값과 내가 구하고 싶은 값을 비교한다. 구할 값이 mid보다 높으면 start = mid + 1 구할 값이 mid보다 낮으면 end = mid-1 이 것을 start>=end가 될 때 까지 반복한다. Code public static int solution(int[] arr, int M) { // arr 배열에서 M을 탐색 Arrays.sort(arr); // 정렬 int start = 0;.. 그래프 탐색 - DFS & BFS # DFS (깊이 우선 탐색) 루트, 혹은 임의 노드까지 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 알고리즘이다. 자기자신을 호출하는 순환 알고리즘의 형태로써 스택이나 재귀함수로 구현한다. 그래프의 모든 경로를 방문해야할 경우에 사용에 적합하다, # DFS Code // i 정점부터 시작. public static void dfs(int i) { visit[i] = true; // 이미 방문한 노드인지 체크를 위한 배열, Boolean System.out.print(i + " "); // j는 dfs 배열의 새로운 브랜치를 뜻함. // map은 그래프를 나타내며 그래프 연결 정보를 // map[a][b] = map[b][a] = 1; 로 저장한다. (a노드와 b노드가 연결되어있다(1)는 정.. 삽입 정렬 - Insertion Sort 개념 선택 정렬과 유사하지만 좀 더 효율적인 알고리즘이다. 2번째 원소부터 시작하여 그 앞의 원소들과 비교하고 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자료를 삽입하여 정렬한다. 동작 과정 - 2번째 위치의 값을 temp에 저장 (첫번째 원소 앞에는 어떤 원소도 없기 때문) - temp와 이전 원소들을 비교하며 삽입해 나간다 - 위치 값을 저장하고 반복한다. Code void insertionSort(int[] arr) { for(int index = 1 ; index = 0) && (arr[prev] > temp) ) { arr[prev+1] .. 선택 정렬 - Selection Sort 개념 선택 정렬은 버블 정렬과 유사한 알고리즘으로 해당 순서에 원소를 넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘이다. 동작 과정 1. 주어진 배열 중에 최소값을 찾는다. 2. 찾은 최소 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Code void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { indexMin = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[indexMin]) { indexMin = j; } } // 4. swap(arr[indexM.. 버블 정렬 - Bubble Sort 버블 정렬의 개념 버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 크기를 비교하고 조건에 맞지 않으면 서로 자리를 교환하여 정렬하는 알고리즘이다. 거품 정렬의 동작 과정 n번째와 n+1번째 원소를 비교하여 조건에 맞지 않으면 교환한다. 1회전 할 때 가장 큰 원소가 제일 마지막 순서에 정렬되고 이 수는 2회전 정렬에서 제외된다. Code void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i arr[j]) { // swap(arr[j-1], arr[j]) temp = arr[j-1]; arr[j-1] .. 이전 1 다음
