Nanarin🙃

일반적으로 A와 B의 최대공약수를 구하는 가장 쉬운 방법은 A와 B를 2부터 A와 B중 더 작은 수 까지 모든 자연수로 나누는 것이다. 이 방법은 수가 커질수록 시간이 오래걸려 비효율적이며, 모든 수로 나눠야 하므로 시간복잡도는 O(n)이 된다. 이때 유클리드 호제법을 사용한다. 유클리드 호제법 (Euclidean Algorithm) : 두 정수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘 A > B 일 때1. A % B = C2. B % C = D3. 위 과정을 계속 반복4. X % Y = 0, Y가 A와 B의 최대공약수 그림으로 표현해 보자 두 정수 A, B를 직사각형의 두 변의 길이라고 생각하면 직사각형을 정사각형으로 완전히 채우려고 할 때 정사각형의 가장 긴 변의 길..

이진 탐색(Binary Search) 알고리즘 : 요소가 오름차순 또는 내림차순으로 정렬(sort)된 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 탐색. 선형 탐색보다 좀 더 빠르게 탐색 가능 값 53을 탐색 1. 배열의 중앙 Binary[5] 와 비교, 53 > Binary[5] => Binary[5] 이전 배열 탐색 대상에서 제외 2. Binary[6] ~ Binary[10]의 중앙 Binary[8] 과 비교, 53 Binary[8] 이후 배열 탐색 대상에서 제외 3. Binary[6] ~ Binary[7]의 중앙 Binary[6] 과 비교, 53 == Binary[6] => 탐색 성공 맨 앞의 인덱스를 pl, 맨 끝의 인덱스를 pr, 중앙 인덱스를 pc라고 할 때 ..

선형 탐색(Linear Search) 알고리즘 or 순차 탐색(Sequential Search) 알고리즘 : 요소가 직선 모양으로 늘어진 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 맨 앞부터 순서대로 탐색 위 배열에서 요소를 탐색하면 값 5를 탐색하면 Linear[2] 에서 탐색에 성공하지만 값 3을 탐색하면 Linear에 값 3이 존재하지 않기 때문에 탐색에 실패한다. 위 예시를 보면 배열 탐색의 종료 조건이 다음 2개임을 알 수 있다. 조건 1 : 탐색할 값과 같은 요소를 발견한 경우 (탐색 성공) 조건 2 : 탐색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (탐색 실패) 배열의 요소 수가 n개 일 때 조건 1,2를 판단하는 횟수는 평균 n/2회 이다. => O(n) 메서드 seqSea..