반응형 [Public] 컴퓨터공학27 [UVA] 100 3n+1 problem The 3n + 1 problem Background Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. The Problem Consider the following algorithm: 1. input n 2. print n 3. if n = 1 then STOP 4. if n is odd then 5. el.. 2011. 7. 25. [알고리즘] KMP 알고리즘 (문자열 검색 #2) 이번 시간에는 KMP 알고리즘에 대해서 설명하려고 한다. KMP 알고리즘 .. 이 역시 이전 카프라빈 알고리즘에 이어서 문자열을 검색하는데 있어 빠르게 검색하기 위한 문자열 검색 알고리즘 중 하나이다. (http://carstart.tistory.com/97) 카프라빈과의 차이점은 카프라빈은 매번 한칸식 이동하면서 문자열과 패턴의 비교를 줄여서 속도를 빠르게 하는 작업이라면 KMP와 나중에 나올 보이무어는 문자열의 비교를 하는 작업 보다는 비교할 필요가 없는 부분을 찾아 한칸이 아니라 비교할 필요없는 부분은 빼고 여러 칸씩 이동함에 있어 속도를 빠르게 한다. 자 그럼 KMP 알고리즘에 대해 알아보자.,, 먼저 왜 이름을 KMP 알고리즘이라 지었나요 ? Knuth Morris Partt 이름을 따서 만들어.. 2010. 8. 14. [자료구조] 그래프 #2 (깊이우선탐색 넓이우선탐색) 지난 번에는 그래프의 정의를 내리고 표현하는 법을 배웠다. 그래프만 잘 표현하면 뭐하나 그래프의 기능을 제대로 사용할려면 실질적으로 그래프를 잘 탐색해야 한다. 그래프의 탐색하는 방법에 대해서 알아보자. 그래프의 탐색 방법에는 크게 2가지로 나뉜다. 1. 깊이 우선탐색 (Depth First Search) 2. 넓이 우선탐색 (Breadth First Search) 많이 들어 보았을 것이다. 먼저 깊이 우선 탐색방법이다. 방식은 다음과 같다. 1. 시작되는 정점을 결정하고 방문한다. (시작점을 설정한다는 말이다.) 2. 시작정점에 인접된 정점중 방문되지 않는 정점을 선택 (인접한 정점중 방문하지 않는 곳으로 진행한다는 말이다.) 3. 모든 인접 정점을 스택에 저장 (시작점도 스택에 넣고 방문을 통한 모든.. 2010. 7. 12. [자료구조] 그래프 #1 (그래프의 정의) 오늘은 그래프 알고리즘에 대해서 알아보자. 동영상을 통하여 이야기를 할 것인데 필자의 HTML 기술 부족으로 동영상은 고정하고 글만 내리는 기능을 할 줄 모른다. 인터넷창 2개를 뛰우고 보는게 편할듯 싶다. 먼저 그래프에 대해서 알아보자 자료구조 시험시간이면 항상 트리와 한 묶음으로 나오는 단골 출제 문제 중 하나이다. 내가 생각하는 공부 방법은 이게 왜 배우고 어떻게 생겼는지를 가장 먼저 이해하는 것이다. 그래야 우리가 이를 왜 배우고 왜 해야하는지를 알기에 공부의 효율도 극대가 된다. 먼저 그래프가 어떻게 만들어 졌는지 알아보자 먼저 세계지도가 동영상에서 나올것이다. 우리나라 월드컵 첫을을 안겨준 유럽의 폴란드로 한번 가보자 폴란드 안에서 좀더 들어가 칼리니그라드 라는 곳에 가보자 여기에서 보이는 위.. 2010. 7. 7. [자료구조] 해시 함수 (Hash) #1 해시 함수 한 동안 글을 안올리고 방황하는 시기가 있었다. 다시 마음을 가다 듬고 올릴려고 한다. 이번에 소개할 내용은 해시 함수이다. 보통 자료구조 시간에 많이 들어봤을 것이다. 해시함수 이게 무엇일가 ? 해시의 어원부터 알아보자 해시를 사전에서 찾아보면 3가지가 나온다. 1. 해시시 ( 대마의 잎으로 만든 마약 ) 2. 그 일을 망쳐 놓는다 3. 잘게 자른 고기를 양파나 감자와 같은 재료와 함께 튀겨 한덩어리로 만든 요리 여기서 보면 "마약" 이건 아닐테고 "그 일을 망쳐놓는다." 이것 역시 알고리즘과 뭔 상관 ? 마지막 잘게 자른 고기를 하나로 합친다. 이게 좀 유사하겠다. 한마디로 원재료를 다른 재료와 함께 다지고 썩고 볶고 .... 등등 해서 완전히 새로운 다른 형태의 요리로 만든다는 것인데 한.. 2010. 6. 14. [알고리즘] 쉘 정렬 (Shell Sort) (정렬#4) 쉘 정렬 (Shell Sort ) 정렬 4번째 이야기 쉘 정렬을 알기전에 삽입정렬(Insert Sort)를 먼저 알아야 한다. 모른다면 삽입정렬에 대해서 알고 와라~ 정렬 2번째 이야기에 삽입 정렬에 대해 자세히 설명되어 있다. 그럼 쉘 정렬이 먼지 알아보자 쉘정렬은 삽입정렬의 단점을 보완한 정렬이다. 삽입정렬의 단점은 요소들이 삽입 될때 이웃한 위치로만 이동을 한다. 이동 하는 과정에서 위치가 멀리 떨어진 곳이라면 많은 이동에 대한 오버헤드가 발생한다. 그래서 도날드. L. 쉘 이라는 사람이 간격(Gap) 이라는 것을 생각한 것이다 그래서 쉘 정렬 이 아닌가 싶다. 위의 조개사진은 무관하다. ㅋ 방법은 데이터를 일정의 간격(Gap)을 만들고 이 간격들을 각각 삽입정렬을 통하여 정렬한다. 그리고 다시 간.. 2010. 5. 20. 이전 1 2 3 4 5 다음 반응형
