알고리즘 | 종류 (탐색, 정렬, 그리드)

 

알고리즘이란 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합을 뜻합니다.

어떤 방식들이 있는지 한 번 살펴보겠습니다.

 

 

 

탐색 알고리즘

1. 선형 탐색 : x와 a1 비교, x!=a1 이면 a2와 비교... 순차적으로 탐색

2. 이진 탐색 : 오름차순으로 비교 되어있는 리스트를 둘로 쪼개 첫리스트의 마지막 항과 비교... 계속 둘로 나눠서 비교

---

 

 

정렬 알고리즘

1. 버블정렬 : 배열 앞뒤를 비교하고 작은 수를 앞으로 보내고, 반복해서 정렬

2. 선택정렬 : 기준값을 선택. 리스트 중 최소값을 찾아서 기준값과 교환

3. 삽입정렬 : 새로운 리스트에 정렬할 리스트의 값을 차례대로 비교 정렬 후 삽입

---

 

 

욕심쟁이 알고리즘 (Greedy Method)

각 단계에서 가장 최선일 것 같은 것을 선택하는 알고리즘

---

 

 

비지루프

오로지 빙글빙글 돌면서 시간을 때우는 방법

-> CPU가동 되므로 좋지 않다.

차라리 할 일을 없을때 CPU를 재워라

---

 

비율에 따른 난수

문제1) 1, 2, 3 의 난수 확률은 10%, 20%, 70%면

100까지의 난수발생 후 1-10은 1, 11-30은 2, 31-100은 3 -> 가중치를 두는 간단한 방법

문제2) 0 또는 1 의 난수를 발생하는 식을 만들되 0과 1의 발생 비율이 5:8의 비율이 되도록 하라

 

(((int)(Math.random() * 13)/8) - 1)*-1

(int)((Math.random()*(x1+x2))/x2) 

n = Random().nextInt(5 + 8) / 8;           //  8 : 5 의 발생 빈도

n = 1 - Random().nextInt(5 + 8) / 8;      // 5 : 8 의 발생 빈도

---