Algorithm/Theory19 에라토스테네스의 체(백준 1713번 : 골드바흐 파티션) 오늘은 소수 판별법 중 하나인 에라토스테네스의 체에 대한 리뷰 오늘도 당연히 그림 같은 건 생략한다. 왜냐하면 귀찮기 때문 에라토스테네스의 체는 소수 판별법 중에 하나인데, 특정 숫자 범위 이내의 숫자들 중 소수들을 찾을 때 사용 가능하다. 찾는 법은 아주 간단한데, 예를 들어 100 이하의 소수를 찾으려고 할 때 2의 배수, 3의 배수, 5의 배수, 7의 배수를 제외하면 남은 숫자가 소수이다. 이렇게 걸러내는 방식이 마치 체로 걸러내는 것과 비슷하여 이름이 붙여졌다. (코드는 아래 주석과 함께) 아래는 에라토스테네스의 체를 사용하는 문제이다. 나는 에라토스테네스의 체를 모르는 채로 아래 문제를 풀었는데, 2의 배수 3의 배수까지 걸러내는 것에는 다가갔는데 그 이후로는 실패하여 검색해서 해결했다. 원래 .. 2023. 12. 9. 유클리드 호제법 오늘은 백준 알고리즘 1735번을 풀면서 접하게 된 유클리드 호제법에 대하여 정리해보겠습니다. 유클리드 호제법(Euclidean Algorithm)은 두 개의 자연수의 최대공약수를 구하는 알고리즘이다. 유클리드 호제법의 핵심은 두개의 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수와 b와 r의 최대공약수는 같다는 것이다. 이 핵심에 따라 b를 r로 나눈 나머지를 r`라고 한다면 다시 r를 r`로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나눈 수가 최대공약수가 되는 것이다. 유클리드 호제법을 사용하여 최대공약수를 구하는 과정을 설명하면 좋겠으나 귀찮기도 하고 핵심만 안다면 코드로 구현하는 것은 어렵지 않다고 생각한다. 반복문으로 a, b 자리에.. 2023. 12. 3. [Java] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort)은 안정 정렬 중 하나이며, 분할 정복 알고리즘을 사용한 정렬 방법입니다. 분할 정복(divide and conquer)은 하나의 문제를 두 개의 문제로 분리하고 각각 해결한 다음 결과를 모아서 문제를 해결하는 방법입니다. 병합 정렬(Merge Sort)이란? 병합 정렬은 분할 정복 알고리즘에 따라서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합하여 정렬된 하나의 리스트로 만드는 방법입니다. 병합 정렬은 아래와 같은 순서로 진행됩니다. 분할(Divide) : 입력된 리스트를 두개의 리스트로 분할한다. 정복(Conquer) : 분할된 리스트를 정렬한다. 분할된 리스트의 크기가 작지 않다면 재귀 호출을 이용하여 다시 분할 정복합니다. 결합.. 2022. 7. 6. [Java] Counting Sort(카운팅 정렬) Counting Sort는 일반적인 정렬 알고리즘과 달리 데이터를 서로 비교하지 않고, 데이터의 값을 카운팅 하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n)인데, 빠른 정렬 알고리즘으로 알려져 있는 Quick Sort, Merge Sort, Heap Sort 등의 시간 복잡도가 O(nlogn)라는 것을 생각하면 Counting Sort의 속도가 엄청나다는 것을 알 수 있습니다. 그럼 왜 Counting Sort는 사용하지 않는 것일까요? Counting Sort는 정렬 할 배열의 최댓값의 +1만큼 새로운 카운팅 배열을 생성해줘야 하는데, 수의 범위가 크다면 메모리를 많이 낭비하기 때문에 자주 사용하지 않습니다. 과정 1. 먼저 정렬할 배열의 데이터의 최댓값의 +1 크기의 카운팅 배열을 생성합니다. .. 2022. 5. 7. [자바] 셸 정렬(Shell Sort) 셸 정렬 셸 정렬은 단순 삽입 정렬을 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다. 단순 삽입 정렬은 아래의 포스팅을 참고해주시길 바랍니다. 2022.01.22 - [Algorithm/Theory] - [자바] 단순 선택 정렬과 단순 삽입 정렬 [자바] 단순 선택 정렬과 단순 삽입 정렬 단순 선택 정렬 단순 선택 정렬이란 배열중 가장 작은 요소를 선택해 알맞은 위치로 옮겨서 정렬하는 단순한 알고리즘입니다. 아래의 배열에서 가장 작은 요소인 1을 선택해 첫 번째 위치인 6과 hyunipad.tistory.com 아래는 단순 삽입 정렬을 장점과 단점입니다. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 빠릅니다.(장점) 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아집니다.(단점) .. 2022. 1. 27. [자바] 단순 선택 정렬과 단순 삽입 정렬 단순 선택 정렬 단순 선택 정렬이란 배열중 가장 작은 요소를 선택해 알맞은 위치로 옮겨서 정렬하는 단순한 알고리즘입니다. 아래의 배열에서 가장 작은 요소인 1을 선택해 첫 번째 위치인 6과 교환합니다. 그다음 작은 요소인 4를 선택해 두 번째 위치는 5와 교환합니다. 아직 정렬하지 않은 요소중에서 가장 작은 값을 선택합니다. 선택한 가장 작은 값과 아직 정렬하지 않은 부분의 첫 번째 위치의 요소와 교환합니다. 단순 선택 정렬은 위와 같은 작업을 N-1회 반복하여 정렬하는 알고리즘입니다. 단순 선택 정렬을 코드로 구현해보겠습니다. package selectionsort; public class selectionSort { static void swap(int[] a, int idx1, int idx2) {.. 2022. 1. 22. [자바] 버블 정렬(Bubble Sort) 버블정렬 버블 정렬이란 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 단순한 알고리즘입니다. 예시를 들어 버블 정렬에 대해 알아보겠습니다. 먼저 끝에 있는 두 요소 9와 8부터 대소를 비교합니다. 이때 오름차순이라면 왼쪽의 값이 작아야 하고 내림차순이라면 왼쪽의 값이 더 커야 합니다. 오름차순으로 정렬을 할 것이기 때문에 9와 8을 교환하면 아래와 같은 배열이 됩니다. 그다음 1와 8을 비교합니다. 1은 8보다 작기 때문에 교환할 필요가 없습니다. 따라서 그 다음 요소를 비교하교 이렇게 첫 번째 요소까지 작업을 계속한다면 아래와 같은 순서로 정렬이 되게 됩니다. 요소의 개수가 N개인 배열에서는 N-1회를 비교하게 되고 끝에서 끝까지 교환하는 작업을 패스(pass)라고 합니다. 그리고 패스가 한번.. 2022. 1. 21. [자바] 큐(Queue) - 선입선출(FIFO : First In First Out)의 자료구조 큐 Queue(대기줄) 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 하지만, 스택과 다른 점은 선입선출(FIFO : First In First Out)의 자료구조로 되어있습니다. Queue(대기줄)이라고 불리는 이유는 선입선출의 구조가 은행에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열과 비슷하기 때문입니다. 큐는 선형 큐 또는 원형 큐를 구현할 수 있습니다. 선형 큐는 데이터가 디큐 되었을 때 데이터를 하나씩 앞쪽으로 옮겨야 하는 구조이고 원형큐는 첫 번째 요소와 마지막 요소를 식별하기 위한 변수 프런트(front)와 리어(rear)를 사용하여 데이터를 앞쪽으로 옮기지 않고 사용하는 자료구조입니다. 이번 포스팅에선 원형 큐를 구현해보도록 하겠습니다. Que.. 2022. 1. 20. [자바] 후입선출(LIFO, Last In First Out)의 자료구조 - 스택(Stack) 스택 Stack(겹겹이 쌓다.) 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입 선출(LIFO, Last In First Out)로 잘 알려져 있습니다. 스택은 배열 또는 링크드 리스트로 구현할 수 있습니다. 두가지의 차이점은 배열은 스택의 용량이 정해져 있지만, 링크드 리스트는 용량이 정해져 있지 않습니다. 이번 포스팅에서는 배열로 구현을 하지만, 기회가 있다면 링크드 리스트를 이용하여 배열을 구현해보도록 하겠습니다. IntStack 생성자 package stack; public class IntStack { private int max; // 스택 용량 private int ptr; // 스택 포인터 private int[] stk; //.. 2022. 1. 9. [자바] 가장 빠른 정렬 알고리즘 - 퀵 정렬 (Quick Sort) 퀵 정렬 Quick(빠른) + Sort(정렬) 퀵 정렬은 가장 빠른 정렬 알고리즘으로 잘 알려져 있습니다. 퀵 정렬은 데이터 그룹에서 그룹을 나누는 기준인 피벗(pivot)을 선택하고, 피벗을 기준으로 그룹을 나누는 것을 반복하여 각 그룹이 1개가 되면 정렬을 마칩니다. 아래의 그림을 통해 자세하게 살펴보겠습니다. 왼쪽 끝에 커서를 pl, 오른쪽 끝의 커서를 pr, 중간의 x 화살표를 피벗이라고 하겠습니다. 양쪽 끝의 커서는 피벗과 비교할 숫자를 가리키게 됩니다. [pl] >= x 가 성립하는 데이터를 찾을 때까지 pl을 오른쪽으로 스캔합니다. [pr] pivot) { // data[pr] 값이 pivot보다 작은 수 탐색 pr--; } if (pl pivot) { // data[pr] 값이 pivot보.. 2022. 1. 1. 이전 1 2 다음 반응형
