본문 바로가기

Algorithmic Wisdom 🧠10

[알고리즘][탐색] - 깊이 우선 탐색(DFS) 깊이 우선 탐색(Depth-first Search)이란? "루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법" 넓이 우선 탐색과 (Breadth-first Search) 대비되는 알고리즘으로 말 그대로 넓이 보단 깊이를 우선적으로 탐색하겠다는 뜻 먼저 그림을 통해 이해를 해보자 이제 위에서 본 그림을 인접리스트를 사용한 JAVA 코드로 풀어보자 사용할 LinkedList와 boolean타입의 배열 선언부 /* * 먼저 정점들의 연결 다리가 되어줄 * LinkedList와 * * 방문 여부를 확인할 * boolean 타입의 배열을 선언 */ public class DFS { private LinkedList list[]; // 정점들의 인접 리스트를 저장하는 배열 pri.. 2023. 12. 3.
[알고리즘][탐색] - 선형 탐색 & 이진 탐색 & 해시 탐색 탐색 알고리즘이란? 저장된 데이터들 중 원하는 값을 찾는 알고리즘 선형 탐색 알고리즘 보편적으로 정렬되지 않은 배열이나 리스트에 사용되며 단순하게 맨 앞이나 뒤에서 시작하여 순차적으로 탐색하는 알고리즘 첫 번째 원소가 정답인 경우: 1 마지막 원소가 정답인 경우: n ∴ O(n) 의 시간 복잡도를 가진다 이진 탐색 알고리즘 정렬된 배열이나 리스트에 사용되며 리스트의 중간값과 찾으려는 값의 대소를 비교하여 탐색 범위를 반으로 줄여가며 값을 탐색하는 알고리즘 (탐색하려고 하는 값이 정렬된 리스트의 중간값보다 크면 중간값을 포함한 하위값들은 탐색 대상에서 제외되며 중간값보다 작으면 상위값들은 탐색에서 제외된다) 첫 번째 원소가 정답인 경우: 1 마지막 원소가 정답인 경우: log2(n) ∴ O(log2(n)).. 2023. 8. 6.
[알고리즘][정렬] - 삽입 정렬 삽입 정렬이란? 데이터들을 기존의 배열과 비교하여 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘 삽입 정렬 예시 오름차순으로 정렬된 [1, 2, 3, 4, 5, 6, 8, 9] 배열이 존재한다고 가정하고 7 이라는 새로운 데이터가 주어졌을 경우 앞(뒤)에서부터 비교하여 6 과 8 사이에 삽입 뒤에서부터 비교하는 삽입 정렬 예시 int[] preSortedArray = {1, 2, 3, 4, 5, 6, 8, 9}; int preSortedArrayLength = preSortedArray.length; int newData = 7; int placeInArray; // 크기 증가가 안되는 배열의 특성을 고려하여 새로운 배열 생성 int[] newArray = new int[preSortedArray.. 2023. 7. 28.
[알고리즘][재귀] - 유클리드 알고리즘 (Euclidean algorithm) 최대공약수(Greatest common divisor)란? "0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다." 최대공약수를 구하는 가장 대표적인 방법 (소인수분해와 나눗셈을 이용하는 방법)은 소인수분해 원리에 기반을 두기에, 정수의 크기가 커질수록 직접 소인수분해 하기엔 부담이 된다. 이때 효과적인 방법은 나눗셈 정리에 기반을 둔 유클리드 호제법을 사용하는 것이다. 유클리드 호제법이란(Euclidean algorithm)? "2개의 자연수 또는 정식의 최대공약수를 구하는 인류 최초의 알고리즘이다." 두 양의 정수 a , b (a < b)에 대하여 a = b * q + r (0≤ r < b)이라 하면, a , b 의 최대공약수는 b , r 의 최대공약수와 같다. 즉 gcd(a , b.. 2023. 7. 8.
728x90
반응형

티스토리툴바