記錄

이 글은 슬라이딩 윈도우와 투 포인터 알고리즘을 정리하는 글입니다. 비슷한 성향의 알고리즘이라 한 포스팅에 같이 정리해봅니다. 01 Sliding Window 창문이 옮겨간다는 이름의 이 알고리즘 풀이 방식은 고정된 범위(창문)가 자동으로 옮겨가면서(=구간의 길이가 같음) 창문 내에 있는 데이터를 이용해 조건에 해당하는 답을 반환하게 된다. 시간복잡도가 O(n)이다. 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법으로 매번 처리되는 중복된 요소를 버리지 않고 재사용함으로써 낭비되는 계산을 하지 않음으로써 효율적으로 처리한다. 배열이나 리스트의 요소들의 일정 범위 값을 비교할 때 사용되며, 배열의 정렬 여부에 관계 없이 활용 가능하다. 예시문제 문제 원문 및 설명 링크 크기가 num인..

이 글은 유클리드 호제법에 대한 설명과 최대공약수와 최소공배수를 JavaScript로 구현하는 방식에 대해 정리하는 글입니다. 01 유클리드 호제법 유클리드 호제법(Euclidean algorithm)이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 유클리드 호제법의 원리는 다음과 같다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다. 이 성질에 따라, b를 r로 나눈 나머지 ..

00. 에라토스테네스의 체란 에라토스테네스의 체(Sieve of Eratosthenes) 란 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(prime number)를 찾는 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 이러한 이름이 붙여졌다. 가장 대표적인 소수 판별 알고리즘으로, 2 이상 n 이하의 정수 x가 소수인지 아닌지 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘이다. 소수(prime number)는 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 양의 정수로 2,3,5,7,11...등의 숫자들이 소수에 속한다. 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2. 2는 소수이므로 오른쪽에 2..

이 글은 완전 탐색의 개념과 완전 탐색 기법을 활용한 알고리즘의 종류들을 간략하게 정리하고, 순열과 조합을 메인으로 설명한다. 01 경우의 수 Number of Cases 경우의 수(境遇─數, number of cases)란, 어떤 사건(일)이 일어날 수 있는 경우의 가짓수(outcomes)를 수로 표현한 것이다. 1회의 시행에서 일어날 수 있는 사건의 가짓수를 n이라고 할 때 이 때의 경우의 수를 n이라고 한다. 각 사건이 일어날 확률들의 관계를 알 수 있다면 경우의 수를 통해 각 확률을 구할 수 있기 때문에 완전탐색 알고리즘에서 사용된다. 02 완전 탐색 Exhaustive search 완전 탐색이란 모든 경우의 수를 나열하는 방식으로 답을 구하는 방법이다. '무식하게 푼다'라는 의미인 Brute-F..