>탐색,정렬,수치계산,문자열 탐색이유명한 알고리즘이다
선형탐색법(리니어서치)-맨 앞부터 순서대로 찾는다
이진탐색법(바이너리서치)-범위를 절반씩출려가면서 찾는다
해시 탐색- 계산해서 저장 위치를 찾는다
정렬
단순 정렬법(선택소트)-최솟(댓)값을 선택하여 맨 앞부터순서대로 나열한다.
단순 교환법(버블소트)-옆에있는데이터를 교환하면서자리를 바꿔 나열한다
단순 삽입버(삽입소트)-데이터를 올바른 위치에 삽입하면서 자리를바꿔나열
퀵정렬 - 기준 데이터를 기반으로 대소분할을 반복하여 자리를 바꿔 나열
머지 정렬- 이분할과 머지(병합)을 이용하여 자리를 바꿔 나열한다
힙 정렬 - 힙이라는 데이터 구조를 이용하여 자리를 바꿔 나열한다
셀 정렬 - 그룹을 나누면서 자리를바꿔 나열한다
수치계산(수치해석)
에라토스테네스의 체 -소수를 구하는 알고리즘
유클리드 알고리즘 - 최대 공약수를 구하는 알고리즘
가우스 소거법 - 연립 1차 방정식을 푸는 알고리즘
사다리꼴 법칙 - 정적분의 근삿값을 구하기 위한 알고리즘
다익스트라 알고리즘 -그래프에서 최적 경로를 구하는 알고리즘
이분법 - 방정식을 푸는 알고리즘
뉴턴법 - 방정식을 푸는 알고리즘
문자열 탐색
무차별 검색법-맨 앞부터 한 문자씩 차례대로 탐색
KMP - 불일치 부분에 착목하여 탐색
BM - 부분 문자열의 끝에서부터 탐색
탐색 알고리즘
선형 탐색법
공의 숫자가 무엇인지 상자 안에서 꺼내보기
선형 탐색법의 절차
맨 앞 칸의 공부터 순서대로 하나씩 값을확인하여 찾고 있는 공과 일치하는지 여부
선형 탐색법 알고리즘
탐색처리의 흐름
탐색시작
일치하고 있는지 비교
일치하면 종료
배열과 요소의설정
-요소는 5개 요소의 첨자는 0에서 4까지
반복 처리에는반드시 종료 조건을 넣을것
이진 탐색법(바이너리 서치)
1가운데에 있는 공의 숫자를 살펴본다
22차시도 다시한 번 가운데 공의 숫자를 살펴본다
3 3차시도, 다시 한 번 가운데 공의 숫자를 살펴본다.
가운데 요소를 선택하는 처리- 가운데 요소와 원하는 데이터 비교하기
-탐색 범위를 절반으로 좁히기 -만약 원하는 데이터가 존재하지 않으면?
선형 탐색법 < 이진 탐색법
해시 탐색법
데이터의 내용과 저장한 곳의 요소를 미리 연계해줌으로써 극히 짧은 시간안에 탐색할 수 있도록 고안된 알고리즘
미리 탐색하기 쉽도록 공을 보관한다
-어떤 값에 해당하는 다른 값이 산출되는 계산식 '함수'
-해시라는 단어는 원래의 숫자를 모양이 변할 정도로 요리하여 전혀 다른 값을 생성한다. 라는 의미로, 해시 포테이토, 해시드 비프 등
해시 함수로 해시값을 구하는 계산식-'공의 숫자 % 7'
해시함수로 데이터를 보관하는 알고리즘
1.해시 함수로 데이터를 저장하는 알고리즘
2.해시 함수로 데이터를 검색하는 알고리즘
배열을 2개 준비한다
arrayD[0]의 데이터를 arrayH에 저장하기
해시값(저장소인 arrayH첨자)=arrayD의 데이터 % 11
해시 탐색법으로 데이터를 탐색하는 알고리즘
탐색 대상이 되는 배열
12가 저장되어 있는 요소를 검색하기
36이 저장되어있는 요소를 검색하기
정렬알고리즘
검색 엔진이나 엑셀에서도 정렬은 중요하다
>유명한 정렬 알고리즘 네가지
단순 선택법(선택정렬)
단순 교환법(버블정렬)
단순 삽입법(삽입정렬)
퀵 정렬
단순 선택법
-오름차순인 경우, 먼저 가장 작은 숫자의 공을 찾는다
숫자가 가장 작은 공을 맨 앞의 데이터와 교환
다음으로 숫자가 작은 공을 두 번째 공과 교환
3개 중에서 가장 숫자가 작은 공을 세 번째 공과 교환
남은 2개를 오름차순으로 정렬
알고리즘
array[0]부터 array[4]사이의 최솟값을 찾는다
쵯솟값과 array[0]의 데이터를 교환한다
array[1]부터 array[4]사이의 최솟값을 찾는다
최솟값과 array[1]의 데이터를 교환한다.
array[2]부터 array[4]사이의 최솟값을 찾는다
최솟값과 array[2]의 데이터를 교환한다
array[3]부터 array[4]사이의 최솟값을 찾는다
최솟값과 array[3]의 데이터를 교환한다
i->indexMin
array[1]<array[indexMin]
1->indexMin
array[2]<array[indexMin]
잠정 최솟값과 비교하는 요소의 첨자를 변수K로 치환한다
최솟값과 array[i]의 데이터를 교환한다
세 가지 처리를 조합하여 순서도를 완성
단순 교환법
버블 정렬
데이터를 교환하는 처리를 반복하여 모든 데이터를 정렬하는 알고리즘이다
공을 오름차순으로 정렬
0번칸에 1인 공을 가져간다
1번칸에 2인 공을 가져간다
2번 칸에 3인 공을 가져간다
3번 칸에 4인 공을 가져간다
1.오른쪽 끝부터 순서대로 인접한 공을 오름차순으로 정렬한다
2.왼쪽 끝 칸부터 순서대로 들어갈 공을 확정시켜나간다
단순 삽입법
삽입 정렬
단순 교환법과 같이 정렬 알고리즘 중에서는 비교적 간단한 알고리즘에 속한다
첫 번째 칸의 공을 올바른 위치에 삽입하기
두 번째 칸의 공을 올바른 위치에 삽입하기
세 번째 칸의 공을 올바른 위치에 삽입하기
네 번째 칸의 공을 올바른 위치에 삽입하기
퀵정렬
-처리 속도가 빠른 정렬 알고리즘 대량의 데이터를 정렬할 때 자주 사용된다. 실제로 사용되는 빈도가 높다
퀵 정렬로 공을 오름차순으로 정렬해 보자
맨앞의 5를 기준으로 공을 대소로 나누기
맨 앞의 3을 기준으로 공을 대소로 나누기
맨 앞의 2를 기준으로 공을 대소로 나누기
맨 앞에 있는 8을 기준으로 공을 대소로 나누기
앞의 7을 기준으로 공을 대소로 나누기
퀵정렬의 알고리즘
기준값을 경계로 데이터를 대소로 나누는 처리
나눈 데이터에 대해 반복적으로 똑같은 작업 실행하기
기준값을 경계로 데이터를 대소로 나누는처리
퀵 정렬의 핵심은 데이터를 대소로 나누는 처리다
배열의 왼쪽과 오른쪽부터 각각 변수를 움직여 대소로 정렬한다
기준값을 작은 데이터와 큰 데이터의 중앙으로 이동한다
나눈데이터에 다시 한법 같은 처리를 실행하는 처리
quicksort를 보조프로그램으로 한다
보조 프로그램으로 정의하려면?
프로그램 :QuickSort(인수1,인수2..)
출처- 처음만나는 알고리즘
---
대략적인 내용을 정리해보았다 자세한내용은 앞으로 포스팅에 순서도와 추가할계획이다
