노트정리/알고리즘
탐색 알고리즘 - 다양한 탐색법
컴퓨터의 기억공간 내에 저장한 특정 항목의 위치를 찾거나 자료가 집합 내에 없을 경우에는 특정한 메시지를 출력하여 주는운영 방법을 탐색이라고 합니다. 컴퓨터를 이용하는 최고의 목적은 정보를 저장하고 정리한 후 탐색하는 것이죠. 탐색에 들어가기전알아야할 용어들이 있습니다. 기본적인 용어는키 : 키는 파일 내의 레코드를 다른 레코드와 구별할 수 있는 항목기본키 : 특별히 각 레코드를 완전히 구분할 수 있는 검색키레코드 : 1개 이상의 항목들을 서로 관련 있는 것끼리 짝을 지어 모은 형태딕셔너리 : 검색이라는 자료 처리를 하기 위하여 키와 레코드 및 기본 연산들을 자료 구조 형태로 표현해 놓은 것심벌 테이블 : 프로그램에 대한 딕셔너리로 자료 구조에 대한 모든 명세들을 가지고 있으며 보통 이름과 값으 쌍으로 ..
노트정리/알고리즘
정렬 알고리즘 - 외부 정렬
외부 정렬주기억장치의 용량이 적기 때문에 자료의 양이 많은 대형 파일은 한 번에 내부 정렬로 처리 하는 것이 힘듭니다.그래서 대형 파일을 여러 개의 부분 파일로 나누어 보조기억장치에 저장합니다. 그런 다음 각각의 부분 파일을 내부 정렬에의해 정렬하고 합병시켜 정렬하죠. 이와 같이 순차적접근 방식의 자기 테이프나 직접 적근 방식의 자기 디스크와 같은같은 보조기억장치를 이용하여 정렬하는 방식을 외부 정렬 이라 합니다.보조기억장치를 이용하는 외부 정렬 방법 중 가장 일반적인 방법은 합병 정렬입니다. 이 방법은 입력 파일을 몇 개의 부분 파일로분리하여 각각을 적절한 내부 정렬 방법으로 정렬한 다음 다시 보조기억공간에 저장한다. 이와 같이 정렬한 부분 파일을런이라고 합니다. 그 다음 먼저 만들어진 런들은 회전을 ..
노트정리/자료구조
정렬 알고리즘 3부 - 계수,기수,버킷 정렬
계수 정렬계수 정렬은 입력키가 어떤 범위, 예를 들어 1부터 k 사이의 작은 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법으로어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있다. 예를 들어 입력키들이숫자일 때 입력에 10이라는 키가 있고 이보다 작은 키가 5개 있다면 10 은 정렬 순서에서 여섯 번째에 위치한다. 계수 정렬에서는입력키들이 범위 k 내의 각 값에 대하여 입력키가 실제로 입력에 나타나는 횟수를 계산한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676..
노트정리/자료구조
정렬알고리즘2부 - 퀵,합병,히프 정렬
퀵 정렬 퀵 정렬 의 기본 개념은 기준이 되는 숫자 피벗을 정한 후에 그 숫자를 기준으로 작은 데이터와 큰 데이터를 나누고 다시분리한 양쪽의 데이터에서 다시 기준이 되는 숫자를 정한 후 그숫자를 기준으로 작은 데이터와 큰 데이터를 나누는 작업을반복하는 것입니다.. 이러한 작업을 위해선 기준이 되는 값보다 작은 값을 찾기 위한 인덱스와 큰 값을 찾기 위한인덱스가 필요합니다..작은 값을 찾기 위한 인덱스는 왼쪽에서 진행하고 큰 값을 찾기 위한 인덱스는 오른쪽부터 진행합니다.왼쪽에서 진행하는 인덱스는 기준값보다 크거나 같은 경우에 멈추고 오른쪽에서 진행하는 인덱스는 기준값보다 작거나 같은경우에 멈춥니다. 그 상태에서 해당 인덱스에 위치한 데이터의 위치를 서로 바꿉니다. 이 작업을 반복하면 기준값을 기준으로 좌..
오늘도 삽질
