소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수 입니다. 예를 들면 2, 3, 5, 7 등 다른 수로 나누어 질 수 없는 수입니다. 에라토스테네스의 체 소수를 구하는 대표적인 판별법은 에라토스테네스의 체가 있습니다. 에라토스테네스의 체를 이용해 소수를 구하는 방법은 다음과 같습니다. 구하고자하는 소수의 범위 만큼 1차원 배열 생성 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움 다음 숫자 중 지워지지 않은 숫자로 이동 배열의 끝에 도달할 때까지 2~3번 반복 에라토스테네스의 체의 경우 이중 for문을 이용하지만 배수를 삭제하는 연산으로 인해 실제 구현에서 for문이 생략되는 경우가 빈번하게 발생합니다. 그렇기 때문에 O..
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리기도 합니다. 그 이유는 미래는 생각하지 않고 현재 주어진 선택지에서 가장 최선의 선택을 하는 알고리즘 이기 때문입니다. 그리디 알고리즘의 수행 과정은 다음과 같습니다. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못하면 1로 돌아가 반복
이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는 방법입니다. 시간 복잡도는 O(log n)입니다. 탐색 과정 현재 데이터에서 중앙값 선택 중앙값 > 탐색값 일 때 중앙 값을 기준으로 왼쪽데이터셋 선택 중앙값 < 탐색값 일 때 중앙 값을 기준으로 오른쪽데이터셋 선택 탐색값을 찾을 때까지 1 ~ 3번 과정 반복 구현 아래의 문제를 예시로 들어 이진탐색을 구현하였습니다. 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에..
깊이 우선 탐색(DFS : Depth First Search) 너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다. FIFO(First In First Out) 방식으로 큐를 이용하여 구현하며 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. 장단점 장점 시작 노드부터 목표 노드 까지의 최단 경로를 보장 단점 큐를 이용해 다음에 탐색 할 노드를 저장하기 때문에 노드의 수가 많을 수로 많은 저장 공간을 필요로함 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기 때문에 비효율적 구현 방법 BFS를 사용하기 위해서는 먼저 그래프를..
그래프의 연결관계를 나타내는 방식은 인접 행렬과 인접 리스트로 두 가지의 방법이 있습니다. 인접 행렬(Adjacency Matrix) 인접 행렬은 이차원 배열을 이용하여 그래프를 표현하는 방식입니다. 위 의 그림과 같이 2 차원 배열의 형태로 두 노드의 번호를 좌표로 이용하여 1이면 연결이 되었음을 0이면 연결 되지 않았음을 뜻하게 됩니다. 무방향 그래프의 경우 양방향으로 연결 되기 때문에 아래와 같이 두 좌표에 입력을 합니다. graph[i][j] = 1 graph[j][i] = 1 방향 그래프의 경우 한쪽에서만 연결 되기 때문에 한 좌표에만 입력을 합니다. graph[i][j] = 1 장단점 장점 구현이 쉬움 노드의 연결성을 확인할 때 시간 복잡도는 O(1)로 빠름 단점 간선의 수와 상관 없이 항상 ..
깊이 우선 탐색(DFS : Depth First Search) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나입니다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다. 구현은 재귀 함수, 스택을 이용하며 시간 복잡도는 O(V + E) V = 노드 수, E = 엣지 수 입니다. 장단점 장점 현 경로상의 노드들만 기억하면 되기때문에 저장 공간의 수요가 적음 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음 단점 해가 없는 경로에 깊이 빠질 가능성이 있음 얻어진 해가 최단 경로가 된다는 보장이 없음 구현 방법 DFS를 사용하기 위해서는 먼저 그래프를 구현 해야합니다. 그래프를 ..
기수 정렬은 값을 비교하지 않는 특이한 정렬입니다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다. 기수 정렬의 시간 복잡도는 O(kn)이고, k는 데이터의 자릿수를 의미합니다. 정렬 과정 입력한 수열은 몇 개의 키로 분류됩니다. 3자리이하 수라고 한다면, 1의 자리, 10의 자리, 100의 자리로 나누어 분류됩니다. 170, 45, 75, 90, 2, 24, 802, 66 1의 자리만 보고 정렬을 수행 ↓ 170, 90, 2, 802, 24, 45, 75, 66 10의 자리만 보고 정렬 수행 ↓ 2, 802, 24, 45, 66, 170, 75, 90 100의 자리만 보고 정렬 수행 ↓ 2, 24, 45, 66, 75, 90, 170, 802 위와 같은 과정을 통해 정렬이 ..
병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 입니다. 시간 복잡도는 O(nlogn)입니다. 정렬 과정 최초에 N개의 그룹으로 나눕니다. 그림을 예로 들면 8개로 나누게 되고 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬합니다. (1), (2), (3), (4), (5), (6), (7), (8) ↓ (5, 6), (1, 3), (7, 8), (2, 4) ↓ (1, 3, 5, 6), (2, 4 ,7, 8) ↓ (1, 2, 3, 4, 5, 6, 7, 8) 소스 코드 public void mergeSort(int A[], int low, int high, int B[]){ // 1. base condition if(low >= high) return; // ..
퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘 입니다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간복잠도는 O(nlogn)이며 최악의 경우 O(n²)이 됩니다. 정렬 과정 데이터를 분할하는 pivot을 설정(그림의 경우 가장 오른쪽 끝을 pivot로 설정) pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동 end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 ..
삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방법입니다. 시간 복잡도는 O(n²)이지만 구현하기 쉽습니다. 정렬 과정 현재 index에 있는 데이터 값 선택 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색 삽인 위치부터 index에 있는 위치 까지 shift 연산 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 선택할 데이터가 없을 때까지 반복 소스 코드 void insertionSort(int[] arr) { for(int index = 1 ; index = 0) && ( arr[aux]..
