yoo.dev

투포인터 알고리즘이란 주어진 배열에서 연속합을 이용한 문제일때 사용할 수 있는 알고리즘. 보통 연속합으로 가능한 경우의 수를 구하거나, 그 길이를 구하거나 할때 사용된다. (대표문제 참고) start, end라는 변수를 배열의 인덱스로 사용하며 sum(arr[start:end])을 구하는 방법이다. 처음에 start = end = 0으로 시작하고, start arr[start:end]) 예를들어 배열의 연속합이 S가 되는 경우의 수를 구하는 문제에서는 무한루프를 돌며 sum이 S보다 작은 경우: sum += arr[++end] sum이 S와 같거나 클 경우: sum -= arr[start++] 를 해준 후, 무한루프는 start == end == len(arr)이 되면 빠져나온다. 저장할때는 파이썬의 s..

소수 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. (1과 본인 외의 약수가 없는 수) 가장 작은 소수는 2로, 유일한 짝수이다. 에라토스테네스의 체 (자연수 n까지의 소수 구하는 방법) 1. n+1개 크기의 배열 생성 후 True로 초기화 2. 최소 소수인 2부터 sqrt(n)까지 확인하면서 2-1. 소수인 경우(True), 본인보다 큰 (본인을 제외) 본인의 배수를 모두 False로 바꿔줌 3. 배열에서 소수인 애들의 인덱스를 0과 1을 제외하고 리턴 sqrt(n)까지만 확인하는 이유 n까지 해도 값의 차이는 없다. 다만, n을 소수에서 제외시킬 수 있는 약수는 sqrt(n)이하일 수 밖에 없기때문에 불필요한 연산을 없애 시간을 줄여준다. 예) n = 10 / n의 약수..

유클리드 호제법이란 최대공약수를 구하기 위해서는 유클리드 호제법을 사용하면 된다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다. 먼저 1071을 1029로 나눈다. 42라는 나머지가 나온다. 만약 1029가 42로 나누어진다면 1071 = 42 * n이 될텐데 42로 안나눠지니까 42는 최대공약수가 될 수 없다. 그 후 1029을 42로 나눠서 21을 얻는다. 이때 42는 21로 나누어지기 때문에 21을 약수로 가진다. 따라서 최대공약수는 21이다. 글로 읽으면 복잡한데 결국 1071은 1071 = (1029 * 1) + 42 = ((42 * k) * 1) + 42 = (((21*2) *k) *1) + (21*2) = 21 * (k+2) 로 쓰일수 있다는걸 생각..

계수 정렬(Counting Sort)이란 원소끼리 비교를 하지 않고 원소가 몇번 등장하는지 갯수를 세서 정렬하는 방법이다. 따라서 비교정렬이 아니고 같은 원소의 순서가 바뀌지 않는 안정정렬(stable sort)이다. 시간복잡도는 O(n + k)으로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다. k: 정렬할 수들 중 가장 큰 값 n: 정렬할 수의 개수 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다. 가장 큰 숫자에 영향을 받는다는 단점이 있다. 만약 정렬해야하는 리스트가 [0, 1, 9999]일때는 배열에 2부터 9998까지 불필요한 공간을 만들어야하기 때문에 비효율적이다. 또, n의 값이 너무 커지면 일반 정렬 알고리즘보다 느려질 수 있으므로 적..