이것이 취업을 위한 코딩 테스트다 책 부록에 있는 기타 알고리즘 몇 가지를 정리해봤다.
소수 판별
소수란 1보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수를 뜻한다. 쉽게 말해 1과 자기 자신으로만 나누어지는 자연수이다. 보통 소수인지 아닌지 판별하는 함수를 작성하라고 하면 아래처럼 코드를 짤 것이다.
나도 대부분 위처럼 코드를 작성해왔는데, 백준에서 문제를 풀다보면 빈번히 시간 초과가 뜬다. 1,000,000 처럼 큰 수가 입력으로 들어오면 2부터 999,999까지 모든 수에 대한 연산이 이루어지기 때문에 상당히 비효율적인 코드이다.
따라서 약수의 특성을 이용하면 훨씬 효율적인 코드를 작성할 수 있다. 16이라는 수를 예로 들면,
- 1, 2, 4, 8, 16
가운데를 기준점으로 삼아 양쪽 수를 2개씩 곱하면 죄다 16이 된다. 그렇기 때문에 2부터 15까지 연산할 필요 없이 16의 제곱근인 4까지만 계산하면 된다.
그렇다면 하나의 수에 대한 소수를 판별하는 것이 아닌, 수의 범위가 주어진 경우에는 어떻게 해야 할까?
에라토스테네스의 체
여러 개의 수가 소수인지 아닌지 판별할 때 사용하는 대표적인 알고리즘이 바로 에라토스테네스의 체 알고리즘이다. 사실 나는 이 알고리즘을 소수 구하기 문제를 풀 때 처음 접했다. 계속 시간초과 뜨길래 찾아보니 거의 모든 사람들이 해당 알고리즘을 문제를 풀어냈다.
알고리즘은 아래와 같은 방식으로 동작한다.
- 2부터 N까지의 모든 자연수를 나열한다.
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i를 제외한 i의 모든 배수들을 제거한다.
- 반복할 수 없을 때 까지 2번과 3번의 과정을 반복한다.
앞서 소개한 소수 판별과 마찬가지로 i는 N의 제곱근까지만 증가시켜서 확인하면 된다.
메모리가 많이 필요하다는 단점이 있지만 선형 시간에 동작할 정도로 빠른 성능을 보여준다.
투 포인터
투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 대표적으로 특정한 합을 갖는 부분 연속 수열 찾기 문제와 정렬되어 있는 두 리스트의 합집합 문제에서 사용된다.
특정한 합을 갖는 부분 연속 수열 찾기
- 1, 2, 3, 2, 5
리스트에서 합이 5가 되는 부분 연속 수열을 찾아보자.
- 시작점과 끝점이 첫 번째 인덱스를 가리키도록 한다.
- 현재 부분합 = M : 카운트
- 현재 부분합 < M : 끝점 + 1
- 현재 부분합 >= M : 시작점 + 1
- 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
끝점을 증가시키면 합이 증가하고, 시작점을 증가시키면 합이 감소하기 때문에 투 포인터 알고리즘으로 해결할 수 있다. 하지만 리스트 내 음수가 포함되어 있는 경우에는 사용할 수 없다.
정렬되어 있는 두 리스트의 합집합
- 1, 3, 5
- 2, 4, 6, 8
2개의 리스트를 합쳐 정렬한 결과를 계산해보자.
- 정렬된 리스트 A와 B를 입력받는다.
- 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.
- 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다.
- A[i]와 B[j] 중 더 작은 원소를 결과 리스트에 담는다.
- 더 이상 처리할 원소가 없을 때까지 2번부터 4번까지의 과정을 반복한다.
익히 알고 있겠지만 해당 알고리즘은 병합 정렬에서도 사용된다.
참고
- 이것이 취업을 위한 코딩 테스트다
