Euclidean Algorithm 유클리드 호제법 알고리즘
Euclidean Algorithm 유클리드 호제법 알고리즘 유클리드 호제법 알고리즘은 두 수의 최대 공약수를 구하는 알고리즘이다. 최대 공약수를 구하는 방법은 소인수분해를 이용하여 공통된 소수들의 곱으로 표현할 수 있지만, 유클리드 호제법 알고리즘을 활용하면 간단하게 구현 가능하다. 유클리드 호제법 수행 과정 큰 수...
Tag: algorithm
Euler's phi 오일러 피 알고리즘
Euler’s phi Algorithm 오일러 피(파이) 알고리즘 오일러 피 알고리즘은 N 까지 범위 안에서 서로소인 수를 찾아내는 알고리즘이다. 서로소? 최대공약수가 1 인 두 자연수 오일러 피 수행 과정 오일러 피의 범위 N 만큼의 배열(P[N])을 선언한다. 2 부터 시작하여 현재 배열의 값과 인덱스...
Sieve of Eratosthenes 에라토스테네스의 체
Sieve of Eratosthenes Algorithm 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘은 소수 찾기에 많이 활용되는 알고리즘이다. 에라토스테네스의 체 수행 과정 소수 찾고자 하는 수를 1차원 배열에 나열한다. 숫자 1 는 제외하고, 2 부터 자기 자신을 배수로 하고 있는 숫자를 삭제한다....
Greedy Algorithm 그리디 알고리즘
Greedy Algorithm 그리디 알고리즘 그리디 알고리즘은 현재 상태에서 최선의 선택지가 전체 문제를 해결할 수 있다고 가정하는 알고리즘이다. 그리디 알고리즘 수행 과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검...
BFS 너비 우선 탐색 알고리즘
BFS Algorithm Breadth-First-Search 너비 우선 탐색 알고리즘 너비 우선 탐색 알고리즘은 DFS와 동일하게 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하여 탐색하는 알고리즘이다. 특징 FIFO 탐색 Queue 자료구조 활용 시간...
DFS 깊이 우선 탐색 알고리즘
DFS Algorithm Depth-First-Search 깊이 우선 탐색 알고리즘 깊이 우선 탐색 알고리즘은 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 특징 재귀 함수로 ...
Quick Sort Algorithm 퀵 정렬 알고리즘
Quick Sort Algorithm 퀵 정렬 알고리즘 퀵 정렬 알고리즘은 분할 정복 알고리즘을 기반으로 비교적 많이 사용하는 정렬 알고리즘이다. 기본적인 시간 복잡도는 O(NlogN) 이지만, 최악의 경우에는 O(N^2) 이 될 수도 있다. 특징 분할 정복 활용 시간 복잡도 : O(NlogN) 구현 순서 ...