전체 글
-
소수 찾기(에라토스테네스의 체)Computer Science/Algorithm 2020. 2. 9. 21:51
일반 방법으로 "소수찾기" 알고리즘 문제를 풀면 시간초과를 경험하는 일이 많기 때문에 에라토스테네스의 체를 이용해서 소수를 구해보자. 2부터 n까지의 모든 수를 나열한다. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를 모두 지운다. 3은 소수이기에 체크하고, 똑같이 3의 배수를 모두 지운다. 다음 소수인 5도 지워지지 않았기에, 5의 배수를 모두 지운다. 위의 과정을 n의 제곱근전의 최대 소수까지 반복을 해준다 (Math.sqrt())를 이용하자. https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 | 프로그래머스 1부터 입력받은 숫자 n 사이에 있는 소수..
-
이진 탐색(Binary Search) 란?Computer Science/Data_Structure 2020. 1. 30. 15:50
정렬된 배열에서의 이진 탐색 정렬된 배열의 탐색에는 이진 탐색(binary search)이 가장 적합하다. 이진 탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 이러한 방법에 의해 매 단계에서 검색해야 할 배열의 크기를 반으로 줄인다. 10억명의 정렬된 배열에서 이진 탐색을 이용하여 특정한 이름을 찾기 위해서는 단지 30번만 비교하면 된다. 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를..
-
백 트래킹 (Backtracking) 이란?Computer Science/Algorithm 2020. 1. 30. 14:21
1. 백 트래킹 (Backtracking) 백트래킹 (Backtracking) 또는 퇴각 검색 (Backtrack)으로 불린다. 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보를 체크하지 않을 것을 표기)하고, 바로 다른 후보로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보)를 상태공간트리(State Space Tree)를 통해 표현 각 후보를 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바..