알고리즘/개념2

• 

  투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기 투 포인터 알고리즘이란? 주로 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법 이 알고리즘을 사용하면 선형 시간 복잡도 O(N)으로 동작하며, 정렬된 배열 또는 리스트에서 특정한 합이나 패턴을 찾는 문제에 효과적으로 사용된다 예시? 예시는 이전에 백준 알고리즘 1644번: 소수의 연속합 문제에 사용되었던 투 포인터 알고리즘을 사용한 풀이에서 예시를 들어 설명하도록 하겠다 문제에 대한 설명은 아래 참고 링크에 올라온 글을 참고하면 좋을 것 같다 이 문제의 경우, 소수들의 연속적인 합이 몇개가 있는지 출력하는 문제이다 target number가 41인 경우를 예를 들어 설명하자면, 먼저 에라토스테네스의 체 알고리즘을 사용하여 41까지의 소수를 primes 배열에 저장할 것이다 그 후 현재.. 알고리즘/개념 2023. 7. 2.

• 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 원리? 자연수 a와 b가 있다고 하면, a를 b로 나눈 나머지를 구한다. 나머지를 r이라고 한다. 나머지 r이 0이라면, b는 a와 b의 최대공약수이다. 따라서 알고리즘을 종료하고 b를 결과로 출력한다. 만약 나머지 r이 0이 아니라면, b를 a로 대체하고, r을 b로 대체한다. 다시 말해서 GCD(a, b) = GCD(b, r) 인 것이다. 식으로 풀면, a = bq + r 일 때 GCD(a, b) = GCD(b, r)이다 예시? 48과 18의 최대공약수(GCD)를 구해보면, 1. 48 % .. 알고리즘/개념 2023. 6. 19.