DevJay

최근 알고리즘 문제를 풀고 있는데, 소수를 찾는 문제를 자주 접한다. 물론 BruteForce 방식으로 찾아도 기능상엔 문제가 없지만, 수행 속도면에서 몇몇 문제의 결과가 실패로 나타나곤 한다. 이때 에라토스테네스의 체라는 개념을 접하게 되었다. 에라토스테네스의 체란? 에라토스테네스의 체는 무엇일까? 고대 그리스 수학자가 체로 숫자를 걸러내는 방식이라 하여 체라는 단어가 붙었다고 한다. 이는 소수를 찾기 위한 가장 간단하고 빠른 방법으로 알려져있다. 방법 1부터 100까지 숫자가 있다고 가정하자. 소수도 아니고 합성수도 아닌 자연수 1을 제외하자. 2를 제외한 모든 2의 배수는 소수가 아니니 제외하자. 3을 제외한 모든 3의 배수는 소수가 아니니 제외하자. 4의 배수는 2의 배수를 처리할 때 이미 지워졌..

문자열 탐색 많은 사람들이 업무를 하기 위해 문서를 볼 때 원하는 부분을 빠르게 찾기 위해 문자열 검색이라는 기능을 사용하곤 한다. 보통 Ctrl + F 단축키를 이용하여 현재 보이는 화면내의 수 많은 문자 중에서 원하는 문자열을 찾는다. 일상 속에서 자연스럽게 사용하고 있는 기능이지만, 수 많은 문자중에 원하는 문자열을 빠르게 찾기까지 알고리즘이 존재한다. Brute Force 먼저, 단순하게 생각해보자. 위 처럼 "SON IS BEST PLAYER"라는 텍스트가 존재하고 우리는 "BEST"라는 문자열 패턴을 찾아보자. Brute Force 방식에서는 막연하게 모든 텍스트를 지나가면서 패턴과 해당 위치의 텍스트를 비교한다. 텍스트 인덱스 0과 문자열 패턴인텍스 0을 먼저 비교한다. S와 O는 서로 다른..

정의 임의의 점들의 집합에서 해당 집합을 감싸는 가장 큰 외곽선을 찾는다. 구현 1) 여러 개의 점을 기준에 따라 정렬한다. var sorted = Sort(items, selector); 아래는 점들을 정렬하기 위한 함수이다. 가장 좌하단에 있는 점을 찾고, 그 점과 이루는 각에 따라 오름차순으로 정렬한다. 각도가 같을 경우에는 가까운 순으로 정렬한다. private static List Sort(IEnumerable items, Func selector) { // 좌하단 기준점 수집 var first = items .MinItems(item => selector(item).Y) .MinItem(item => selector(item).X); return items .OrderBy(i => GetDeg..