반응형 [Public] 컴퓨터공학/알고리즘13 [알고리즘] 에라토스테네스의 체 (소수#2) 에라토스테네스의 체 2011. 09. 25 저번 소수#1 시간에는 주어진 소수가 소수인지 여부를 판별하는 거에 대해서알아봤습니다. 이번 시간은 에라토스테네스의 체에 대해서 알아볼려고 합니다. 에라토스테네스의 체는 소수를 구할 때 유용하게 사용되는 방법이라 할수가 있겠습니다. 먼저 에라토스테네스의 체란 무엇일가요 ? 에라토스테네스의 체는 사람의 이름입니다 그리스의 수학자이자 지리학자인 에라토스테네스는 소수를 찾는 방법을 고안하였습니다. 방법은 체란 말이 들어 가있드시 걸러낸다는 방법입니다. 그럼 어떻게 걸러내서 소수를 구하죠 ? 예를 들어 1~ 100까지 안의 솟수를 구한다면 방법은 2의 배수, 3의배수, 5의 배수를 걸러 내면 남는 수가 소수가 된다는 것입니다. 역시 말은 어렵네요 예를들어 보여주세요 !.. 2011. 9. 25. [알고리즘] KMP 알고리즘 (문자열 검색 #2) 이번 시간에는 KMP 알고리즘에 대해서 설명하려고 한다. KMP 알고리즘 .. 이 역시 이전 카프라빈 알고리즘에 이어서 문자열을 검색하는데 있어 빠르게 검색하기 위한 문자열 검색 알고리즘 중 하나이다. (http://carstart.tistory.com/97) 카프라빈과의 차이점은 카프라빈은 매번 한칸식 이동하면서 문자열과 패턴의 비교를 줄여서 속도를 빠르게 하는 작업이라면 KMP와 나중에 나올 보이무어는 문자열의 비교를 하는 작업 보다는 비교할 필요가 없는 부분을 찾아 한칸이 아니라 비교할 필요없는 부분은 빼고 여러 칸씩 이동함에 있어 속도를 빠르게 한다. 자 그럼 KMP 알고리즘에 대해 알아보자.,, 먼저 왜 이름을 KMP 알고리즘이라 지었나요 ? Knuth Morris Partt 이름을 따서 만들어.. 2010. 8. 14. [알고리즘] 쉘 정렬 (Shell Sort) (정렬#4) 쉘 정렬 (Shell Sort ) 정렬 4번째 이야기 쉘 정렬을 알기전에 삽입정렬(Insert Sort)를 먼저 알아야 한다. 모른다면 삽입정렬에 대해서 알고 와라~ 정렬 2번째 이야기에 삽입 정렬에 대해 자세히 설명되어 있다. 그럼 쉘 정렬이 먼지 알아보자 쉘정렬은 삽입정렬의 단점을 보완한 정렬이다. 삽입정렬의 단점은 요소들이 삽입 될때 이웃한 위치로만 이동을 한다. 이동 하는 과정에서 위치가 멀리 떨어진 곳이라면 많은 이동에 대한 오버헤드가 발생한다. 그래서 도날드. L. 쉘 이라는 사람이 간격(Gap) 이라는 것을 생각한 것이다 그래서 쉘 정렬 이 아닌가 싶다. 위의 조개사진은 무관하다. ㅋ 방법은 데이터를 일정의 간격(Gap)을 만들고 이 간격들을 각각 삽입정렬을 통하여 정렬한다. 그리고 다시 간.. 2010. 5. 20. [알고리즘] 삽입 정렬 (Insert Sort) (정렬#3) (3 번째 정렬 Story) 삽입 정렬 이번엔 삽입 정렬이다. 삽입정렬의 방법은 이미 나열되어 있는 정렬할 공간에서 가장 작은 범위 부터 시작하여서 작은 범위 안에서 가장 작은 수가 나올때 까지 옆으로 이동하면서 마지막의 수를 이동한 자리의 빈공간에 넣어준다 하여 삽입 정렬이라 한다. 말로 설명하면 잘 모르니 그림을 보자 5 -> 1 -> 7 -> 4 -> 2 -> 6 -> 3 의 데이터를 정렬 할려고 한다. 가장 작은 정렬 할 범위를 지정해주고 늘려가면서 진행된다. 먼저 시작점을 설정해야한다. 시작점을 0부터 하면 그 전 데이터가 없기 때문에 시작 점을 1부터 하고 진행한다. 자 그럼 정렬을 시작 해 보장 저장 [ 5 -> 1 ]-> 7 -> 4 -> 2 -> 6 -> 3 [1]저장 데이터 공간의 시.. 2010. 5. 12. [알고리즘] 선택 정렬 (Selection Sort) (정렬#2) (2번째 정렬 Story) 선택 정렬 원리가 가장 간단한 알고리즘 중 하나로 오른쪽 리스에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동작업을 오른쪽 리스트가 공백 상태가 될 때 까지 되풀이 하는 방법이다. 말로 하면 이해하기 힘드니 아래 그림을 보면 쉽게 이해를 할 것이다. 지금 5 3 8 1 2 7 이라는 오른쪽 공간이 있다. 여기서 가장 작은 수를 찾는 것이다. 그 작은 수를 왼쪽 공간에 차례로 넣어주면서 오른쪽 공간에서 더이상 수가 존재하지않으면 선택정렬은 종료가 되는 것이다. 하지만.... 항상 그래 왔듯이 여기에는 문제점이 있다. 그래 저번에 배운 공간 복잡도에 대해서 생각을 하지 않은 것이다. 위에서 표현하는 자료는 비록 6개의 자료를 담고 있지만 회사에서 사용하는 10만개가 넘어가는 자료.. 2010. 5. 4. [알고리즘] 버블정렬 (Bubble Sort) (정렬#1) 정렬 이야기 (첫번째 이야기) - 버블 정렬 오늘은 많은 정렬 중 버블 정렬에 대해서 설명해보려고 한다. 버블 정렬, 거품 정렬 등등으로 많이 불린다. 왜 거품, 버블 정렬 일가? 이 질문에 답은 아래를 읽다 보면 해결 할 수 있다. 먼저 방법을 알고 가자 버블 정렬의 방법은 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환(SWAP) 하여서 계속 진행하는 방식이다. 이렇게 말하면 절대 모르지... ㅋㅋ 그림으로 보자 5 - 3 - 8 - 1 - 2 - 7 순서로 나열되어 있다. 이를 오름차순으로 나열 하기 위하여 버블 정렬을 사용하면 인접한 두개의 값을 비교하여 조건과 일치하면 서로 교환해주는 것이다. 5 - 3 - 8 - 1 - 2 - 7 (5>3) 3 - 5 - 8 - 1 - 2.. 2010. 4. 28. 이전 1 2 3 다음 반응형
